Dijkstra< GR, LM, TR > Class Template Reference
[Shortest Path algorithms]

Detailed Description

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

This class provides an efficient implementation of Dijkstra algorithm. The edge lengths are passed to the algorithm using a ReadMap, so it is easy to change it to any kind of length.

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

It is also possible to change the underlying priority heap.

Parameters:

	GR	The graph type the algorithm runs on. The default value is ListGraph. The value of GR is not used directly by Dijkstra, it is only passed to DijkstraDefaultTraits.
	LM	This read-only EdgeMap determines the lengths of the edges. It is read once for each edge, so the map may involve in relatively time consuming process to compute the edge length if it is necessary. The default map type is Graph::EdgeMap<int>. The value of LM is not used directly by Dijkstra, it is only passed to DijkstraDefaultTraits.
	TR	Traits class to set various data types used by the algorithm. The default traits class is DijkstraDefaultTraits<GR,LM>. See DijkstraDefaultTraits for the documentation of a Dijkstra traits class.

Author:: Jacint Szabo and Alpar Juttner

#include <lemon/dijkstra.h>

List of all members.

Classes

struct DefDistMap

struct DefHeap

struct DefOperationTraits

struct DefPredMap

struct DefProcessedMap

struct DefProcessedMapToBeDefaultMap

Named parameter for setting the ProcessedMap type to be Graph::NodeMap<bool>. More...

struct DefStandardHeap

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

class UninitializedParameter

Exception for uninitialized parameters. More...

Public Types

typedef TR::Graph Graph

The type of the underlying graph.

typedef Graph::Node Node

typedef Graph::NodeIt NodeIt

typedef Graph::Edge Edge

typedef Graph::OutEdgeIt OutEdgeIt

typedef TR::LengthMap::Value Value

The type of the length of the edges.

typedef TR::LengthMap LengthMap

The type of the map that stores the edge lengths.

typedef TR::PredMap PredMap

The type of the map that stores the last edges of the shortest paths.

typedef TR::ProcessedMap ProcessedMap

The type of the map indicating if a node is processed.

typedef TR::DistMap DistMap

The type of the map that stores the dists of the nodes.

typedef TR::HeapCrossRef HeapCrossRef

The cross reference type used for the current heap.

typedef TR::Heap Heap

The heap type used by the dijkstra algorithm.

typedef TR::OperationTraits OperationTraits

The operation traits.

Public Member Functions

Dijkstra (const Graph &_G, const LengthMap &_length)

Constructor.

~Dijkstra ()

Destructor.

Dijkstra & lengthMap (const LengthMap &m)

Sets the length map.

Dijkstra & predMap (PredMap &m)

Sets the map storing the predecessor edges.

Dijkstra & distMap (DistMap &m)

Sets the map storing the distances calculated by the algorithm.

Dijkstra & heap (Heap &hp, HeapCrossRef &cr)

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, Value dst=OperationTraits::zero())

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.

void start (Node dest)

Executes the algorithm until dest is reached.

template<class NodeBoolMap >

Node start (const NodeBoolMap &nm)

Executes the algorithm until a condition is met.

void run (Node s)

Runs Dijkstra algorithm from node s.

Value run (Node s, Node t)

Finds the shortest path between s and t.

Query Functions

The result of the Dijkstra algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.

Path path (Node t)

Gives back the shortest path.

Value dist (Node v) const

The distance of a node from the root.

Value currentDist (Node v) const

The current distance of a node from the root.

Edge predEdge (Node v) const

Returns the 'previous edge' of the shortest path tree.

Node predNode (Node v) const

Returns the 'previous node' of the shortest path tree.

const DistMap & distMap () const

Returns a reference to the NodeMap of distances.

const PredMap & predMap () const

Returns a reference to the shortest path tree map.

bool reached (Node v)

Checks if a node is reachable from the root.

bool processed (Node v)

Checks if a node is processed.

