// El grafo de subproblemas, y el camino más largo en un DAG con pesos negativos y un nodo sin alcanzar.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "dag_dp.h"

namespace {

void show_subproblem_graphs() {
    std::cout << "Fibonacci, n = 5: quién lee a quién\n";
    for (int n = 2; n <= 5; n++) {
        std::cout << "  F(" << n - 1 << ") -> F(" << n << ")   F(" << n - 2 << ") -> F(" << n << ")\n";
    }
    std::cout << "  6 nodos, 8 aristas\n\n";

    const std::string a = "casa";
    const std::string b = "cosas";
    const WeightedDag g = edit_subproblem_dag(a, b);
    std::size_t arcs = 0;
    for (const auto& out : g) arcs += out.size();
    std::cout << "Distancia de edición, " << a << " -> " << b << ": " << g.size() << " nodos, " << arcs << " aristas\n";
    const LongestPaths paths = longest_paths(g, edit_node(0, 0, b.size()));
    const int target = edit_node(a.size(), b.size(), b.size());
    std::cout << "  distancia, como camino en ese DAG: " << -paths.length[target] << '\n';
    std::cout << "  el camino, en casillas (i, j):";
    for (int v : path_to(paths, target)) {
        std::cout << " (" << v / static_cast<int>(b.size() + 1) << "," << v % static_cast<int>(b.size() + 1) << ")";
    }
    std::cout << "\n\n";

    const std::vector<KnapsackObject> objects = {{2, 3}, {3, 4}, {4, 5}, {5, 8}};
    std::cout << "Mochila de la semana 7, capacidad 9, como camino más largo: " << knapsack_as_path(objects, 9) << "\n\n";
}

void show_longest_path() {
    // El nodo 0 no se alcanza desde el origen 1, y es la cola de una arista muy pesada.
    WeightedDag g(7);
    g[0] = {{2, 100}, {6, 1}};
    g[1] = {{2, 3}, {3, 5}};
    g[2] = {{4, -1}};
    g[3] = {{4, -4}, {5, 2}};
    g[4] = {{5, 6}};

    std::cout << "DAG:";
    for (int u = 0; u < 7; u++) {
        for (const Arc& arc : g[u]) std::cout << ' ' << u << "->" << arc.to << '(' << arc.weight << ')';
    }
    std::cout << "\nOrigen: 1\nOrden topológico:";
    for (int u : topological_order(g)) std::cout << ' ' << u;
    std::cout << "\n\n";

    const int source = 1;
    const LongestPaths r = longest_paths(g, source);
    const std::vector<long long> anywhere = longest_from_anywhere(g);
    std::cout << "nodo   L(v)  pred  todos en 0\n";
    for (int v = 0; v < 7; v++) {
        std::cout << std::setw(4) << v;
        if (r.reached[v]) {
            std::cout << std::setw(7) << r.length[v] << std::setw(6) << r.pred[v];
        } else {
            std::cout << std::setw(7) << "-inf" << std::setw(6) << "-";
        }
        std::cout << std::setw(12) << anywhere[v] << '\n';
    }

    std::cout << "\nCamino más largo de 1 a 5:";
    for (int v : path_to(r, 5)) std::cout << ' ' << v;
    std::cout << ", largo " << r.length[5] << '\n';

    long long total = 0;
    std::vector<int> walk;
    heaviest_arc_walk(g, source, 5, total, walk);
    std::cout << "Salir por la arista más pesada:";
    for (int v : walk) std::cout << ' ' << v;
    std::cout << ", largo " << total << '\n';
}

}  // namespace

int main() {
    show_subproblem_graphs();
    show_longest_path();
}