// Matching bipartito: la red, los caminos de aumento, los greedy que fallan y la capacidad que no se puede olvidar.
#include <iostream>
#include <string>
#include <vector>

#include "matching.h"

namespace {

std::string node_name(int v, int left, int sink) {
    if (v == 0) return "s";
    if (v == sink) return "t";
    if (v <= left) return "E" + std::to_string(v - 1);
    return "S" + std::to_string(v - left - 1);
}

void print_options(const Options& options) {
    for (std::size_t i = 0; i < options.size(); i++) {
        std::cout << "  E" << i << ":";
        for (int j : options[i]) std::cout << " S" << j;
        std::cout << '\n';
    }
}

void print_matching(const std::vector<int>& partner) {
    std::cout << assigned_count(partner) << " (";
    bool first = true;
    for (std::size_t i = 0; i < partner.size(); i++) {
        if (partner[i] < 0) continue;
        std::cout << (first ? "" : ", ") << "E" << i << "-S" << partner[i];
        first = false;
    }
    std::cout << ")\n";
}

void run_network(const Options& options, int right) {
    int left = static_cast<int>(options.size());
    MatchingNetwork net = matching_network(options, right);
    net.flow.keep_paths();
    long long value = net.flow.edmonds_karp(net.source, net.sink);
    for (const auto& path : net.flow.paths()) {
        std::cout << "  camino:";
        for (int v : path) std::cout << ' ' << node_name(v, left, net.sink);
        std::cout << '\n';
    }
    std::cout << "  flujo máximo: " << value << '\n';
    std::cout << "  matching: ";
    print_matching(read_matching(net, options));
}

void compare_greedy(const Options& options, int right) {
    std::vector<int> quota(static_cast<std::size_t>(right), 1);
    std::vector<int> copy = quota;
    std::cout << "  primera opción libre:        ";
    print_matching(first_fit(options, quota));
    std::cout << "  menos opciones primero:      ";
    print_matching(fewest_options_first(options, quota));
    std::cout << "  óptimo por fuerza bruta:     " << brute_assignment(options, copy) << '\n';
    std::cout << "  flujo:                       ";
    print_matching(max_matching(options, right));
}

}  // namespace

int main() {
    std::cout << "Una red de 3 por 3:\n";
    Options three = {{0, 1}, {0}, {1, 2}};
    print_options(three);
    run_network(three, 3);

    std::cout << "\nCada uno a su primera opción libre falla:\n";
    Options first = {{0, 1}, {0}};
    print_options(first);
    compare_greedy(first, 2);

    std::cout << "\nMenos opciones primero también falla:\n";
    Options fewest = {{0, 1}, {2, 0}, {2}};
    print_options(fewest);
    compare_greedy(fewest, 3);

    std::cout << "\nSin el límite en s -> estudiante, E0 cuenta dos veces:\n";
    Options greedy_student = {{0, 1}, {}};
    print_options(greedy_student);
    MatchingNetwork wide = matching_network(greedy_student, 2, 1000);
    std::cout << "  flujo con capacidad 1000 en s -> E: " << wide.flow.edmonds_karp(wide.source, wide.sink) << '\n';
    std::vector<int> quota = {1, 1};
    std::cout << "  matching máximo real:               " << brute_assignment(greedy_student, quota) << '\n';
}