// Detectar un ciclo negativo y recuperarlo: el nodo relajado en la vuelta V puede no estar en el ciclo.
#include <iostream>
#include <vector>

#include "shortest_paths.h"

namespace {

void print_values(const char* name, const std::vector<long long>& values) {
    std::cout << name;
    for (long long x : values) std::cout << ' ' << (x >= INF ? "inf" : std::to_string(x));
    std::cout << '\n';
}

}  // namespace

int main() {
    // 0 -> 1, el ciclo 1 -> 2 -> 3 -> 1 de peso -1, y la cola 3 -> 4 -> 5.
    const int n = 6;
    const std::vector<Edge> edges = {{0, 1, 2}, {1, 2, 1}, {2, 3, 1}, {3, 1, -3}, {3, 4, 1}, {4, 5, 1}};
    std::cout << "Aristas: 0->1 (2), 1->2 (1), 2->3 (1), 3->1 (-3), 3->4 (1), 4->5 (1)\n";
    std::cout << "vuelta: d[0..5]\n";
    const BellmanFordResult r = bellman_ford(n, edges, 0, [](int round, const BellmanFordResult& partial) {
        std::cout << round << ":";
        print_values("", partial.dist);
    });
    std::cout << "nodo relajado al final de la vuelta " << n << ": " << r.witness << '\n';
    std::cout << "pred:";
    for (int p : r.pred) std::cout << ' ' << p;
    std::cout << '\n';

    std::cout << "\nLeer directamente desde ese nodo, hasta volver a él (se corta a los 12 pasos):\n ";
    int x = r.witness;
    for (int step = 0; step < 12; step++) {
        std::cout << ' ' << x;
        x = r.pred[idx(x)];
        if (x == r.witness) break;
    }
    std::cout << " ...\n";

    std::cout << "\nRetroceder " << n << " veces y recién entonces leer:\n ";
    x = r.witness;
    for (int step = 0; step < n; step++) {
        std::cout << ' ' << x;
        x = r.pred[idx(x)];
    }
    std::cout << " -> " << x << '\n';
    const std::vector<int> cycle = recover_cycle(n, r.pred, r.witness);
    std::cout << "ciclo:";
    for (int v : cycle) std::cout << ' ' << v;
    std::cout << " -> " << cycle[0] << ", peso " << cycle_weight(edges, cycle) << '\n';
}