Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Dijkstra Class Template Reference
[Path and Flow Algorithms]

#include <lemon/dijkstra.h>

Inheritance diagram for Dijkstra:

Inheritance graph
[legend]
List of all members.

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
Todo:
A compare object would be nice.

Definition at line 173 of file dijkstra.h.

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::PredNodeMap PredNodeMap
 The type of the map that stores the last but one nodes of the shortest paths.
typedef TR::ReachedMap ReachedMap
 The type of the map indicating if a node is reached.
typedef TR::DistMap DistMap
 The type of the map that stores the dists of the nodes.
typedef TR::Heap Heap
 The heap type used by the dijkstra algorithm.

Public Member Functions

 Dijkstra (const Graph &_G, const LengthMap &_length)
 Constructor.
 ~Dijkstra ()
 Destructor.
DijkstralengthMap (const LengthMap &m)
 Sets the length map.
DijkstrapredMap (PredMap &m)
 Sets the map storing the predecessor edges.
DijkstrapredNodeMap (PredNodeMap &m)
 Sets the map storing the predecessor nodes.
DijkstradistMap (DistMap &m)
 Sets the map storing the distances calculated by the algorithm.
Excetution control
The simplest way to execute the algorithm is to use one of the member functions called run(...).
It 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, Value dst=0)
 Adds a new source node.
void processNextNode ()
 Processes the next node in the priority heap.
bool emptyHeap ()
 Returns false if there are nodes to be processed in the priority heap.
int heapSize ()
 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 NM>
void start (const NM &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.

Value dist (Node v) const
 The distance of a node from the root.
Edge pred (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 DistMapdistMap () const
 Returns a reference to the NodeMap of distances.
const PredMappredMap () const
 Returns a reference to the shortest path tree map.
const PredNodeMappredNodeMap () const
 Returns a reference to the map of nodes of shortest paths.
bool reached (Node v)
 Checks if a node is reachable from the root.

Classes

class  DefDistMap
 Named parameter for setting DistMap type More...
class  DefPredMap
 Named parameter for setting PredMap type More...
class  DefPredNodeMap
 Named parameter for setting PredNodeMap type More...
class  DefReachedMap
 Named parameter for setting ReachedMap type More...
class  DefReachedMapToBeDefaultMap
 Named parameter for setting the ReachedMap type to be Graph::NodeMap<bool>. More...
class  UninitializedParameter
 Exception for uninitialized parameters. More...


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.

Definition at line 370 of file dijkstra.h.


Member Function Documentation

Dijkstra& lengthMap const LengthMap m  )  [inline]
 

Sets the length map.

Returns:
(*this)

Definition at line 392 of file dijkstra.h.

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)

Definition at line 405 of file dijkstra.h.

Dijkstra& predNodeMap PredNodeMap m  )  [inline]
 

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

Definition at line 422 of file dijkstra.h.

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)

Definition at line 439 of file dijkstra.h.

void init  )  [inline]
 

Initializes the internal data structures.

Todo:
_heap_map's type could also be in the traits class.

Todo:
*_reached is not set to false.

Definition at line 474 of file dijkstra.h.

void addSource Node  s,
Value  dst = 0
[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 longer then dst.

Definition at line 495 of file dijkstra.h.

void processNextNode  )  [inline]
 

Processes the next node in the priority heap.

Warning:
The priority heap must not be empty!

Definition at line 510 of file dijkstra.h.

bool emptyHeap  )  [inline]
 

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

Definition at line 542 of file dijkstra.h.

int heapSize  )  [inline]
 

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

Definition at line 547 of file dijkstra.h.

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

Definition at line 563 of file dijkstra.h.

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

Definition at line 582 of file dijkstra.h.

void start const NM &  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.

Definition at line 598 of file dijkstra.h.

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();

Definition at line 619 of file dijkstra.h.

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

Definition at line 638 of file dijkstra.h.

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.

Definition at line 661 of file dijkstra.h.

Edge pred 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(Node v).

Precondition:
run() must be called before using this function.
Todo:
predEdge could be a better name.

Definition at line 673 of file dijkstra.h.

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 pred(Node v).

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

Definition at line 683 of file dijkstra.h.

const DistMap& distMap  )  const [inline]
 

Returns a reference to the NodeMap of distances.

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

Definition at line 690 of file dijkstra.h.

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.

Definition at line 697 of file dijkstra.h.

const PredNodeMap& predNodeMap  )  const [inline]
 

Returns a reference to the NodeMap of the last but one nodes of the shortest path tree.

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

Definition at line 704 of file dijkstra.h.

bool reached Node  v  )  [inline]
 

Returns true if v is reachable from the root.

Warning:
If the algorithm is started from multiple nodes, this function may give false result for the source nodes.
Precondition:
run() must be called before using this function.

Definition at line 713 of file dijkstra.h.


The documentation for this class was generated from the following file:
Generated on Sat Mar 19 10:58:48 2005 for LEMON by  doxygen 1.4.1