Class RandomMaximumSpanningForest¶

Defined in File RandomMaximumSpanningForest.hpp

Nested Relationships¶

Nested Types¶

Struct RandomMaximumSpanningForest::weightedEdge

Inheritance Relationships¶

Base Type¶

public NetworKit::Algorithm (Class Algorithm)

Class Documentation¶

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.

Parameters:: G – The input graph.

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

Initialize the random maximum-weight spanning forest algorithm using a vector of values, one for each edge. These values are used as edge weights. Each value corresponds to the edge with the given id.

Note: Since the mapping relies on edge ids, this variant only works, if the graph has edge ids. Call Graph::indexEdges() beforehand if necessary. The values are copied, the supplied vector is not stored in the RandomMaximumSpanningForest object. If the graph is changed, i.e. edges are removed, indexEdges should be called again to ensure that edge ids are contiguous. Otherwise edgeValues entries for the missing edges can be arbitrary.

Parameters:

G – The input graph.
edgeValues – The edge values 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> TLX_DEPRECATED(getAttribute(bool move = false))¶

DEPRECATED: this function will no longer be supported in later releases. Use getIndicator() instead.

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.

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

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

This indicator vector is only calculated and can thus only be requested if the supplied graph has edge ids.

Parameters:: move – If the indicator vector shall be moved out of the algorithm instance.
Returns:: The vector with the boolean indicator 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:

u – The first node of the edge to check
v – The second node of the edge to check

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.