// Pesos repetidos: varios árboles mínimos, y por qué el enunciado necesita el conjunto F.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#include "mst.h"

namespace {

std::string indices_text(const std::vector<Edge>& edges, const std::vector<int>& indices) {
    std::string text;
    for (int i : indices) {
        text += std::to_string(edges[i].u) + "-" + std::to_string(edges[i].v) + " ";
    }
    return text;
}

}  // namespace

int main() {
    std::vector<Edge> triangle = {{0, 1, 1}, {0, 2, 1}, {1, 2, 1}};
    std::cout << "Triángulo con tres pesos 1:\n";
    for (const std::vector<int>& tree : all_minimum_trees(3, triangle)) {
        std::cout << "  árbol mínimo: " << indices_text(triangle, tree) << "\n";
    }
    std::cout << "  cortes y una arista más barata de cada uno:\n";
    struct CutChoice {
        int side;
        const char* text;
        int edge;
    };
    for (const CutChoice& c : {CutChoice{0, "{0} | {1 2}", 0}, CutChoice{2, "{2} | {0 1}", 1}, CutChoice{1, "{1} | {0 2}", 2}}) {
        int lowest = 1000;
        for (const Edge& e : triangle) {
            if ((e.u == c.side) != (e.v == c.side)) lowest = std::min(lowest, e.weight);
        }
        const Edge& e = triangle[c.edge];
        bool crosses = (e.u == c.side) != (e.v == c.side);
        std::cout << "    " << c.text << ": " << e.u << "-" << e.v << " con peso " << e.weight
                  << (crosses && e.weight == lowest ? ", la más barata" : ", NO") << "\n";
    }
    std::cout << "  juntas forman " << count_components(3, triangle) << " grupo y "
              << (is_spanning_tree(3, triangle) ? "un árbol" : "un ciclo") << "\n";

    std::vector<Edge> ties = {{0, 1, 2}, {1, 2, 2}, {2, 3, 2}, {3, 0, 2}, {0, 2, 3}, {3, 4, 1}};
    std::cout << "\nCuadrado con pesos 2, diagonal 0-2:3 y 3-4:1:\n";
    for (const std::vector<int>& tree : all_minimum_trees(5, ties)) {
        long long cost = 0;
        for (int i : tree) cost += ties[i].weight;
        std::cout << "  árbol mínimo: " << indices_text(ties, tree) << " costo " << cost << "\n";
    }
    std::vector<Edge> reversed_list(ties.rbegin(), ties.rend());
    std::cout << "  Kruskal, con la lista como viene:  costo " << total_weight(kruskal(5, ties)) << "\n";
    std::cout << "  Kruskal, con la lista invertida:   costo " << total_weight(kruskal(5, reversed_list)) << "\n";
    std::cout << "  Prim desde 0:                      costo " << total_weight(prim(5, ties, 0).tree) << "\n";
    std::cout << "  Prim desde 4:                      costo " << total_weight(prim(5, ties, 4).tree) << "\n";
}