prim.h

Go to the documentation of this file.

#ifndef GRAPHLIB_ALGORITHMS_PRIM_H
#define GRAPHLIB_ALGORITHMS_PRIM_H
 
#include <set>
 
#include "GraphLib/internal/concepts.h"

 
namespace GraphLib {


template <Internal::valid_weighted_undirected_graph_type G>
G prim(const G& graph, typename G::id_type root)
{
    using id_type = G::id_type;
    using edge_type = G::edge_type;
    using edge_weight_type = typename G::edge_type::weight_type;
 
    if (!graph.node_exists(root)) {
        throw std::runtime_error("Root ID does not exist in Graph, cannot conduct Prim Algorithm");
    }
 
    G mst {};
 
    for (const auto& id : graph.get_nodes()) {
        mst.add_node_with_id(id, graph.get_node_data(id));
    }
 
    std::set<id_type> visited {root};
 
    while (visited.size() < graph.get_nodes().size()) {
        edge_type min_edge {{0}, edge_weight_type {}};
        id_type from_node;
        id_type to_node;
        bool found_edge = false;
 
        // schaue durch besuchte Knoten
        for (id_type current : visited) {
            // Prüfe alle ihre Nachbarn
            for (id_type neighbor : graph.get_neighbors(current)) {
                if (visited.contains(neighbor)) {
                    continue;
                }
 
                auto current_edge = graph.get_edge(current, neighbor);
                // Falls erste gefundene Kante oder Gewicht kleiner als bisheriges Minimum
                if (!found_edge || current_edge.weight < min_edge.weight) {
                    min_edge = current_edge;
                    from_node = current;
                    to_node = neighbor;
                    found_edge = true;
                }
            }
        }
 
        if (found_edge) {
            mst.add_edge(from_node, to_node, min_edge.weight);
            visited.insert(to_node);
        } else {
            throw std::runtime_error("Graph is not connected - cannot construct minimum spanning tree");
        }
    }
 
    return mst;
}

} // namespace GraphLib
 
#endif