Class RandomMaximumSpanningForest¶

Nested Relationships¶

class RandomMaximumSpanningForest : public NetworKit::Algorithm ¶

Computes a random maximum-weight spanning forest using Kruskal’s algorithm by randomizing the order of edges of the same weight.

Public Functions

RandomMaximumSpanningForest(const Graph &G)¶

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

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

Initialize the random 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 the calculated 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 inMSF(node u, node v) const¶

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

Parameters:

Returns:

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

bool inMSF(edgeid eid) const¶

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

Parameters:: eid – The id of the edge to check.
Returns:: If the edge is part of the calculated maximum-weight spanning forest.

Graph getMSF(bool move = false)¶

Gets the calculated maximum-weight spanning forest as graph.

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