// Caminos disjuntos: un flujo con un ciclo, aristas y nodos, no dirigido, y qué pasa si s y t son vecinos.
#include <iostream>
#include <string>
#include <vector>

#include "disjoint_paths.h"

namespace {

void print_trail(const std::vector<int>& trail, const std::string& names) {
    for (std::size_t k = 0; k < trail.size(); k++) {
        std::cout << (k ? " " : "") << names[static_cast<std::size_t>(trail[k])];
    }
}

void print_decomposition(const Decomposition& result, const std::string& names) {
    std::cout << "  caminos: " << result.paths.size() << '\n';
    for (const auto& path : result.paths) {
        std::cout << "    ";
        print_trail(path, names);
        std::cout << '\n';
    }
    for (const auto& cycle : result.cycles) {
        std::cout << "  ciclo apartado: ";
        print_trail(cycle, names);
        std::cout << '\n';
    }
}

}  // namespace

int main() {
    std::cout << "Un flujo de valor 2 con un ciclo, escrito a mano:\n";
    // s = 0, a = 1, b = 2, c = 3, d = 4, t = 5
    std::vector<Arc> with_cycle = {{0, 1}, {1, 2}, {2, 5}, {0, 3}, {3, 5}, {2, 4}, {4, 3}, {3, 2}};
    print_decomposition(decompose_flow(6, with_cycle, 0, 5), "sabcdt");

    // Un cuello de botella en c: s = 0, a = 1, b = 2, c = 3, d = 4, e = 5, t = 6
    const std::string names = "sabcdet";
    std::vector<Arc> arcs = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 5}, {4, 6}, {5, 6}};
    std::cout << "\nDirigido, sin compartir aristas:\n";
    print_decomposition(edge_disjoint_paths(7, arcs, 0, 6), names);
    std::cout << "  corte mínimo:";
    for (const Arc& arc : minimum_edge_cut(7, arcs, 0, 6)) {
        std::cout << ' ' << names[static_cast<std::size_t>(arc.from)] << "->" << names[static_cast<std::size_t>(arc.to)];
    }
    std::cout << "\n\nEl mismo grafo, sin compartir nodos:\n";
    print_decomposition(vertex_disjoint_paths(7, arcs, 0, 6), names);
    std::cout << "  separador mínimo:";
    for (int v : minimum_vertex_separator(7, arcs, 0, 6)) std::cout << ' ' << names[static_cast<std::size_t>(v)];
    std::cout << '\n';

    std::cout << "\nNo dirigido: el flujo de esta red usa una arista en las dos direcciones.\n";
    std::vector<Arc> edges = {{0, 4}, {6, 5}, {0, 2}, {2, 5}, {3, 6}, {1, 4}, {3, 1}, {0, 6}, {5, 4}};
    Decomposition undirected = undirected_edge_disjoint_paths(7, edges, 0, 6);
    std::cout << "  aristas canceladas: " << undirected.cancelled << '\n';
    print_decomposition(undirected, "sabcdet");

    std::cout << "\nCon una arista directa s -> t:\n";
    // s = 0, a = 1, b = 2, t = 3
    std::vector<Arc> adjacent = {{0, 3}, {0, 1}, {1, 3}, {0, 2}, {2, 3}};
    print_decomposition(vertex_disjoint_paths(4, adjacent, 0, 3), "sabt");
    SplitNetwork unlimited = split_network(4, adjacent, 0, 3, 5);
    std::cout << "  flujo si las aristas tienen capacidad \"sin límite\" (aquí, 5): "
              << unlimited.flow.edmonds_karp(unlimited.source, unlimited.sink) << '\n';
}