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

Detailed Description

template<typename GR, typename CM, typename TR>
class lemon::Prim< GR, CM, 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.
	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 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,CM>. See PrimDefaultTraits for the documentation of a Prim traits class.

Author:: Balazs Attila Mihaly

#include <lemon/prim.h>

List of all members.

Classes

struct DefHeap

struct DefPredMap

struct DefProcessedMap

struct DefStandardHeap

Named parameter for setting heap and cross reference type with automatic allocation More...

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::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)

~Prim ()

Destructor.

Prim & costMap (const CostMap &m)

Sets the cost map.

Prim & predMap (PredMap &m)

Sets the map storing the predecessor edges.

Prim & treeMap (TreeMap &m)

Sets the map storing the tree edges.

Prim & heap (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 ()

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 PredMap & predMap () const

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

const TreeMap & treeMap () const

Returns a reference to the tree edges map.

template<class TreeMap >

void quickTreeEdges (TreeMap &tree) const

Sets the tree edges map.

template<class TreeMap >

void treeEdges (TreeMap &tree) 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.

Value treeValue () const

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.

PredMap * _pred

Pointer to the map of predecessors edges.

bool local_pred

Indicates if _pred is locally allocated (true) or not.

TreeMap * _tree

Pointer to the map of tree edges.

bool local_tree

Indicates if _tree is locally allocated (true) or not.

ProcessedMap * _processed

Pointer to the map of processed status of the nodes.

bool local_processed

Indicates if _processed is locally allocated (true) or not.

HeapCrossRef * _heap_cross_ref

Pointer to the heap cross references.

bool local_heap_cross_ref

Indicates if _heap_cross_ref is locally allocated (true) or not.

Heap * _heap

Pointer to the heap.

bool local_heap

Indicates if _heap is locally allocated (true) or not.

Constructor & Destructor Documentation

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

Constructor.

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:

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

         p.init();
         p.addSource(s);
         p.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]

For a node v it returns the 'previous node' of the minimum spanning tree, i.e. it returns the node 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 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 [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 [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

Value treeValue ( ) const [inline]

Returns the value of the total cost of the spanning tree.


Classes
struct	DefHeap
struct	DefPredMap
struct	DefProcessedMap
struct	DefStandardHeap
	Named parameter for setting heap and cross reference type with automatic allocation More...
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::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)
	~Prim ()
	Destructor.
Prim &	costMap (const CostMap &m)
	Sets the cost map.
Prim &	predMap (PredMap &m)
	Sets the map storing the predecessor edges.
Prim &	treeMap (TreeMap &m)
	Sets the map storing the tree edges.
Prim &	heap (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 ()
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 PredMap &	predMap () const
	Returns a reference to the NodeMap of the edges of the minimum spanning tree.
const TreeMap &	treeMap () const
	Returns a reference to the tree edges map.
template<class TreeMap >
void	quickTreeEdges (TreeMap &tree) const
	Sets the tree edges map.
template<class TreeMap >
void	treeEdges (TreeMap &tree) 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.
Value	treeValue () const
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.
PredMap *	_pred
	Pointer to the map of predecessors edges.
bool	local_pred
	Indicates if _pred is locally allocated (`true`) or not.
TreeMap *	_tree
	Pointer to the map of tree edges.
bool	local_tree
	Indicates if _tree is locally allocated (`true`) or not.
ProcessedMap *	_processed
	Pointer to the map of processed status of the nodes.
bool	local_processed
	Indicates if _processed is locally allocated (`true`) or not.
HeapCrossRef *	_heap_cross_ref
	Pointer to the heap cross references.
bool	local_heap_cross_ref
	Indicates if _heap_cross_ref is locally allocated (`true`) or not.
Heap *	_heap
	Pointer to the heap.
bool	local_heap
	Indicates if _heap is locally allocated (`true`) or not.

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

Detailed Description

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

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

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

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