Private Member Functions

void create_maps ()

Creates the maps if necessary.

Private Attributes

const Graph * G

Pointer to the underlying graph.

const LengthMap * length

Pointer to the length map.

PredMap * _pred

Pointer to the map of predecessors edges.

bool local_pred

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

DistMap * _dist

Pointer to the map of distances.

bool local_dist

Indicates if _dist 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

Dijkstra	(	const Graph &	_G,
		const LengthMap &	_length
	)			`[inline]`

Parameters:

	_G	the graph the algorithm will run on.
	_length	the length map used by the algorithm.

Member Function Documentation

void create_maps ( ) [inline, private]

Todo:: Better memory allocation (instead of new).

Dijkstra& lengthMap ( const LengthMap & m ) [inline]

Sets the length map.

Returns:: (*this)

Dijkstra& 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)

Dijkstra& distMap ( DistMap & m ) [inline]

Sets the map storing the distances calculated by the 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)

Dijkstra& heap	(	Heap &	hp,
		HeapCrossRef &	cr
	)			`[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 heap and cross reference, of course.

Returns:: (*this)

void init ( ) [inline]

Initializes the internal data structures.

void addSource	(	Node	s,
		Value	dst = `OperationTraits::zero()`
	)			`[inline]`

Adds a new source node to the priority heap.

The optional second parameter is the initial distance of the node.

It checks if the node has already been added to the heap and it is pushed to the heap only if either it was not in the heap or the shortest path found till then is shorter than dst.

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 Dijkstra algorithm from the root node(s) in order to compute the shortest path to each node. The algorithm computes

The shortest path tree.
The distance of each node from the root(s).

void start ( Node dest ) [inline]

Executes the algorithm until dest is reached.

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

This method runs the Dijkstra algorithm from the root node(s) in order to compute the shortest path to dest. The algorithm computes

The shortest path to dest.
The distance of dest from the root(s).

Node 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.

Returns:: The reached node v with nm[v] true or INVALID if no such node was found.

void run ( Node s ) [inline]

This method runs the Dijkstra algorithm from a root node s in order to compute the shortest path to each node. The algorithm computes

The shortest path tree.
The distance of each node from the root.

Note:

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

         d.init();
         d.addSource(s);
         d.start();

Value run	(	Node	s,
		Node	t
	)			`[inline]`

Finds the shortest path between s and t.

Returns:: The length of the shortest s---t path if there exists one, 0 otherwise.

Note:

Apart from the return value, d.run(s) is just a shortcut of the following code.

         d.init();
         d.addSource(s);
         d.start(t);

Path path ( Node t ) [inline]

Gives back the shortest path.

Precondition:: The t should be reachable from the source.

Value dist ( Node v ) const [inline]

Returns the distance of a node from the root.

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

Warning:: If node v in unreachable from the root the return value of this funcion is undefined.

Value currentDist ( Node v ) const [inline]

Returns the current distance of a node from the root. It may be decreased in the following processes.

Precondition:: node should be reached but not processed

Edge predEdge ( Node v ) const [inline]

For a node v it returns the 'previous edge' of the shortest path tree, i.e. it returns the last edge of a shortest path from the root to v. It is INVALID if v is unreachable from the root or if v=s. The shortest path tree used here is equal to the shortest path tree used in predNode().

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

Node predNode ( Node v ) const [inline]

For a node v it returns the 'previous node' of the shortest path tree, i.e. it returns the last but one node from a shortest path from the root to /v. It is INVALID if v is unreachable from the root or if v=s. The shortest path tree used here is equal to the shortest path tree used in predEdge().

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

const DistMap& distMap ( ) const [inline]

Returns a reference to the NodeMap of distances.

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

const PredMap& predMap ( ) const [inline]

Returns a reference to the NodeMap of the edges of the shortest path tree.

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

bool reached ( Node v ) [inline]

Returns true if v is reachable from the root.

Warning:: The source nodes are inditated as unreached.

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

bool processed ( Node v ) [inline]

Returns true if v is processed, i.e. the shortest path to v has already found.

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


Classes
struct	DefDistMap
struct	DefHeap
struct	DefOperationTraits
struct	DefPredMap
struct	DefProcessedMap
struct	DefProcessedMapToBeDefaultMap
	Named parameter for setting the ProcessedMap type to be Graph::NodeMap<bool>. More...
struct	DefStandardHeap
	Named parameter for setting heap and cross reference type with automatic allocation More...
class	UninitializedParameter
	Exception for uninitialized parameters. More...
Public Types
typedef TR::Graph	Graph
	The type of the underlying graph.
typedef Graph::Node	Node

typedef Graph::NodeIt	NodeIt

typedef Graph::Edge	Edge

typedef Graph::OutEdgeIt	OutEdgeIt

typedef TR::LengthMap::Value	Value
	The type of the length of the edges.
typedef TR::LengthMap	LengthMap
	The type of the map that stores the edge lengths.
typedef TR::PredMap	PredMap
	The type of the map that stores the last edges of the shortest paths.
typedef TR::ProcessedMap	ProcessedMap
	The type of the map indicating if a node is processed.
typedef TR::DistMap	DistMap
	The type of the map that stores the dists of the nodes.
typedef TR::HeapCrossRef	HeapCrossRef
	The cross reference type used for the current heap.
typedef TR::Heap	Heap
	The heap type used by the dijkstra algorithm.
typedef TR::OperationTraits	OperationTraits
	The operation traits.
Public Member Functions
	Dijkstra (const Graph &_G, const LengthMap &_length)
	Constructor.
	~Dijkstra ()
	Destructor.
Dijkstra &	lengthMap (const LengthMap &m)
	Sets the length map.
Dijkstra &	predMap (PredMap &m)
	Sets the map storing the predecessor edges.
Dijkstra &	distMap (DistMap &m)
	Sets the map storing the distances calculated by the algorithm.
Dijkstra &	heap (Heap &hp, HeapCrossRef &cr)
	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, Value dst=OperationTraits::zero())
	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.
void	start (Node dest)
	Executes the algorithm until `dest` is reached.
template<class NodeBoolMap >
Node	start (const NodeBoolMap &nm)
	Executes the algorithm until a condition is met.
void	run (Node s)
	Runs Dijkstra algorithm from node `s`.
Value	run (Node s, Node t)
	Finds the shortest path between `s` and `t`.
Query Functions
The result of the Dijkstra algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called.
Path	path (Node t)
	Gives back the shortest path.
Value	dist (Node v) const
	The distance of a node from the root.
Value	currentDist (Node v) const
	The current distance of a node from the root.
Edge	predEdge (Node v) const
	Returns the 'previous edge' of the shortest path tree.
Node	predNode (Node v) const
	Returns the 'previous node' of the shortest path tree.
const DistMap &	distMap () const
	Returns a reference to the NodeMap of distances.
const PredMap &	predMap () const
	Returns a reference to the shortest path tree map.
bool	reached (Node v)
	Checks if a node is reachable from the root.
bool	processed (Node v)
	Checks if a node is processed.
Private Member Functions
void	create_maps ()
	Creates the maps if necessary.
Private Attributes
const Graph *	G
	Pointer to the underlying graph.
const LengthMap *	length
	Pointer to the length map.
PredMap *	_pred
	Pointer to the map of predecessors edges.
bool	local_pred
	Indicates if _pred is locally allocated (`true`) or not.
DistMap *	_dist
	Pointer to the map of distances.
bool	local_dist
	Indicates if _dist 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.

Dijkstra< GR, LM, TR > Class Template Reference [Shortest Path algorithms]

Detailed Description

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

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

Dijkstra< GR, LM, TR > Class Template Reference
[Shortest Path algorithms]

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