// BFS y reconstrucción de caminos, tal como quedaron en la semana 14.
#ifndef TRAVERSALS_H
#define TRAVERSALS_H

#include <algorithm>
#include <queue>
#include <vector>

#include "graph.h"

// distance[v]: aristas desde el origen, o -1 si no se llega a v.
// parent[v]: de dónde se llegó a v. -1 si no se llega, y el origen es su propio padre.
struct BfsResult {
    std::vector<int> distance;
    std::vector<int> parent;
};

inline BfsResult bfs(const Graph& graph, int source) {
    int n = graph.node_count();
    BfsResult result{std::vector<int>(n, -1), std::vector<int>(n, -1)};
    std::queue<int> pending;
    result.distance[source] = 0;
    result.parent[source] = source;
    pending.push(source);
    while (!pending.empty()) {
        int u = pending.front();
        pending.pop();
        for (const Edge& edge : graph.neighbors(u)) {
            if (result.distance[edge.to] == -1) {  // se marca al meterlo a la cola
                result.distance[edge.to] = result.distance[u] + 1;
                result.parent[edge.to] = u;
                pending.push(edge.to);
            }
        }
    }
    return result;
}

// Camino del origen a target, siguiendo parent hacia atrás. Vacío si no se llega.
inline std::vector<int> path_to(const std::vector<int>& parent, int target) {
    std::vector<int> path;
    if (parent[target] == -1) {
        return path;
    }
    int node = target;
    while (parent[node] != node) {
        path.push_back(node);
        node = parent[node];
    }
    path.push_back(node);
    std::reverse(path.begin(), path.end());
    return path;
}

#endif