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

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

#include <RandomMaximumSpanningForest.h>

Public Member Functions

 RandomMaximumSpanningForest (const Graph &G)
 Initialize the random maximum-weight spanning forest algorithm, uses edge weights. More...
 
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. 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 the calculated maximum-weight spanning forest. More...
 
bool inMSF (node u, node v) const
 Checks if the edge (u, v) is part of the calculated maximum-weight spanning forest. More...
 
bool inMSF (edgeid eid) const
 Checks if the edge with the id eid is part of the calculated maximum-weight spanning forest. More...
 
Graph getMSF (bool move=false)
 Gets the calculated maximum-weight spanning forest 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

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

Constructor & Destructor Documentation

NetworKit::RandomMaximumSpanningForest::RandomMaximumSpanningForest ( const Graph G)

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

Parameters
GThe input graph.
template<typename A >
NetworKit::RandomMaximumSpanningForest::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
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::RandomMaximumSpanningForest::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
moveIf the attribute shall be moved out of the algorithm instance.
Returns
The vector with the boolean attribute for each edge.
Graph NetworKit::RandomMaximumSpanningForest::getMSF ( bool  move = false)

Gets the calculated maximum-weight spanning forest as graph.

Parameters
moveIf the graph shall be moved out of the algorithm instance.
Returns
The calculated maximum-weight spanning forest.
bool NetworKit::RandomMaximumSpanningForest::inMSF ( node  u,
node  v 
) const

Checks if the edge (u, v) is part of the calculated 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 the calculated maximum-weight spanning forest.
bool NetworKit::RandomMaximumSpanningForest::inMSF ( edgeid  eid) const

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

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

Reimplemented from NetworKit::Algorithm.

void NetworKit::RandomMaximumSpanningForest::run ( )
overridevirtual

Execute the algorithm.

Implements NetworKit::Algorithm.

std::string NetworKit::RandomMaximumSpanningForest::toString ( ) const
overridevirtual
Returns
The name of this algorithm.

Reimplemented from NetworKit::Algorithm.


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