FredmanTarjan Class Template Reference
[Minimum Cost Spanning Tree Algorithms]

#include <lemon/fredman_tarjan.h>

List of all members.


Detailed Description

template<typename GR, typename LM, typename TR>
class lemon::FredmanTarjan< GR, LM, 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 O(e*B(e,n)) where e is the number of edges, n is the number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n} ( log^(i+1) n = log(log^(i)) n )

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.
LM 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 LM 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,LM>. See FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits class.
Author:
Balazs Attila Mihaly


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.
FredmanTarjancostMap (const CostMap &m)
 Sets the cost map.
FredmanTarjantreeMap (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 ()
 Initializes the internal data structures.
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 TreeMaptreeMap () 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.

Classes

struct  DefTreeMap
 Named parameter for setting TreeMap More...
class  UninitializedParameter
 Exception for uninitialized parameters. More...


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


The documentation for this class was generated from the following file:
Generated on Fri Feb 3 18:41:29 2006 for LEMON by  doxygen 1.4.6