// Pregunta de repaso 4, con un ejemplo de cada problema y la fuerza bruta al lado.
#include <iostream>
#include "frontier.h"
#include "two_sat.h"

int main() {
    Dag dag = {{1, 2}, {3}, {3, 4}, {5}, {5}, {}};
    std::cout << "Camino más largo en un DAG de 6 nodos: " << longest_path_dag(dag) << " aristas, fuerza bruta "
              << longest_path_dag_brute(dag) << '\n';

    Graph triangle = make_graph(3, {{0, 1}, {1, 2}, {0, 2}});
    Graph square = make_graph(4, {{0, 1}, {1, 2}, {2, 3}, {0, 3}});
    std::cout << "2-coloreo: triángulo " << (two_coloring(triangle) ? "sí" : "no") << " (3 colores: "
              << (find_coloring(triangle, 3) ? "sí" : "no") << "), cuadrado " << (two_coloring(square) ? "sí" : "no") << '\n';

    Graph bowtie = make_graph(5, {{0, 1}, {1, 2}, {0, 2}, {2, 3}, {3, 4}, {2, 4}});
    Graph two_triangles = make_graph(6, {{0, 1}, {1, 2}, {0, 2}, {3, 4}, {4, 5}, {3, 5}});
    Graph tail = make_graph(4, {{0, 1}, {1, 2}, {0, 2}, {2, 3}});
    auto euler_line = [](const char* name, const Graph& g) {
        std::cout << "  " << name << ": grados y conexión " << (has_euler_cycle(g) ? "sí" : "no") << ", fuerza bruta "
                  << (euler_cycle_brute(g) ? "sí" : "no") << '\n';
    };
    std::cout << "¿Ciclo que use cada arista exactamente una vez?\n";
    euler_line("dos triángulos con un nodo común", bowtie);
    euler_line("dos triángulos separados        ", two_triangles);
    euler_line("triángulo con una cola          ", tail);

    std::cout << "Camino simple más largo, y camino hamiltoniano:\n";
    Graph star = make_graph(4, {{0, 1}, {0, 2}, {0, 3}});
    std::cout << "  cuadrado: " << longest_simple_path(square) << " aristas, de V − 1 = 3: hamiltoniano\n";
    std::cout << "  estrella: " << longest_simple_path(star) << " aristas, de V − 1 = 3: no hamiltoniano\n";

    std::vector<TwoClause> clauses = {{1, 2}, {-1, 3}, {-2, -3}};
    auto a = solve_two_sat(3, clauses);
    std::cout << "2-SAT: " << formula_text(two_clauses_as_formula(3, clauses)) << ": " << (a ? assignment_text(*a) : "insatisfacible") << '\n';
}