Kruskal< _UGraph, _CostMap, _Traits > Class Template Reference
[Minimum Spanning Tree algorithms]

---

Detailed Description

template<typename _UGraph, typename _CostMap, typename _Traits = KruskalDefaultTraits<_UGraph, _CostMap>>
class lemon::Kruskal< _UGraph, _CostMap, _Traits >

This class implements Kruskal's algorithm to find a minimum cost spanning tree. The

Parameters:

	_UGraph	Undirected graph type.
	_CostMap	Type of cost map.

#include <lemon/kruskal.h>

List of all members.

Classes
struct	DefRadixSort
	Named parameter for setting the sort function to radix sort More...
struct	DefSortCompare
struct	DefTreeMap
Public Member Functions
	Kruskal (const UGraph &_graph, const CostMap &_cost)
	Constructor.
	~Kruskal ()
	Destructor.
Kruskal &	treeMap (TreeMap &m)
	Sets the map storing the tree edges.
void	init ()
	Initialize the algorithm.
template<typename Iterator >
void	initPresorted (Iterator begin, Iterator end)
	Initialize the algorithm.
void	reinit ()
	Initialize the algorithm.
void	start ()
	Executes the algorithm.
UEdge	findNextTreeEdge ()
	Runs the prim algorithm until it find a new tree edge.
UEdge	processNextEdge ()
	Processes the next edge in the sequence.
bool	processEdge (const UEdge &edge)
	Processes an arbitrary edge.
bool	emptyQueue ()
	Returns false if there are edge to be processed in sequence.
UEdge	nextEdge () const
	Returns the next edge to be processed.
void	run ()
	Runs Kruskal algorithm.
const TreeMap &	treeMap () const
	Returns a reference to the tree edges map.
Value	treeValue () const
	Returns the total cost of the tree.
bool	tree (UEdge e) const
	Returns true when the given edge is tree edge.

---

Constructor & Destructor Documentation

Kruskal	(	const UGraph &	_graph,
		const CostMap &	_cost
	)			[inline]

Constructor of the algorithm.

~Kruskal

(

)

[inline]

Destructor

---

Member Function Documentation

Kruskal& treeMap

(

TreeMap &

m

)

[inline]

Sets the map storing the tree edges. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.

Returns:

*this

void init

(

)

[inline]

This member function initializes the unionfind data structure and sorts the edges into ascending order

void initPresorted	(	Iterator	begin,
		Iterator	end
	)			[inline]

This member function initializes the unionfind data structure and sets the edge order to the given sequence. The given sequence should be a valid STL range of undirected edges.

void reinit

(

)

[inline]

This member function initializes the unionfind data structure and sets the tree to empty. It does not change the order of the edges, it uses the order of the previous running.

void start

(

)

[inline]

Executes the algorithm.

Precondition:

init() must be called before using this function.

This method runs the Kruskal algorithm.

UEdge findNextTreeEdge

(

)

[inline]

Runs the prim algorithm until it find a new tree edge. If it does not next tree edge in the sequence it gives back INVALID.

UEdge processNextEdge

(

)

[inline]

Processes the next edge in the sequence.

Returns:

The prcocessed edge.

Warning:

The sequence must not be empty!

bool processEdge

(

const UEdge &

edge

)

[inline]

Processes the next edge in the sequence.

Returns:

True when the edge is a tree edge.

bool emptyQueue

(

)

[inline]

Returns false if there are nodes to be processed in the sequence

UEdge nextEdge

(

)

const [inline]

Returns the next edge to be processed

void run

(

)

[inline]

This method runs the Kruskal algorithm in order to compute the minimum spanning tree (or minimum spanning forest). The method also works on graphs that has more than one components. In this case it computes the minimum spanning forest.

const TreeMap& treeMap

(

)

const [inline]

Returns a reference to the TreeEdgeMap of the edges of the minimum spanning tree. The value of the map is true only if the edge is in the minimum spanning tree.

Value treeValue

(

)

const [inline]

Returns the total cost of the tree

bool tree

(

UEdge

e

)

const [inline]

Returns true when the given edge is tree edge