PathFinder.h

#ifndef PATHFINDER_H
#define PATHFINDER_H

#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include "PachnerGrid.h"

class PathFinder {
public:
    // Find shortest path from start to end vertex using BFS
    static std::vector<int> findShortestPath(const PachnerGrid& grid, int start, int end) {
        auto adj = grid.getAdjacencyList();
        int n = grid.vertexCount();

        std::vector<bool> visited(n, false);
        std::vector<int> parent(n, -1);
        std::queue<int> q;

        visited[start] = true;
        q.push(start);

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            if (curr == end) break;

            for (int neighbor : adj[curr]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = curr;
                    q.push(neighbor);
                }
            }
        }

        // Reconstruct path
        std::vector<int> path;
        if (!visited[end]) return path;

        int curr = end;
        while (curr != -1) {
            path.push_back(curr);
            curr = parent[curr];
        }
        std::reverse(path.begin(), path.end());
        return path;
    }

    // Get all edges that are part of the path
    static std::set<std::pair<int, int>> getPathEdges(const std::vector<int>& path) {
        std::set<std::pair<int, int>> edges;
        for (size_t i = 0; i + 1 < path.size(); ++i) {
            int u = std::min(path[i], path[i + 1]);
            int v = std::max(path[i], path[i + 1]);
            edges.insert({ u, v });
        }
        return edges;
    }

    // Check if an edge is part of the path
    static bool isPathEdge(const std::set<std::pair<int, int>>& pathEdges, int u, int v) {
        int a = std::min(u, v);
        int b = std::max(u, v);
        return pathEdges.count({ a, b }) > 0;
    }
};

#endif // PATHFINDER_H