All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Public Member Functions | List of all members
NetworKit::UnionMaximumSpanningForest Class Reference

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

#include <UnionMaximumSpanningForest.h>

Public Member Functions

 UnionMaximumSpanningForest (const Graph &G)
 Initialize the union maximum-weight spanning forest algorithm, uses edge weights. More...
 
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. More...
 
virtual void run () override
 Execute the algorithm. More...
 
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. More...
 
bool inUMSF (node u, node v) const
 Checks if the edge (u, v) is part of any maximum-weight spanning forest. More...
 
bool inUMSF (edgeid eid) const
 Checks if the edge with the id eid is part of any maximum-weight spanning forest. More...
 
Graph getUMSF (bool move=false)
 Gets the union of all maximum-weight spanning forests as graph. More...
 
virtual bool isParallel () const override
 
virtual std::string toString () const override
 
- Public Member Functions inherited from NetworKit::Algorithm
 Algorithm ()
 Constructor to the algorithm base class. More...
 
virtual ~Algorithm ()=default
 Virtual default destructor. More...
 
bool hasFinished () const
 Indicates whether an algorithm has completed computation or not. More...
 
void assureFinished () const
 Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...
 

Additional Inherited Members

- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

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

Constructor & Destructor Documentation

NetworKit::UnionMaximumSpanningForest::UnionMaximumSpanningForest ( const Graph G)

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

Parameters
GThe input graph.
template<typename A >
NetworKit::UnionMaximumSpanningForest::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
GThe input graph.
attributeThe attribute to use, can be either of type edgeweight (double) or count (uint64), internally all values are handled as double.

Member Function Documentation

std::vector< bool > NetworKit::UnionMaximumSpanningForest::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
moveIf the attribute shall be moved out of the algorithm instance.
Returns
The vector with the boolean attribute for each edge.
Graph NetworKit::UnionMaximumSpanningForest::getUMSF ( bool  move = false)

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

Parameters
moveIf the graph shall be moved out of the algorithm instance.
Returns
The calculated union of all maximum-weight spanning forests.
bool NetworKit::UnionMaximumSpanningForest::inUMSF ( node  u,
node  v 
) const

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

Parameters
uThe first node of the edge to check
vThe second node of the edge to check
Returns
If the edge is part of any maximum-weight spanning forest.
bool NetworKit::UnionMaximumSpanningForest::inUMSF ( edgeid  eid) const

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

Parameters
eidThe id of the edge to check.
Returns
If the edge is part of any maximum-weight spanning forest.
bool NetworKit::UnionMaximumSpanningForest::isParallel ( ) const
overridevirtual
Returns
false - this algorithm is not parallelized.

Reimplemented from NetworKit::Algorithm.

void NetworKit::UnionMaximumSpanningForest::run ( )
overridevirtual

Execute the algorithm.

Implements NetworKit::Algorithm.

std::string NetworKit::UnionMaximumSpanningForest::toString ( ) const
overridevirtual
Returns
The name of the algorithm.

Reimplemented from NetworKit::Algorithm.


The documentation for this class was generated from the following files: