// Mide las tres formas de calcular todos los pares. Con -O2, una corrida, en la máquina del momento.
#include <chrono>
#include <cstdio>
#include <functional>
#include <random>
#include <vector>

#include "all_pairs.h"

namespace {

double seconds_of(const std::function<void()>& work) {
    const auto start = std::chrono::steady_clock::now();
    work();
    return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}

std::vector<Edge> random_sparse(int n, int per_node, std::mt19937& gen) {
    std::vector<Edge> edges;
    for (int i = 0; i < n * per_node; i++) {
        const int a = static_cast<int>(gen() % static_cast<unsigned>(n));
        const int b = static_cast<int>(gen() % static_cast<unsigned>(n));
        if (a != b) edges.push_back({a, b, static_cast<long long>(gen() % 1000) + 1});
    }
    return edges;
}

std::vector<Edge> complete(int n, std::mt19937& gen) {
    std::vector<Edge> edges;
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            if (a != b) edges.push_back({a, b, static_cast<long long>(gen() % 1000) + 1});
        }
    }
    return edges;
}

// Una cadena con sus aristas al revés: el peor orden para una sola fila.
std::vector<Edge> reversed_chain(int n) {
    std::vector<Edge> edges;
    for (int a = n - 2; a >= 0; a--) edges.push_back({a, a + 1, 1});
    return edges;
}

void measure(const char* family, int n, const std::vector<Edge>& edges) {
    Matrix a;
    Matrix b;
    FloydResult c;
    const double t_dijkstra = seconds_of([&] { a = all_pairs_dijkstra(n, edges); });
    const double t_bellman = seconds_of([&] { b = all_pairs_bellman_ford(n, edges); });
    const double t_floyd = seconds_of([&] { c = floyd_warshall(n, edges); });
    std::printf("%-16s %5d %8zu %10.3f %10.3f %10.3f  %s\n", family, n, edges.size(), t_dijkstra, t_bellman, t_floyd,
                a == b && b == c.dist ? "iguales" : "DISTINTOS");
}

}  // namespace

int main() {
    std::mt19937 gen(2026);
    std::printf("%-16s %5s %8s %10s %10s %10s\n", "grafo", "V", "E", "V Dijkstra", "V B-F", "F-W");
    for (int n : {100, 200, 400}) measure("disperso, E=4V", n, random_sparse(n, 4, gen));
    for (int n : {100, 200, 400}) measure("completo", n, complete(n, gen));
    for (int n : {200, 400, 800}) measure("cadena al revés", n, reversed_chain(n));
}