// Edmonds-Karp frente a la cota O(VE) de iteraciones y a la regla de DFS, en redes por capas con
// capacidades al azar. Mide con -O2, una sola corrida por fila: los tiempos dependen de la máquina.
#include <chrono>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

#include "flow_checks.h"

namespace {

// Capas de width nodos entre la fuente y el sumidero, cada nodo con aristas a la capa siguiente.
// Con shuffled, las aristas se agregan en orden al azar, y los arcos de cada nodo quedan en otro orden.
FlowNetwork layered(int layers, int width, int out_degree, unsigned max_capacity, unsigned seed, bool shuffled = false) {
    std::mt19937 rng(seed);
    const int nodes = layers * width + 2;
    const int sink = nodes - 1;
    std::vector<EdgeSpec> edges;
    const auto node = [width](int layer, int k) { return 1 + layer * width + k; };
    const auto capacity = [&rng, max_capacity] { return 1 + static_cast<long long>(rng() % max_capacity); };
    for (int k = 0; k < width; k++) {
        edges.push_back({0, node(0, k), capacity()});
        edges.push_back({node(layers - 1, k), sink, capacity()});
    }
    for (int layer = 0; layer + 1 < layers; layer++) {
        for (int k = 0; k < width; k++) {
            for (int d = 0; d < out_degree; d++) {
                edges.push_back({node(layer, k), node(layer + 1, static_cast<int>(rng() % static_cast<unsigned>(width))), capacity()});
            }
        }
    }
    if (shuffled) {
        for (std::size_t i = edges.size(); i > 1; i--) std::swap(edges[i - 1], edges[rng() % i]);
    }
    return build_network(nodes, edges);
}

template <typename Rule>
void measure(const char* name, FlowNetwork net, Rule rule) {
    const int sink = net.node_count() - 1;
    const auto start = std::chrono::steady_clock::now();
    const FlowRun run = ford_fulkerson(net, 0, sink, rule);
    const std::chrono::duration<double, std::milli> elapsed = std::chrono::steady_clock::now() - start;
    std::cout << std::setw(7) << net.node_count() << std::setw(8) << net.edge_count() << std::setw(8) << name
              << std::setw(16) << run.value << std::setw(12) << run.iterations << std::setw(12)
              << static_cast<long long>(net.node_count()) * net.edge_count() << std::setw(11) << std::fixed
              << std::setprecision(1) << elapsed.count() << '\n';
}

}  // namespace

int main() {
    std::cout << "      V       E   regla           flujo iteraciones          VE         ms\n";
    for (int layers : {10, 20, 40}) {
        const FlowNetwork net = layered(layers, 10, 3, 1000000000U, 7U);
        measure("BFS", net, shortest_path_rule);
        measure("DFS", net, depth_first_rule);
    }
    std::cout << "\nLa red de 402 nodos, con las aristas agregadas en orden al azar:\n";
    std::cout << "      V       E   regla           flujo iteraciones          VE         ms\n";
    measure("BFS", layered(40, 10, 3, 1000000000U, 7U, true), shortest_path_rule);
    measure("DFS", layered(40, 10, 3, 1000000000U, 7U, true), depth_first_rule);
    std::cout << "\nLa misma red de 402 nodos con otras capacidades máximas, solo BFS:\n";
    std::cout << "      V       E   regla           flujo iteraciones          VE         ms\n";
    for (unsigned max_capacity : {10U, 1000U, 1000000U, 1000000000U}) {
        measure("BFS", layered(40, 10, 3, max_capacity, 7U), shortest_path_rule);
    }
}