Class RandomMaximumSpanningForest

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

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> &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:
  • 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.