Prim Class Template Reference
[Minimum Cost Spanning Tree Algorithms]

#include <lemon/prim.h>

List of all members.


Detailed Description

template<typename GR, typename LM, typename TR>
class lemon::Prim< GR, LM, TR >

This class provides an efficient implementation of Prim algorithm.

The running time is O(e*log n) where e is the number of edges and n is the number of nodes in the graph.

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.

It is also possible to change the underlying priority heap.

Parameters:
GR The graph type the algorithm runs on. The default value is ListUGraph. The value of GR is not used directly by Prim, it is only passed to PrimDefaultTraits.
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 Prim, it is only passed to PrimDefaultTraits.
TR Traits class to set various data types used by the algorithm. The default traits class is PrimDefaultTraits<GR,LM>. See PrimDefaultTraits for the documentation of a Prim 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::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::PredMap PredMap
 The type of the map that stores the last predecessor edges of the spanning tree.
typedef TR::TreeMap TreeMap
 Edges of the spanning tree.
typedef TR::ProcessedMap ProcessedMap
 The type of the map indicating if a node is processed.
typedef TR::HeapCrossRef HeapCrossRef
 The cross reference type used for the current heap.
typedef TR::Heap Heap
 The heap type used by the prim algorithm.

Public Member Functions

 Prim (const UGraph &_graph, const CostMap &_cost)
 Constructor.
 ~Prim ()
 Destructor.
PrimcostMap (const CostMap &m)
 Sets the cost map.
PrimpredMap (PredMap &m)
 Sets the map storing the predecessor edges.
PrimtreeMap (TreeMap &m)
 Sets the map storing the tree edges.
Primheap (Heap &heap, HeapCrossRef &crossRef)
 Sets the heap and the cross reference used by algorithm.
Execution control
The simplest way to execute the algorithm is to use one of the member functions called run(...).
If you need more control on the execution, first you must call init(), then you can add several source nodes with addSource(). Finally start() will perform the actual path computation.

void init ()
 Initializes the internal data structures.
void addSource (Node s)
 Adds a new source node.
Node processNextNode ()
 Processes the next node in the priority heap.
Node nextNode ()
 Next node to be processed.
bool emptyQueue ()
 Returns false if there are nodes to be processed in the priority heap.
int queueSize ()
 Returns the number of the nodes to be processed in the priority heap.
void start ()
 Executes the algorithm.
template<class NodeBoolMap>
void start (const NodeBoolMap &nm)
 Executes the algorithm until a condition is met.
void run ()
 Runs Prim algorithm.
void run (Node s)
 Runs Prim algorithm from node s.
Query Functions
The result of the Prim algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.

UEdge predEdge (Node v) const
 Returns the 'previous edge' of the minimum spanning tree.
Node predNode (Node v) const
 Returns the 'previous node' of the minimum spanning tree.
const PredMappredMap () const
 Returns a reference to the NodeMap of the edges of the minimum spanning tree.
const TreeMaptreeMap () const
 Returns a reference to the tree edges map.
template<class TreeMap>
void quickTreeEdges (TreeMap &tree, const typename TreeMap::Value &tree_edge_value=true) const
 Sets 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 reached (Node v)
 Checks if a node is reachable from the starting node.
bool processed (Node v)
 Checks if a node is processed.
bool tree (UEdge e)
 Checks if an edge is in the spanning tree or not.

Classes

struct  DefHeap
struct  DefPredMap
 Named parameter for setting PredMap type More...
struct  DefProcessedMap
 Named parameter for setting ProcessedMap type More...
struct  DefStandardHeap
struct  DefTreeMap
 Named parameter for setting TreeMap More...
class  UninitializedParameter
 Exception for uninitialized parameters. More...


Constructor & Destructor Documentation

Prim 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

Prim& costMap const CostMap m  )  [inline]
 

Sets the cost map.

Returns:
(*this)

Prim& predMap PredMap m  )  [inline]
 

Sets the map storing the predecessor 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)

Prim& 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 NullMap.

Returns:
(*this)

Prim& heap Heap heap,
HeapCrossRef crossRef
[inline]
 

Sets the heap and the cross reference used by algorithm. 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]
 

Initializes the internal data structures.

void addSource Node  s  )  [inline]
 

Adds a new source node to the priority heap.

It checks if the node has already been added to the heap and it is pushed to the heap only if it was not in the heap.

Node processNextNode  )  [inline]
 

Processes the next node in the priority heap.

Returns:
The processed node.
Warning:
The priority heap must not be empty!

Node nextNode  )  [inline]
 

Next node to be processed.

Returns:
The next node to be processed or INVALID if the priority heap is empty.

bool emptyQueue  )  [inline]
 

Returns false if there are nodes to be processed in the priority heap

int queueSize  )  [inline]
 

Returns the number of the nodes to be processed in the priority heap

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 Prim algorithm from the node(s) in order to compute the minimum spanning tree.

void start const NodeBoolMap &  nm  )  [inline]
 

Executes the algorithm until a condition is met.

Precondition:
init() must be called and at least one node should be added with addSource() before using this function.
Parameters:
nm must be a bool (or convertible) node map. The algorithm will stop when it reaches a node v with nm[v]==true.

void run  )  [inline]
 

This method runs the Prim 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.

void run Node  s  )  [inline]
 

This method runs the Prim algorithm from node s in order to compute the minimun spanning tree

Note:
d.run(s) is just a shortcut of the following code.
         d.init();
         d.addSource(s);
         d.start();

If the graph has more than one components, the method will compute the minimun spanning tree for only one component.

See run() if you want to compute the minimal spanning forest.

UEdge predEdge Node  v  )  const [inline]
 

For a node v it returns the 'previous edge' of the minimum spanning tree, i.e. it returns the edge from where v was reached. For a source node or an unreachable node it is INVALID. The minimum spanning tree used here is equal to the minimum spanning tree used in predNode().

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

Node predNode Node  v  )  const [inline]
 

tree used in predEdge().

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

const PredMap& predMap  )  const [inline]
 

Returns a reference to the NodeMap of the edges of the minimum spanning tree.

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

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.

Warning:
By default, the TreeEdgeMap is a NullMap.
If it is not set before the execution of the algorithm, use the treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the edges of the minimum spanning tree in O(n) time where n is the number of nodes in the graph.
Precondition:
run() or start() must be called before using this function.

void quickTreeEdges TreeMap tree,
const typename TreeMap::Value &  tree_edge_value = true
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, the other map values remain untouched.

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 reached Node  v  )  [inline]
 

Returns true if v is reachable from the starting node.

Warning:
The source nodes are inditated as unreached.
Precondition:
run() or start() must be called before using this function.

bool processed Node  v  )  [inline]
 

Returns true if v is processed, i.e. v is already connencted to the minimum spanning tree.

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:42:29 2006 for LEMON by  doxygen 1.4.6