kruskal.h

Go to the documentation of this file.

#ifndef GRAPHLIB_ALGORITHMS_KRUSKAL_H
#define GRAPHLIB_ALGORITHMS_KRUSKAL_H
 
#include <algorithm>
#include <functional>
#include <map>
 
#include "GraphLib/internal/concepts.h"

 
namespace GraphLib {


template <Internal::valid_weighted_undirected_graph_type G>
G kruskal(const G& graph)
{
    using id_type = G::id_type;
    using edge_weight_type = typename G::edge_type::weight_type;
 
    G mst {};
 
    for (const auto& id : graph.get_nodes()) {
        mst.add_node_with_id(id, graph.get_node_data(id));
    }
 
    // Jede Node anfänglich eigener Parent, jede Node hat eigenes Set
    std::map<id_type, id_type> parent;
    for (const auto& id : graph.get_nodes()) {
        parent[id] = id;
    }
 
    // finde root/Ursprungsnode eines Sets und sorge dafür, dass jede Node direkt auf root zeigt
    // find_set(a): pfad a->b->c wird zu a->c, b-> c
    std::function<id_type(id_type)> find_set = [&parent, &find_set](id_type node) {
        if (parent[node] != node) {
            parent[node] = find_set(parent[node]);
        }
        return parent[node];
    };
 
    // Vereinigung zweier Sets, root eines Sets zeigt auf Root anderes Sets
    auto union_sets = [&find_set, &parent](id_type a, id_type b) { parent[find_set(a)] = find_set(b); };
 
    // Sammle alle Kanten
    std::vector<std::tuple<edge_weight_type, id_type, id_type>> edges;
    for (const auto& id : graph.get_nodes()) {
        for (const auto& neighbor : graph.get_neighbors(id)) {
            if (id < neighbor) { // Add each edge only once
                auto edge = graph.get_edge(id, neighbor);
                edges.emplace_back(edge.weight, id, neighbor);
            }
        }
    }
 
    // Sortiere Kanten nach Gewicht
    std::sort(edges.begin(), edges.end());
 
    // Arbeite Kanten nach Gewicht ab.
    for (const auto& [weight, u, v] : edges) {
        if (find_set(u) != find_set(v)) { // wenn nodes in versch. sets (um zyklenbildung zu vermeiden),
            mst.add_edge(u, v, weight);   // füge kante zu mst hinzu und merge sets
            union_sets(u, v);
        }
    }
 
    return mst;
}

} // namespace GraphLib
 
#endif