Class UnionMaximumSpanningForest¶

Defined in File UnionMaximumSpanningForest.hpp

Nested Relationships¶

Nested Types¶

Struct UnionMaximumSpanningForest::weightedEdge

Inheritance Relationships¶

Base Type¶

public NetworKit::Algorithm (Class Algorithm)

Class Documentation¶

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.

Parameters:: G – The input graph.

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

Initialize the union 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 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.

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 inUMSF(node u, node v) const¶

Checks if the edge (u, v) is part of any 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 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.

Parameters:: eid – The id of the edge to check.
Returns:: If the edge 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.