// Las tres reducciones en un grafo pequeño, comparadas con fuerza bruta, y una reducción mal hecha.
#include <iostream>

#include "graphs.h"

namespace {

Graph small_graph() {
    return {6, {{0, 1}, {0, 2}, {1, 2}, {2, 3}, {3, 4}, {4, 5}}};
}

void print_edges(const Graph& g) {
    for (auto [u, v] : g.edges) std::cout << ' ' << u << '-' << v;
    std::cout << '\n';
}

std::string yes_no(bool answer) { return answer ? "sí" : "no"; }

// Busca el conjunto más grande que cumple check, entre todas las máscaras.
template <typename Check>
unsigned best_set(const Graph& g, Check check, bool largest) {
    unsigned best = 0;
    bool found = false;
    for (unsigned set = 0; set < (1u << g.n); set++) {
        if (!check(g, set)) continue;
        int size = std::popcount(set), size_best = std::popcount(best);
        if (!found || (largest ? size > size_best : size < size_best)) best = set;
        found = true;
    }
    return best;
}

// Recorre los grafos de menos a más nodos, hasta que CI(G, k) y CV(G, k) no coinciden.
void print_counterexample() {
    for (int n = 1; n <= 4; n++) {
        for (unsigned edges = 0; edges < (1u << (n * (n - 1) / 2)); edges++) {
            Graph candidate{n, {}};
            int bit = 0;
            for (int u = 0; u < n; u++) {
                for (int v = u + 1; v < n; v++) {
                    if ((edges >> bit++) & 1u) candidate.edges.emplace_back(u, v);
                }
            }
            for (int k = 1; k <= n; k++) {
                Instance in{candidate, k};
                if (has_independent_set(in) != has_vertex_cover(in)) {
                    std::cout << "  el contraejemplo más chico: " << n << " nodos, aristas:";
                    print_edges(candidate);
                    std::cout << "  k = " << k << ": CI dice " << yes_no(has_independent_set(in)) << ", CV dice "
                              << yes_no(has_vertex_cover(in)) << '\n';
                    return;
                }
            }
        }
    }
}

}  // namespace

int main() {
    const Graph g = small_graph();
    std::cout << "G tiene " << g.n << " nodos y estas aristas:";
    print_edges(g);
    unsigned independent = best_set(g, is_independent_set, true);
    unsigned cover = best_set(g, is_vertex_cover, false);
    std::cout << "conjunto independiente máximo: " << set_to_string(independent, g.n) << ", tamaño "
              << std::popcount(independent) << '\n';
    std::cout << "cobertura mínima:              " << set_to_string(cover, g.n) << ", tamaño " << std::popcount(cover)
              << '\n';
    const unsigned rest = ((1u << g.n) - 1) & ~independent;
    std::cout << "V − S = " << set_to_string(rest, g.n) << ", ¿es cobertura? " << yes_no(is_vertex_cover(g, rest))
              << '\n';

    std::cout << "\nConjunto independiente a cobertura, con k → n − k:\n";
    std::cout << "  k  CI(G, k)  CV(G, n − k)\n";
    for (int k = 0; k <= g.n + 1; k++) {
        Instance in{g, k};
        std::cout << "  " << k << "  " << yes_no(has_independent_set(in)) << "        "
                  << yes_no(has_vertex_cover(independent_set_to_vertex_cover(in))) << '\n';
    }

    const Graph h = complement(g);
    std::cout << "\nEl complemento tiene estas aristas:";
    print_edges(h);
    unsigned clique = best_set(h, is_clique, true);
    std::cout << "clique máximo del complemento: " << set_to_string(clique, g.n) << ", tamaño "
              << std::popcount(clique) << '\n';
    std::cout << "  k  CI(G, k)  clique(complemento, k)\n";
    for (int k = 0; k <= g.n + 1; k++) {
        Instance in{g, k};
        std::cout << "  " << k << "  " << yes_no(has_independent_set(in)) << "        "
                  << yes_no(has_clique(independent_set_to_clique(in))) << '\n';
    }

    std::cout << "\nUna reducción mal hecha: conservar k, sin cambiarlo por n − k.\n";
    print_counterexample();

    std::cout << "\n2-coloreo a 3-coloreo: agregar un nodo vecino de todos.\n";
    const Graph pentagon{5, {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}}};
    const Graph square{4, {{0, 1}, {1, 2}, {2, 3}, {3, 0}}};
    for (const auto& [name, graph] : {std::pair{"ciclo de 4", square}, std::pair{"ciclo de 5", pentagon}}) {
        std::cout << "  " << name << ": 2 colores con BFS: " << yes_no(two_colorable(graph))
                  << "; 3 colores en el grafo con el nodo nuevo: " << yes_no(colorable_brute_force(add_apex(graph), 3))
                  << '\n';
    }
}