FredmanTarjan< GR, CM, TR > Class Template Reference
[Minimum Spanning Tree algorithms]

---

Detailed Description

template<typename GR, typename CM, typename TR>
class lemon::FredmanTarjan< GR, CM, TR >

This class provides an efficient implementation of FredmanTarjan algorithm whitch is sometimes a bit quicker than the Prim algorithm on larger graphs. Due to the structure of the algorithm, it has less controll functions than Prim.

The running time is where and

The edge costs are passed to the algorithm using a ReadMap, so it is easy to change it to any kind of cost.

The type of the cost is determined by the Value of the cost map.

Parameters:

	GR	The graph type the algorithm runs on. The default value is ListUGraph. The value of GR is not used directly by FredmanTarjan, it is only passed to FredmanTarjanDefaultTraits.
	CM	This read-only UEdgeMap determines the costs of the edges. It is read once for each edge, so the map may involve in relatively time consuming process to compute the edge cost if it is necessary. The default map type is UGraph::UEdgeMap<int>. The value of CM is not used directly by FredmanTarjan, it is only passed to FredmanTarjanDefaultTraits.
	TR	Traits class to set various data types used by the algorithm. The default traits class is FredmanTarjanDefaultTraits<GR,CM>. See FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits class.

Author:

Balazs Attila Mihaly

#include <lemon/fredman_tarjan.h>

List of all members.

Classes
struct	DefTreeMap
class	UninitializedParameter
	Exception for uninitialized parameters. More...
Public Types
typedef TR::UGraph	UGraph
	The type of the underlying graph.
typedef UGraph::Node	Node
typedef UGraph::NodeIt	NodeIt
typedef UGraph::UEdge	UEdge
typedef UGraph::UEdgeIt	UEdgeIt
typedef UGraph::IncEdgeIt	IncEdgeIt
typedef TR::CostMap::Value	Value
	The type of the cost of the edges.
typedef TR::CostMap	CostMap
	The type of the map that stores the edge costs.
typedef TR::TreeMap	TreeMap
	Edges of the spanning tree.
Public Member Functions
	FredmanTarjan (const UGraph &_graph, const CostMap &_cost)
	Constructor.
	~FredmanTarjan ()
	Destructor.
FredmanTarjan &	costMap (const CostMap &m)
	Sets the cost map.
FredmanTarjan &	treeMap (TreeMap &m)
	Sets the map storing the tree edges.
Execution control
The simplest way to execute the algorithm is to use one of the member functions called run(...).
void	init ()
void	start ()
	Executes the algorithm.
void	run ()
	Runs FredmanTarjan algorithm.
Query Functions
The result of the FredmanTarjan algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called.
const TreeMap &	treeMap () const
	Returns a reference to the tree edges map.
template<class TreeMap >
void	treeEdges (TreeMap &tree, const typename TreeMap::Value &tree_edge_value=true, const typename TreeMap::Value &tree_default_value=false) const
	Sets the tree edges map.
bool	tree (UEdge e)
	Checks if an edge is in the spanning tree or not.
Private Member Functions
void	create_maps ()
	Creates the maps if necessary.
Private Attributes
const UGraph *	graph
	Pointer to the underlying graph.
const CostMap *	cost
	Pointer to the cost map.
TreeMap *	_tree
	Pointer to the map of tree edges.
bool	local_tree
	Indicates if _tree is locally allocated (true) or not.

---

Constructor & Destructor Documentation

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

Parameters:

	_graph	the graph the algorithm will run on.
	_cost	the cost map used by the algorithm.

---

Member Function Documentation

FredmanTarjan& costMap

(

const CostMap &

m

)

[inline]

Sets the cost map.

Returns:

(*this)

FredmanTarjan& 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. By default this is a BoolEdgeMap.

Returns:

(*this)

void init

(

)

[inline]

Initializes the internal data structures.

void start

(

)

[inline]

Executes the algorithm.

Precondition:

init() must be called and at least one node should be added with addSource() before using this function.

This method runs the FredmanTarjan algorithm from the node(s) in order to compute the minimum spanning tree.

void run

(

)

[inline]

This method runs the FredmanTarjan algorithm in order to compute the minimum spanning forest.

Note:

ft.run() is just a shortcut of the following code.

         ft.init();
         ft.start();

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.

Precondition:

run() or start() must be called before using this function.

void treeEdges	(	TreeMap &	tree,
		const typename TreeMap::Value &	tree_edge_value = true,
		const typename TreeMap::Value &	tree_default_value = false
	)			const [inline]

Sets the TreeMap of the edges of the minimum spanning tree. The map values belonging to the edges of the minimum spanning tree are set to tree_edge_value or true by default while the edge values not belonging to the minimum spanning tree are set to tree_default_value or false by default.

Precondition:

run() or start() must be called before using this function.

bool tree

(

UEdge

e

)

[inline]

Checks if an edge is in the spanning tree or not.

Parameters:

e

is the edge that will be checked

Returns:

true if e is in the spanning tree, false otherwise