// DFS con tiempos: la tabla de la clase, los tipos de arista, el orden topológico y el atajo.
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

#include "digraph.h"

namespace {

std::string order_text(const std::vector<int>& order) {
    std::string text;
    for (int v : order) text += std::to_string(v) + " ";
    if (!text.empty()) text.pop_back();
    return text;
}

}  // namespace

int main() {
    Digraph g = {{1, 2, 3}, {2}, {0}, {2}, {3, 5}, {4}};
    std::vector<ClassifiedEdge> kinds;
    DfsTimes t = dfs_recursive(g, &kinds);
    std::cout << "Grafo con ciclos:\n";
    std::cout << "  nodo  inicio  fin\n";
    for (int v = 0; v < static_cast<int>(g.size()); v++) {
        std::printf("  %4d  %6d  %3d\n", v, t.start[v], t.finish[v]);
    }
    std::cout << "  arista  tipo\n";
    for (const ClassifiedEdge& e : kinds) {
        std::printf("  %d -> %d  %s\n", e.u, e.v, kind_name(e.kind));
    }

    // Tareas para armar un programa: toda arista va de una tarea a otra que la necesita.
    Digraph dag = {{1, 2}, {3}, {3, 4}, {5}, {5}, {}};
    DfsTimes d = dfs_recursive(dag);
    std::cout << "\nDAG: 0->1 0->2 1->3 2->3 2->4 3->5 4->5\n";
    std::cout << "  nodo  inicio  fin\n";
    for (int v = 0; v < static_cast<int>(dag.size()); v++) {
        std::printf("  %4d  %6d  %3d\n", v, d.start[v], d.finish[v]);
    }
    std::cout << "  terminan en este orden: " << order_text(d.finish_order) << "\n";
    std::vector<int> topo = reverse_finish_order(dag);
    std::cout << "  orden decreciente de fin: " << order_text(topo) << "  "
              << (is_topological(dag, topo) ? "es topológico" : "no es topológico") << "\n";

    Digraph with_cycle = {{1}, {2}, {0, 3}, {}};
    std::vector<int> not_topo = reverse_finish_order(with_cycle);
    std::cout << "\nCon un ciclo: 0->1 1->2 2->0 2->3\n";
    std::cout << "  orden decreciente de fin: " << order_text(not_topo) << "  "
              << (is_topological(with_cycle, not_topo) ? "es topológico" : "no es topológico") << "\n";

    Digraph small = {{1, 2}, {2}, {}};
    std::vector<int> shortcut = stack_shortcut_order(small);
    std::vector<int> shortcut_reversed(shortcut.rbegin(), shortcut.rend());
    DfsTimes real = dfs_iterative(small);
    std::cout << "\nEl atajo de la pila, en 0->1 0->2 1->2:\n";
    std::cout << "  pila con (nodo, siguiente), terminan: " << order_text(real.finish_order)
              << "  al revés: " << order_text(reverse_finish_order(small)) << "  "
              << (is_topological(small, reverse_finish_order(small)) ? "topológico" : "no topológico") << "\n";
    std::cout << "  atajo, orden al sacar: " << order_text(shortcut) << "  "
              << (is_topological(small, shortcut) ? "topológico" : "no topológico") << "\n";
    std::cout << "  atajo, al revés:       " << order_text(shortcut_reversed) << "  "
              << (is_topological(small, shortcut_reversed) ? "topológico" : "no topológico") << "\n";
}