// Cuánto cuesta el matching como flujo: aumentos y tiempo, con grafos al azar de grado fijo. Se compila con -O2.
#include <chrono>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>

#include "matching.h"

namespace {

Options random_options(int n, int degree, std::uint32_t seed) {
    std::mt19937 random(seed);
    Options options(static_cast<std::size_t>(n));
    for (auto& list : options) {
        for (int k = 0; k < degree; k++) {
            int j = static_cast<int>(random() % static_cast<std::uint32_t>(n));
            if (std::find(list.begin(), list.end(), j) == list.end()) list.push_back(j);
        }
    }
    return options;
}

}  // namespace

int main() {
    std::cout << "     n   aristas  matching  aumentos EK  ms EK  aumentos DFS  ms DFS\n";
    for (int n : {2000, 4000, 8000, 16000, 32000}) {
        Options options = random_options(n, 3, 12345);
        std::size_t edges = 0;
        for (const auto& list : options) edges += list.size();
        MatchingNetwork bfs = matching_network(options, n);
        auto start = std::chrono::steady_clock::now();
        long long value = bfs.flow.edmonds_karp(bfs.source, bfs.sink);
        auto middle = std::chrono::steady_clock::now();
        MatchingNetwork dfs = matching_network(options, n);
        auto middle2 = std::chrono::steady_clock::now();
        long long value2 = dfs.flow.ford_fulkerson(dfs.source, dfs.sink);
        auto end = std::chrono::steady_clock::now();
        assert(value == value2);
        std::cout.width(6);
        std::cout << n;
        std::cout.width(10);
        std::cout << edges;
        std::cout.width(10);
        std::cout << value;
        std::cout.width(13);
        std::cout << bfs.flow.augmentations();
        std::cout.width(7);
        std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(middle - start).count();
        std::cout.width(14);
        std::cout << dfs.flow.augmentations();
        std::cout.width(8);
        std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - middle2).count() << '\n';
    }
}