// Tres reglas para la cobertura de vértices: la que falla, la que tiene factor 2 y la natural.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <string>

#include "cover.h"

namespace {

std::string list(const cover::Nodes& nodes) {
    std::string text = "{";
    for (std::size_t i = 0; i < nodes.size(); i++) text += (i > 0 ? ", " : "") + std::to_string(nodes[i]);
    return text + "}";
}

void compare_on(const std::string& title, int n, const cover::Edges& edges) {
    std::cout << title << '\n';
    std::cout << "  una sola punta: " << list(cover::one_endpoint_cover(n, edges)) << '\n';
    const auto matched = cover::matching_cover(n, edges);
    std::cout << "  matching maximal, " << matched.matching.size() << " aristas: " << list(matched.cover) << '\n';
    std::cout << "  mayor grado: " << list(cover::greedy_degree_cover(n, edges)) << '\n';
    std::cout << "  óptimo por fuerza bruta: " << cover::minimum_cover_size(n, edges) << "\n\n";
}

}  // namespace

int main() {
    compare_on("Estrella con centro 0 y 6 hojas:", 7, {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}});
    compare_on("Camino 0-1-2-3, primero la arista 0-1:", 4, {{0, 1}, {1, 2}, {2, 3}});
    compare_on("Camino 0-1-2-3, primero la arista 1-2:", 4, {{1, 2}, {0, 1}, {2, 3}});
    compare_on("Una sola arista:", 2, {{0, 1}});

    std::cout << "La trampa del mayor grado:\n";
    std::cout << "   k  nodos  aristas  mayor grado  matching  mayor grado / k\n";
    for (int k : {6, 12, 24, 48, 96, 192}) {
        const auto trap = cover::greedy_trap(k);
        const auto chosen = cover::greedy_degree_cover(trap.nodes, trap.edges);
        const auto matched = cover::matching_cover(trap.nodes, trap.edges);
        std::cout << std::string(k < 10 ? 3 : (k < 100 ? 2 : 1), ' ') << k << "  " << trap.nodes << "  "
                  << trap.edges.size() << "  " << chosen.size() << "  " << matched.cover.size() << "  "
                  << static_cast<double>(chosen.size()) / k << '\n';
    }

    std::cout << "\n300 grafos al azar, 16 nodos, cada arista con probabilidad 1/4:\n";
    std::mt19937 rng(15);
    long long sum_opt = 0;
    long long sum_matching = 0;
    long long sum_greedy = 0;
    double worst_matching = 0;
    double worst_greedy = 0;
    const int graphs = 300;
    for (int g = 0; g < graphs; g++) {
        cover::Edges edges;
        for (int u = 0; u < 16; u++) {
            for (int v = u + 1; v < 16; v++) {
                if (rng() % 4 == 0) edges.push_back({u, v});
            }
        }
        const int opt = cover::minimum_cover_size(16, edges);
        const auto matching = cover::matching_cover(16, edges).cover.size();
        const auto greedy = cover::greedy_degree_cover(16, edges).size();
        sum_opt += opt;
        sum_matching += static_cast<long long>(matching);
        sum_greedy += static_cast<long long>(greedy);
        if (opt > 0) {
            worst_matching = std::max(worst_matching, static_cast<double>(matching) / opt);
            worst_greedy = std::max(worst_greedy, static_cast<double>(greedy) / opt);
        }
    }
    std::cout << "  promedio del óptimo: " << static_cast<double>(sum_opt) / graphs << '\n';
    std::cout << "  promedio del matching: " << static_cast<double>(sum_matching) / graphs
              << ", peor razón " << worst_matching << '\n';
    std::cout << "  promedio del mayor grado: " << static_cast<double>(sum_greedy) / graphs
              << ", peor razón " << worst_greedy << '\n';
}