Program Listing for File UnionMaximumSpanningForest.hpp¶

#ifndef NETWORKIT_GRAPH_UNION_MAXIMUM_SPANNING_FOREST_HPP_
#define NETWORKIT_GRAPH_UNION_MAXIMUM_SPANNING_FOREST_HPP_

#include <limits>

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

namespace NetworKit {

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

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

    void run() override;

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

    bool inUMSF(node u, node v) const;

    bool inUMSF(edgeid eid) const;

    Graph getUMSF(bool move = false);

private:
    struct weightedEdge {
        edgeweight attribute;
        node u;
        node v;
        edgeid eid;

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

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

    Graph umsf;
    std::vector<bool> umsfAttribute;

    bool hasWeightedEdges;
    bool hasUMSF;
    bool hasAttribute;
};

template <typename A>
UnionMaximumSpanningForest::UnionMaximumSpanningForest(const Graph &G,
                                                       const std::vector<A> &attribute)
    : G(&G), hasWeightedEdges(false), hasUMSF(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_UNION_MAXIMUM_SPANNING_FOREST_HPP_