Class UnionMaximumSpanningForest¶

Nested Relationships¶

class UnionMaximumSpanningForest : public NetworKit::Algorithm ¶

Union maximum-weight spanning forest algorithm, computes the union of all maximum-weight spanning forests using Kruskal’s algorithm.

Public Functions

UnionMaximumSpanningForest(const Graph &G)¶

Initialize the union maximum-weight spanning forest algorithm, uses edge weights.

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

Initialize the union maximum-weight spanning forest algorithm using an attribute as edge weight.

This copies the attribute values, the supplied attribute vector is not stored.

Parameters:

G – The input graph.
attribute – The attribute to use, can be either of type edgeweight (double) or count (uint64), internally all values are handled as double.

virtual void run() override¶: Execute the algorithm. The algorithm is not parallel.

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

Get a boolean attribute that indicates for each edge if it is part of any maximum-weight spanning forest.

This attribute is only calculated and can thus only be request if the supplied graph has edge ids.

Parameters:: move – If the attribute shall be moved out of the algorithm instance.
Returns:: The vector with the boolean attribute for each edge.

bool inUMSF(node u, node v) const¶

Checks if the edge (u, v) is part of any maximum-weight spanning forest.

Parameters:

Returns:

If the edge is part of any maximum-weight spanning forest.

bool inUMSF(edgeid eid) const¶

Checks if the edge with the id eid is part of any maximum-weight spanning forest.

Graph getUMSF(bool move = false)¶

Gets the union of all maximum-weight spanning forests as graph.

Parameters:: move – If the graph shall be moved out of the algorithm instance.
Returns:: The calculated union of all maximum-weight spanning forests.