Minimum Spanning Trees

Provides algorithms for minimum spanning trees. More...

Methods for minimum spanning tree computation
template<typename T >
T	ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
	Computes a minimum spanning tree using Prim's algorithm.
template<typename T >
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.
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.
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<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<typename T >
T	ogdf::makeMinimumSpanningTree (Graph &G, const EdgeArray< T > &weight)
	Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.

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

T	is the numeric type for edge weights.

Parameters

G	is the input graph.
weight	is an edge array with the edge weights.
isInTree	is 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 236 of file extended_graph_alg.h.

computeMinST() [2/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

T	is the numeric type for edge weights.

Parameters

G	is the input graph.
weight	is an edge array with the edge weights.
pred	is assigned for each node the edge from its parent in the MST.

Definition at line 268 of file extended_graph_alg.h.

computeMinST() [3/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

T	is the numeric type for edge weights.

Parameters

G	is the input graph.
weight	is an edge array with the edge weights.
isInTree	is assigned the result, i.e. isInTree[e] is true iff edge e is in the computed MST.
pred	is 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 253 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

T	is the numeric type for edge weights.

Parameters

s	is the start node for Prim's algorithm and will be the root of the MST.
G	is the input graph.
weight	is an edge array with the edge weights.
pred	is assigned for each node the edge from its parent in the MST.

Definition at line 283 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

T	is the numeric type for edge weights.

Parameters

s	is the start node for Prim's algorithm and will be the root of the MST.
G	is the input graph.
weight	is an edge array with the edge weights.
pred	is assigned for each node the edge from its parent in the MST.
isInTree	is 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 326 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

T	is the numeric type for edge weights.

Parameters

G	is the input graph.
weight	is an edge array with the edge weights.

Returns

the sum of the edge weights in the computed tree.

Definition at line 362 of file extended_graph_alg.h.