// Recorridos de un grafo: BFS, DFS, caminos, componentes y ciclos.
#ifndef TRAVERSALS_H
#define TRAVERSALS_H

#include <algorithm>
#include <cstddef>
#include <queue>
#include <utility>
#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.
// order: los nodos en el orden en que salieron de la cola.
struct BfsResult {
    std::vector<int> distance;
    std::vector<int> parent;
    std::vector<int> order;
};

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();
        result.order.push_back(u);
        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;
}

inline void dfs_visit(const Graph& graph, int u, std::vector<bool>& marked, std::vector<int>& order) {
    marked[u] = true;
    order.push_back(u);
    for (const Edge& edge : graph.neighbors(u)) {
        if (!marked[edge.to]) {
            dfs_visit(graph, edge.to, marked, order);
        }
    }
}

// DFS recursivo: gasta un marco de llamada por cada nodo del camino actual.
inline std::vector<int> dfs_recursive(const Graph& graph, int source) {
    std::vector<bool> marked(graph.node_count(), false);
    std::vector<int> order;
    dfs_visit(graph, source, marked, order);
    return order;
}

// El mismo orden que la versión recursiva, con una pila propia: cada entrada es un nodo y la
// posición de su lista por la que iba, justo lo que guardaría su marco de llamada.
inline std::vector<int> dfs_iterative(const Graph& graph, int source) {
    std::vector<bool> marked(graph.node_count(), false);
    std::vector<int> order;
    std::vector<std::pair<int, std::size_t>> stack;
    marked[source] = true;
    order.push_back(source);
    stack.push_back({source, 0});
    while (!stack.empty()) {
        auto& [u, next] = stack.back();
        const std::vector<Edge>& list = graph.neighbors(u);
        if (next == list.size()) {
            stack.pop_back();
            continue;
        }
        int v = list[next].to;
        next++;
        if (!marked[v]) {
            marked[v] = true;
            order.push_back(v);
            stack.push_back({v, 0});  // invalida u y next, que no se vuelven a usar en esta vuelta
        }
    }
    return order;
}

// La cola de BFS cambiada por una pila: se marca al sacar, y un nodo puede estar varias veces.
// Visita lo mismo, pero en otro orden, y la pila puede llegar a tener Θ(E) entradas.
inline std::vector<int> stack_search(const Graph& graph, int source) {
    std::vector<bool> marked(graph.node_count(), false);
    std::vector<int> order;
    std::vector<int> stack{source};
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        if (marked[u]) {
            continue;
        }
        marked[u] = true;
        order.push_back(u);
        for (const Edge& edge : graph.neighbors(u)) {
            if (!marked[edge.to]) {
                stack.push_back(edge.to);
            }
        }
    }
    return order;
}

// Componente de cada nodo, numeradas desde 0. Una búsqueda por cada nodo sin marcar.
inline std::vector<int> component_labels(const Graph& graph) {
    std::vector<int> label(graph.node_count(), -1);
    int count = 0;
    for (int start = 0; start < graph.node_count(); start++) {
        if (label[start] != -1) {
            continue;
        }
        std::vector<int> stack{start};
        label[start] = count;
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            for (const Edge& edge : graph.neighbors(u)) {
                if (label[edge.to] == -1) {
                    label[edge.to] = count;
                    stack.push_back(edge.to);
                }
            }
        }
        count++;
    }
    return label;
}

inline bool undirected_cycle_from(const Graph& graph, int u, int parent, std::vector<bool>& marked) {
    marked[u] = true;
    for (const Edge& edge : graph.neighbors(u)) {
        if (!marked[edge.to]) {
            if (undirected_cycle_from(graph, edge.to, u, marked)) {
                return true;
            }
        } else if (edge.to != parent) {
            return true;  // ya marcado y no es de donde vengo: hay otro camino hasta él
        }
    }
    return false;
}

// Para un grafo no dirigido sin aristas repetidas.
inline bool has_cycle_undirected(const Graph& graph) {
    std::vector<bool> marked(graph.node_count(), false);
    for (int start = 0; start < graph.node_count(); start++) {
        if (!marked[start] && undirected_cycle_from(graph, start, -1, marked)) {
            return true;
        }
    }
    return false;
}

enum class Color { White, Gray, Black };  // sin ver, en el camino actual, terminado

inline bool directed_cycle_from(const Graph& graph, int u, std::vector<Color>& color) {
    color[u] = Color::Gray;
    for (const Edge& edge : graph.neighbors(u)) {
        if (color[edge.to] == Color::Gray) {
            return true;  // volvió a un nodo del camino actual
        }
        if (color[edge.to] == Color::White && directed_cycle_from(graph, edge.to, color)) {
            return true;
        }
    }
    color[u] = Color::Black;
    return false;
}

// Para un grafo dirigido: hacen falta tres estados, no dos.
inline bool has_cycle_directed(const Graph& graph) {
    std::vector<Color> color(graph.node_count(), Color::White);
    for (int start = 0; start < graph.node_count(); start++) {
        if (color[start] == Color::White && directed_cycle_from(graph, start, color)) {
            return true;
        }
    }
    return false;
}

#endif