// Cada fila del cuadro de decisión con el mismo grafo de prueba: el algoritmo rápido frente a
// Bellman-Ford, que sirve en todas pero cuesta más.
#include <iostream>
#include <vector>

#include "all_pairs.h"

namespace {

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

}  // namespace

int main() {
    std::cout << "Sin pesos: 0->1, 0->2, 1->3, 2->3, 3->4\n";
    std::vector<Edge> unweighted = {{0, 1, 1}, {0, 2, 1}, {1, 3, 1}, {2, 3, 1}, {3, 4, 1}};
    print_row("BFS:         ", bfs_distances(5, unweighted, 0));
    print_row("Bellman-Ford:", bellman_ford(5, unweighted, 0).dist);

    std::cout << "\nDAG con un peso negativo: 0->1 (1), 0->2 (4), 2->1 (-5), 1->3 (2)\n";
    std::vector<Edge> dag = {{0, 1, 1}, {0, 2, 4}, {2, 1, -5}, {1, 3, 2}};
    print_row("orden topológico:", dag_distances(4, dag, 0));
    print_row("Bellman-Ford:    ", bellman_ford(4, dag, 0).dist);
    print_row("Dijkstra:        ", dijkstra(4, dag, 0));

    std::cout << "\nPesos no negativos: 0->1 (7), 0->2 (1), 2->1 (2), 1->3 (1), 2->3 (6)\n";
    std::vector<Edge> roads = {{0, 1, 7}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 6}};
    print_row("Dijkstra:    ", dijkstra(4, roads, 0));
    print_row("Bellman-Ford:", bellman_ford(4, roads, 0).dist);

    std::cout << "\nCon un ciclo: el orden topológico no se aplica. Aristas 0->1 (1), 1->2 (1), 2->1 (1)\n";
    const std::vector<Edge> cyclic = {{0, 1, 1}, {1, 2, 1}, {2, 1, 1}};
    std::cout << "  dag_distances devuelve " << dag_distances(3, cyclic, 0).size() << " valores\n";

    std::cout << "\nTodos los pares con un negativo: 0->1 (3), 1->2 (-1), 2->0 (2), 2->1 (4)\n";
    const std::vector<Edge> small = {{0, 1, 3}, {1, 2, -1}, {2, 0, 2}, {2, 1, 4}};
    const Matrix floyd = floyd_warshall(3, small).dist;
    const Matrix repeated = all_pairs_bellman_ford(3, small);
    for (int s = 0; s < 3; s++) {
        print_row("Floyd-Warshall:", floyd[idx(s)]);
        print_row("V Bellman-Ford:", repeated[idx(s)]);
    }
}