Program Listing for File RandomMaximumSpanningForest.hpp¶

#ifndef NETWORKIT_GRAPH_RANDOM_MAXIMUM_SPANNING_FOREST_HPP_
#define NETWORKIT_GRAPH_RANDOM_MAXIMUM_SPANNING_FOREST_HPP_

#include <limits>

#include <networkit/auxiliary/Log.hpp>
#include <networkit/auxiliary/Random.hpp>
#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>
#include <networkit/structures/UnionFind.hpp>

namespace NetworKit {

class RandomMaximumSpanningForest : public Algorithm {
public:
    RandomMaximumSpanningForest(const Graph &G);

    template <typename A>
    RandomMaximumSpanningForest(const Graph &G, const std::vector<A> &attribute);

    void run() override;

    std::vector<bool> getAttribute(bool move = false);

    bool inMSF(node u, node v) const;

    bool inMSF(edgeid eid) const;

    Graph getMSF(bool move = false);

private:
    struct weightedEdge {
        double attribute;
        node u;
        node v;
        edgeid eid;
        index rand;

        bool operator>(const weightedEdge &other) const {
            return (attribute > other.attribute)
                   || (attribute == other.attribute
                       && (rand > other.rand
                           || (rand == other.rand
                               && (u > other.u || (u == other.u && v > other.v)))));
        };
        weightedEdge(node u, node v, double attribute, edgeid eid = 0)
            : attribute(attribute), u(u), v(v), eid(eid), rand(Aux::Random::integer()) {};
    };

    const Graph &G;
    std::vector<weightedEdge> weightedEdges;

    Graph msf;
    std::vector<bool> msfAttribute;

    bool hasWeightedEdges;
    bool hasMSF;
    bool hasAttribute;
};

template <typename A>
RandomMaximumSpanningForest::RandomMaximumSpanningForest(const Graph &G,
                                                         const std::vector<A> &attribute)
    : G(G), hasWeightedEdges(false), hasMSF(false), hasAttribute(false) {
    if (!G.hasEdgeIds()) {
        throw std::runtime_error("Error: Edges of G must be indexed for using edge attributes");
    }

    weightedEdges.reserve(G.numberOfEdges());

    G.forEdges(
        [&](node u, node v, edgeid eid) { weightedEdges.emplace_back(u, v, attribute[eid], eid); });

    INFO(weightedEdges.size(), " weighted edges saved");

    hasWeightedEdges = true;
}

} // namespace NetworKit

#endif // NETWORKIT_GRAPH_RANDOM_MAXIMUM_SPANNING_FOREST_HPP_