/*

TSP mit  boost 1.92.0  - Demograph,  4 Knoten (0-3), 6 Kanten mit Gewichtung für jede Kante.
Visual Studio  2026.
kein UNICODE
Boost unter Windows kompiliert (Visual Studio  2026,  Compiler  14.50)
Trotz  etlicher Makrofehlermeldungen, (Windows 7 wird angenommen für den weiteren Kompilierungsschritt), scheint boost 1.92.0 unter VS 2026, 18.9.0 zu funktionieren

boost lib und boost include einbinden.

Erstellen von boost library über diesen Befehl

bootstrap.bat,  b2 erzeugen.
Dann alle Komponenten für  Toolset msvc. Diese Parameter reichen aus.

b2 toolset=msvc --build-type=complete stage.

Kleines Fazit:  Die Vereinbarungen für boost,  graph, mittlerweile sehr komplex geworden.

*/

#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <iterator>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/metric_tsp_approx.hpp>

// Definition eines vollständig verbundenen, ungerichteten Graphen
typedef boost::adjacency_list<
    boost::vecS, boost::vecS, boost::undirectedS,
    boost::no_property, boost::property<boost::edge_weight_t, double>
> Graph;

typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;

int main(int argc, char *argv[]) {
    // Graph initialisieren
    const int num_vertices = 4;
    Graph g(num_vertices);
    auto weight_map = boost::get(boost::edge_weight, g);

    //  Kanten und Gewichte definieren
    std::vector<std::pair<std::pair<int, int>, double>> edges = {
        {{0, 1}, 10.0}, {{0, 2}, 15.0}, {{0, 3}, 20.0},
        {{1, 2}, 35.0}, {{1, 3}, 25.0},
        {{2, 3}, 30.0}
    };

    //  Graph befüllen
    for (const auto& edge_data : edges) {
        int u = edge_data.first.first;
        int v = edge_data.first.second;
        double weight = edge_data.second;

        Edge e;
        bool inserted = false;
        std::tie(e, inserted) = boost::add_edge(u, v, g);
        if (inserted) {
            weight_map[e] = weight;
        }
    }

    //  Ausgabestrukturen vorbereiten
    std::vector<Vertex> tsp_tour;
    auto vertex_id_map = boost::get(boost::vertex_index, g);

    // Diese Variable wird vom Visitor automatisch befüllt
    double gesamte_distanz = 0.0;

    // Erstellung des Visitors mitArgumentenliste
    auto tsp_visitor = boost::make_tsp_tour_len_visitor(
        g,
        std::back_inserter(tsp_tour),
        gesamte_distanz,
        weight_map
    );

    //  TSP Algorithmus ausführen
    boost::metric_tsp_approx(
        g,
        weight_map,
        vertex_id_map,
        tsp_visitor
    );

    //  Ergebnis ausgeben
    std::cout << "TSP Tour Reihenfolge: ";
    for (size_t i = 0; i < tsp_tour.size(); ++i) {
        std::cout << tsp_tour[i];
        if (i < tsp_tour.size() - 1) {
            std::cout << " -> ";
        }
    }

    // Die Variable 'gesamt_distanz' wurde von Boost berechnet
    std::cout << "\nTotal Tour Distanz: " << gesamte_distanz << std::endl;

    return 0;
}