# HG changeset patch # User alpar # Date 1107720056 0 # Node ID 47ef467ccf70815631ed1c5bdd7cd051f0354d42 # Parent 4e26fd7ffcdca1334ea8350e378e77eeedd4a5ac - PredNodeMap is a NullMap by default - Execution with stop condition - Find shortest path between two nodes diff -r 4e26fd7ffcdc -r 47ef467ccf70 src/work/alpar/dijkstra.h --- a/src/work/alpar/dijkstra.h Sun Feb 06 15:49:37 2005 +0000 +++ b/src/work/alpar/dijkstra.h Sun Feb 06 20:00:56 2005 +0000 @@ -85,14 +85,14 @@ ///nodes of the shortest paths. ///It must meet the \ref concept::WriteMap "WriteMap" concept. /// - typedef typename Graph::template NodeMap PredNodeMap; + typedef NullMap PredNodeMap; ///Instantiates a PredNodeMap. ///This function instantiates a \ref PredNodeMap. ///\param G is the graph, to which we would like to define the \ref PredNodeMap static PredNodeMap *createPredNodeMap(const GR &G) { - return new PredNodeMap(G); + return new PredNodeMap(); } ///The type of the map that stores whether a nodes is reached. @@ -222,13 +222,13 @@ ///Indicates if \ref _pred is locally allocated (\c true) or not. bool local_pred; ///Pointer to the map of predecessors nodes. - PredNodeMap *pred_node; - ///Indicates if \ref pred_node is locally allocated (\c true) or not. - bool local_pred_node; + PredNodeMap *_predNode; + ///Indicates if \ref _predNode is locally allocated (\c true) or not. + bool local_predNode; ///Pointer to the map of distances. - DistMap *distance; - ///Indicates if \ref distance is locally allocated (\c true) or not. - bool local_distance; + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not. + bool local_dist; ///Pointer to the map of reached status of the nodes. ReachedMap *_reached; ///Indicates if \ref _reached is locally allocated (\c true) or not. @@ -247,13 +247,13 @@ local_pred = true; _pred = Traits::createPredMap(*G); } - if(!pred_node) { - local_pred_node = true; - pred_node = Traits::createPredNodeMap(*G); + if(!_predNode) { + local_predNode = true; + _predNode = Traits::createPredNodeMap(*G); } - if(!distance) { - local_distance = true; - distance = Traits::createDistMap(*G); + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*G); } if(!_reached) { local_reached = true; @@ -369,8 +369,8 @@ Dijkstra(const Graph& _G, const LengthMap& _length) : G(&_G), length(&_length), _pred(NULL), local_pred(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false), + _predNode(NULL), local_predNode(false), + _dist(NULL), local_dist(false), _reached(NULL), local_reached(false), _heap_map(*G,-1),_heap(_heap_map) { } @@ -379,8 +379,8 @@ ~Dijkstra() { if(local_pred) delete _pred; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; + if(local_predNode) delete _predNode; + if(local_dist) delete _dist; if(local_reached) delete _reached; } @@ -420,11 +420,11 @@ ///\return (*this) Dijkstra &predNodeMap(PredNodeMap &m) { - if(local_pred_node) { - delete pred_node; - local_pred_node=false; + if(local_predNode) { + delete _predNode; + local_predNode=false; } - pred_node = &m; + _predNode = &m; return *this; } @@ -437,14 +437,23 @@ ///\return (*this) Dijkstra &distMap(DistMap &m) { - if(local_distance) { - delete distance; - local_distance=false; + if(local_dist) { + delete _dist; + local_dist=false; } - distance = &m; + _dist = &m; return *this; } + private: + void finalizeNodeData(Node v,Value dst) + { + _reached->set(v,true); + _dist->set(v, dst); + _predNode->set(v,G->source((*_pred)[v])); + } + + public: ///\name Excetution control ///The simplest way to execute the algorithm is to use ///\ref run(). @@ -467,7 +476,7 @@ for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { _pred->set(u,INVALID); - pred_node->set(u,INVALID); + _predNode->set(u,INVALID); ///\todo *_reached is not set to false. _heap_map.set(u,Heap::PRE_HEAP); } @@ -490,10 +499,9 @@ void processNode() { Node v=_heap.top(); - _reached->set(v,true); Value oldvalue=_heap[v]; _heap.pop(); - distance->set(v, oldvalue); + finalizeNodeData(v,oldvalue); for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { Node w=G->target(e); @@ -501,13 +509,13 @@ case Heap::PRE_HEAP: _heap.push(w,oldvalue+(*length)[e]); _pred->set(w,e); - pred_node->set(w,v); +// _predNode->set(w,v); break; case Heap::IN_HEAP: if ( oldvalue+(*length)[e] < _heap[w] ) { _heap.decrease(w, oldvalue+(*length)[e]); _pred->set(w,e); - pred_node->set(w,v); +// _predNode->set(w,v); } break; case Heap::POST_HEAP: @@ -516,12 +524,12 @@ } } - ///Starts the execution of the algorithm. + ///Executes the algorithm. - ///Starts the execution of the algorithm. + ///Executes the algorithm. /// - ///\pre init() must be called before and at least one node should be added - ///with addSource(). + ///\pre 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 @@ -535,12 +543,12 @@ while ( !_heap.empty() ) processNode(); } - ///Starts the execution of the algorithm until \c dest is reached. + ///Executes the algorithm until \c dest is reached. - ///Starts the execution of the algorithm until \c dest is reached. + ///Executes the algorithm until \c dest is reached. /// - ///\pre init() must be called before and at least one node should be added - ///with addSource(). + ///\pre 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 @@ -551,7 +559,24 @@ /// void start(Node dest) { - while ( !_heap.empty() && _heap.top()!=dest) processNode(); + while ( !_heap.empty() && _heap.top()!=dest ) processNode(); + if ( _heap.top()==dest ) finalizeNodeData(_heap.top()); + } + + ///Executes the algorithm until a condition is met. + + ///Executes the algorithm until a condition is met. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///\param nm must be a bool (or convertible) node map. The algorithm + ///will stop when it reaches a node \c v with nm[v]==true. + template + void start(const NM &nm) + { + while ( !_heap.empty() && !mn[_heap.top()] ) processNode(); + if ( !_heap.empty() ) finalizeNodeData(_heap.top()); } ///Runs %Dijkstra algorithm from node \c s. @@ -575,6 +600,26 @@ start(); } + ///Finds the shortest path between \c s and \c t. + + ///Finds the shortest path between \c s and \c t. + /// + ///\return 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. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(t); + ///\endcode + Value run(Node s,Node t) { + init(); + addSource(s); + start(t); + return (*_pred)[t]==INVALID?0:(*_dist)[t]; + } + ///@} ///\name Query Functions @@ -591,7 +636,7 @@ ///\pre \ref run() must be called before using this function. ///\warning If node \c v in unreachable from the root the return value ///of this funcion is undefined. - Value dist(Node v) const { return (*distance)[v]; } + Value dist(Node v) const { return (*_dist)[v]; } ///Returns the 'previous edge' of the shortest path tree. @@ -613,13 +658,14 @@ ///\c v=s. The shortest path tree used here is equal to the shortest path ///tree used in \ref pred(Node v). \pre \ref run() must be called before ///using this function. - Node predNode(Node v) const { return (*pred_node)[v]; } + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: + G->source((*_pred)[v]); } ///Returns a reference to the NodeMap of distances. ///Returns a reference to the NodeMap of distances. \pre \ref run() must ///be called before using this function. - const DistMap &distMap() const { return *distance;} + const DistMap &distMap() const { return *_dist;} ///Returns a reference to the shortest path tree map. @@ -633,7 +679,7 @@ ///Returns a reference to the NodeMap of the last but one nodes of the ///shortest path tree. ///\pre \ref run() must be called before using this function. - const PredNodeMap &predNodeMap() const { return *pred_node;} + const PredNodeMap &predNodeMap() const { return *_predNode;} ///Checks if a node is reachable from the root.