Dijkstra Class Template Reference
[Path and Flow Algorithms]

#include <lemon/dijkstra.h>

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


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.

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.
DijkstradistMap (DistMap &m)
 Sets the map storing the distances calculated by the algorithm.
Dijkstraheap (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, Value dst=dijkstraZero< Value >())
 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>
void 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.

template<class P>
bool getPath (P &p, Node t)
 Copies the shortest path to t into p.
Value dist (Node v) const
 The 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 DistMapdistMap () const
 Returns a reference to the NodeMap of distances.
const PredMappredMap () 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.

Classes

struct  DefDistMap
 Named parameter for setting DistMap type More...
struct  DefHeap
struct  DefPredMap
 Named parameter for setting PredMap type More...
struct  DefProcessedMap
 Named parameter for setting ProcessedMap type More...
struct  DefProcessedMapToBeDefaultMap
 Named parameter for setting the ProcessedMap type to be Graph::NodeMap<bool>. More...
struct  DefStandardHeap
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.


Member Function Documentation

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 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,
Value  dst = dijkstraZero<Value>()
[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.

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

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

bool getPath P &  p,
Node  t
[inline]
 

This function copies the shortest path to t into p. If it t is a source itself or unreachable, then it does not alter p.

Returns:
Returns true if a path to t was actually copied to p, false otherwise.
See also:
DirPath

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.

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.


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