Program Listing for File PrimMSF.hpp¶

/*  PrimMST.hpp
 *
 *  Created on: 29.03.2025
 *  Authors: Andreas Scharf (andreas.b.scharf@gmail.com)
 *
 */
#ifndef NETWORKIT_GRAPH_PRIM_MSF_HPP_
#define NETWORKIT_GRAPH_PRIM_MSF_HPP_
#include <networkit/Globals.hpp>
#include <networkit/graph/Graph.hpp>
#include <networkit/graph/SpanningForest.hpp>

namespace NetworKit {

class PrimMSF : public SpanningForest {
public:
    PrimMSF(const Graph &G) : SpanningForest(G) {
        if (G.isDirected()) {
            throw std::runtime_error("The graph is not an undirected graph.");
        }
    }

    void run() override;

    edgeweight getTotalWeight() const {
        assureFinished();
        if (G->isWeighted())
            return totalWeight;
        return static_cast<edgeweight>(forest.numberOfEdges());
    }

private:
    static constexpr edgeweight infiniteWeight = std::numeric_limits<edgeweight>::max();
    edgeweight totalWeight = 0;
};
} // namespace NetworKit
#endif // NETWORKIT_GRAPH_PRIM_MSF_HPP_