// Bellman-Ford: el grafo donde Dijkstra falla, la tabla d_i(v), la versión de una sola fila y cuánto
// importa el orden de las aristas.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "shortest_paths.h"

namespace {

std::string show(long long x) { return x >= INF ? "inf" : std::to_string(x); }

void print_row(const std::vector<long long>& row) {
    for (long long x : row) std::cout << std::setw(5) << show(x);
    std::cout << '\n';
}

// Una cadena 0 -> 1 -> ... -> n - 1, con sus aristas en el orden dado.
std::vector<Edge> chain(int n, bool forward) {
    std::vector<Edge> edges;
    for (int i = 0; i + 1 < n; i++) {
        const int a = forward ? i : n - 2 - i;
        edges.push_back({a, a + 1, 1});
    }
    return edges;
}

}  // namespace

int main() {
    const std::vector<Edge> edges = {{0, 1, 1}, {0, 2, 4}, {2, 1, -5}, {1, 3, 2}};
    std::cout << "Aristas: 0->1 (1), 0->2 (4), 2->1 (-5), 1->3 (2)\n";
    std::cout << "Dijkstra:    ";
    print_row(dijkstra(4, edges, 0));

    std::cout << "\nLa tabla d_i(v):\n  i    0    1    2    3\n";
    const auto table = bellman_ford_table(4, edges, 0, 4);
    for (std::size_t i = 0; i < table.size(); i++) {
        std::cout << std::setw(3) << i;
        for (long long x : table[i]) std::cout << std::setw(5) << show(x);
        std::cout << '\n';
    }

    std::cout << "\nUna sola fila, con las aristas en el orden de arriba:\n";
    std::cout << "vuelta  0    1    2    3\n";
    bellman_ford(4, edges, 0, [](int round, const BellmanFordResult& r) {
        std::cout << std::setw(3) << round << ' ';
        print_row(r.dist);
    });

    const std::vector<Edge> shuffled = {{1, 3, 2}, {2, 1, -5}, {0, 2, 4}, {0, 1, 1}};
    std::cout << "\nUna sola fila, con las aristas al revés:\n";
    std::cout << "vuelta  0    1    2    3\n";
    bellman_ford(4, shuffled, 0, [](int round, const BellmanFordResult& r) {
        std::cout << std::setw(3) << round << ' ';
        print_row(r.dist);
    });

    std::cout << "\nCuántas vueltas hacen falta, hasta una que no cambia nada, en una cadena de n nodos:\n";
    std::cout << "    n  aristas en orden  aristas al revés\n";
    for (int n : {10, 100, 1000}) {
        std::cout << std::setw(5) << n << std::setw(18) << bellman_ford(n, chain(n, true), 0).rounds << std::setw(18)
                  << bellman_ford(n, chain(n, false), 0).rounds << '\n';
    }
}