Minimum Spanning Tree algorithms
[Algorithms]

Detailed Description

This group describes the algorithms for finding a minimum cost spanning tree in a graph


Classes
class	FredmanTarjan< GR, CM, TR >
	FredmanTarjan algorithm class to find a minimum spanning tree. More...
class	Kruskal< _UGraph, _CostMap, _Traits >
	Kruskal's algorithm to find a minimum cost tree of a graph. More...
class	MinCostArborescence< _Graph, _CostMap, _Traits >
	MinCostArborescence algorithm class. More...
class	Prim< GR, CM, TR >
	Prim algorithm class to find a minimum spanning tree. More...
Files
file	fredman_tarjan.h
	FredmanTarjan algorithm to compute minimum spanning forest.
file	kruskal.h
file	min_cost_arborescence.h
	Minimum Cost Arborescence algorithm.
file	prim.h
	Prim algorithm to compute minimum spanning tree.
Functions
template<class Graph , class CostMap , class TreeMap >
void	fredmanTarjan (const Graph &graph, const CostMap &cost, TreeMap &tree)
	Function type interface for FredmanTarjan algorithm.
template<class Graph , class In , class Out >
Value	kruskal (GR const &g, const In &in, Out &out)
	Kruskal's algorithm to find a minimum cost tree of a graph.
template<typename Graph , typename CostMap , typename ArborescenceMap >
CostMap::Value	minCostArborescence (const Graph &graph, const CostMap &cost, typename Graph::Node source, ArborescenceMap &arborescence)
	Function type interface for MinCostArborescence algorithm.
template<class Graph , class CostMap , class TreeMap >
CostMap::Value	prim (const Graph &graph, const CostMap &cost, TreeMap &tree)
	Function type interface for Prim algorithm.
template<class Graph , class CostMap , class TreeMap >
CostMap::Value	prim (const Graph &graph, const CostMap &cost)
	Function type interface for Prim algorithm.

Function Documentation

void lemon::fredmanTarjan	(	const Graph &	graph,
		const CostMap &	cost,
		TreeMap &	tree
	)			`[inline]`

Function type interface for FredmanTarjan algorithm.

Parameters:

	graph	the UGraph that the algorithm runs on
	cost	the CostMap of the edges

Return values:

tree

the EdgeMap that contains whether an edge is in the spanning tree or not

See also:: Prim

Value lemon::kruskal	(	GR const &	g,
		const In &	in,
		Out &	out
	)			`[inline]`

This function runs Kruskal's algorithm to find a minimum cost tree. Due to hard C++ hacking, it accepts various input and output types.

Parameters:

	g	The graph the algorithm runs on. It can be either directed or undirected. If the graph is directed, the algorithm consider it to be undirected by disregarding the direction of the edges.
	in	This object is used to describe the edge costs. It can be one of the following choices. An STL compatible 'Forward Container' with `std::pair<GR::UEdge,X>` or `std::pair<GR::Edge,X>` as its `value_type`, where `X` is the type of the costs. The pairs indicates the edges along with the assigned cost. They must be in a cost-ascending order. Any readable Edge map. The values of the map indicate the edge costs.

Return values:

out

Here we also have a choise.

It can be a writable bool edge map. After running the algorithm this will contain the found minimum cost spanning tree: the value of an edge will be set to true if it belongs to the tree, otherwise it will be set to false. The value of each edge will be set exactly once.
It can also be an iteraror of an STL Container with GR::UEdge or GR::Edge as its value_type. The algorithm copies the elements of the found tree into this sequence. For example, if we know that the spanning tree of the graph g has say 53 edges, then we can put its edges into an STL vector tree with a code like this.
```
      std::vector<Edge> tree(53);
      kruskal(g,cost,tree.begin());
```
Or if we don't know in advance the size of the tree, we can write this.
```
 std::vector<Edge> tree;
      kruskal(g,cost,std::back_inserter(tree)); 
```

Returns:: The total cost of the found tree.

Warning:: If kruskal runs on an be consistent of using the same Edge type for input and output.

CostMap::Value lemon::minCostArborescence	(	const Graph &	graph,
		const CostMap &	cost,
		typename Graph::Node	source,
		ArborescenceMap &	arborescence
	)			`[inline]`

Function type interface for MinCostArborescence algorithm.

Parameters:

	graph	The Graph that the algorithm runs on.
	cost	The CostMap of the edges.
	source	The source of the arborescence.

Return values:

arborescence

The bool EdgeMap which stores the arborescence.

Returns:: The cost of the arborescence.

See also:: MinCostArborescence

CostMap::Value lemon::prim	(	const Graph &	graph,
		const CostMap &	cost,
		TreeMap &	tree
	)			`[inline]`

Function type interface for Prim algorithm.

Parameters:

	graph	the UGraph that the algorithm runs on
	cost	the CostMap of the edges

Return values:

tree

the EdgeMap that contains whether an edge is in the spanning tree or not

Returns:: The total cost of the spanning tree

See also:: Prim

CostMap::Value lemon::prim	(	const Graph &	graph,
		const CostMap &	cost
	)			`[inline]`

Function type interface for Prim algorithm.

Parameters:

	graph	the UGraph that the algorithm runs on
	cost	the CostMap of the edges the spanning tree or not

Returns:: The total cost of the spanning tree

See also:: Prim

Minimum Spanning Tree algorithms [Algorithms]

Detailed Description

Classes

Files

Functions

Function Documentation

Minimum Spanning Tree algorithms
[Algorithms]