Open
Graph Drawing
Framework

 v. snapshot-2018-03-28
 

Minimum Spanning Trees

Provides algorithms for minimum spanning trees. More...

Methods for minimum spanning tree computation

template<typename T >
ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
 Computes a minimum spanning tree using Prim's algorithm. More...
 
template<typename T >
ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred, EdgeArray< bool > &isInTree)
 Computes a minimum spanning tree (MST) using Prim's algorithm. More...
 
template<typename T >
void ogdf::computeMinST (node s, const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred)
 Computes a minimum spanning tree (MST) using Prim's algorithm. More...
 
template<typename T >
ogdf::makeMinimumSpanningTree (Graph &G, const EdgeArray< T > &weight)
 Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm. More...
 
template<typename T >
void ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred)
 Computes a minimum spanning tree (MST) using Prim's algorithm. More...
 
template<typename T >
ogdf::computeMinST (node s, const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred, EdgeArray< bool > &isInTree)
 Computes a minimum spanning tree (MST) using Prim's algorithm. More...
 

Detailed Description

Provides algorithms for minimum spanning trees.

Function Documentation

◆ computeMinST() [1/5]

template<typename T >
T ogdf::computeMinST ( const Graph G,
const EdgeArray< T > &  weight,
EdgeArray< bool > &  isInTree 
)
inline

Computes a minimum spanning tree using Prim's algorithm.

Template Parameters
Tis the numeric type for edge weights.
Parameters
Gis the input graph.
weightis an edge array with the edge weights.
isInTreeis assigned the result, i.e. isInTree[e] is true iff edge e is in the computed MST.
Returns
the sum of the edge weights in the computed tree.

Definition at line 233 of file extended_graph_alg.h.

◆ computeMinST() [2/5]

template<typename T >
T ogdf::computeMinST ( const Graph G,
const EdgeArray< T > &  weight,
NodeArray< edge > &  pred,
EdgeArray< bool > &  isInTree 
)
inline

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
Tis the numeric type for edge weights.
Parameters
Gis the input graph.
weightis an edge array with the edge weights.
isInTreeis assigned the result, i.e. isInTree[e] is true iff edge e is in the computed MST.
predis assigned for each node the edge from its parent in the MST.
Returns
the sum of the edge weights in the computed tree.

Definition at line 251 of file extended_graph_alg.h.

◆ computeMinST() [3/5]

template<typename T >
void ogdf::computeMinST ( const Graph G,
const EdgeArray< T > &  weight,
NodeArray< edge > &  pred 
)
inline

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
Tis the numeric type for edge weights.
Parameters
Gis the input graph.
weightis an edge array with the edge weights.
predis assigned for each node the edge from its parent in the MST.

Definition at line 264 of file extended_graph_alg.h.

◆ computeMinST() [4/5]

template<typename T >
void ogdf::computeMinST ( node  s,
const Graph G,
const EdgeArray< T > &  weight,
NodeArray< edge > &  pred 
)

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
Tis the numeric type for edge weights.
Parameters
sis the start node for Prim's algorithm and will be the root of the MST.
Gis the input graph.
weightis an edge array with the edge weights.
predis assigned for each node the edge from its parent in the MST.

Definition at line 280 of file extended_graph_alg.h.

◆ computeMinST() [5/5]

template<typename T >
T ogdf::computeMinST ( node  s,
const Graph G,
const EdgeArray< T > &  weight,
NodeArray< edge > &  pred,
EdgeArray< bool > &  isInTree 
)

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
Tis the numeric type for edge weights.
Parameters
sis the start node for Prim's algorithm and will be the root of the MST.
Gis the input graph.
weightis an edge array with the edge weights.
predis assigned for each node the edge from its parent in the MST.
isInTreeis assigned the result, i.e. isInTree[e] is true iff edge e is in the computed MST.
Returns
the sum of the edge weights in the computed tree.

Definition at line 324 of file extended_graph_alg.h.

◆ makeMinimumSpanningTree()

template<typename T >
T ogdf::makeMinimumSpanningTree ( Graph G,
const EdgeArray< T > &  weight 
)

Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.

Template Parameters
Tis the numeric type for edge weights.
Parameters
Gis the input graph.
weightis an edge array with the edge weights.
Returns
the sum of the edge weights in the computed tree.

Definition at line 355 of file extended_graph_alg.h.