diff -r 2dea256cb988 -r 6a347310d4c2 src/work/alpar/dijkstra.h --- a/src/work/alpar/dijkstra.h Sun Feb 06 14:38:00 2005 +0000 +++ b/src/work/alpar/dijkstra.h Sun Feb 06 14:44:41 2005 +0000 @@ -158,7 +158,7 @@ ///a Dijkstra traits class. /// ///\author Jacint Szabo and Alpar Juttner - ///\todo We need a typedef-names should be standardized. (-: + ///\todo A compare object would be nice. #ifdef DOXYGEN template struct DefPredMapTraits : public Traits { typedef T PredMap; - ///\todo An exception should be thrown. - /// static PredMap *createPredMap(const Graph &G) { throw UninitializedParameter(); @@ -285,8 +287,6 @@ template struct DefPredNodeMapTraits : public Traits { typedef T PredNodeMap; - ///\todo An exception should be thrown. - /// static PredNodeMap *createPredNodeMap(const Graph &G) { throw UninitializedParameter(); @@ -304,8 +304,6 @@ template struct DefDistMapTraits : public Traits { typedef T DistMap; - ///\todo An exception should be thrown. - /// static DistMap *createDistMap(const Graph &G) { throw UninitializedParameter(); @@ -320,6 +318,50 @@ LengthMap, DefDistMapTraits > { }; + template + struct DefReachedMapTraits : public Traits { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + /// + template + class DefReachedMap : public Dijkstra< Graph, + LengthMap, + DefReachedMapTraits > { }; + + struct DefGraphReachedMapTraits : public Traits { + typedef typename Graph::NodeMap ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + return new ReachedMap(G); + } + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting the ReachedMap type to be Graph::NodeMap. + /// + ///\ref named-templ-param "Named parameter" + ///for setting the ReachedMap type to be Graph::NodeMap. + ///If you don't set it explicitely, it will be automatically allocated. + template + class DefReachedMapToBeDefaultMap : + public Dijkstra< Graph, + LengthMap, + DefGraphReachedMapTraits> { }; + + ///@} + + + private: + typename Graph::template NodeMap _heap_map; + Heap _heap; + public: + ///Constructor. ///\param _G the graph the algorithm will run on. @@ -329,7 +371,8 @@ _pred(NULL), local_pred(false), pred_node(NULL), local_pred_node(false), distance(NULL), local_distance(false), - _reached(NULL), local_reached(false) + _reached(NULL), local_reached(false), + _heap_map(*G,-1),_heap(_heap_map) { } ///Destructor. @@ -401,65 +444,147 @@ distance = &m; return *this; } - - ///Runs %Dijkstra algorithm from node \c s. - ///This method runs the %Dijkstra algorithm from a root node \c 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. - ///\todo heap_map's type could also be in the traits class. - void run(Node s) { - - init_maps(); - - source = s; + ///\name Excetution control + ///The simplest way to execute the algorithm is to use + ///\ref run(). + ///\n + ///It you need more control on the execution, + ///first you must call \ref init(), then you can add several source nodes + ///with \ref addSource(). Finally \ref start() will perform the actual path + ///computation. + + ///@{ + + ///Initializes the internal data structures. + + ///Initializes the internal data structures. + /// + ///\todo _heap_map's type could also be in the traits class. + void init() + { + create_maps(); for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { _pred->set(u,INVALID); pred_node->set(u,INVALID); ///\todo *_reached is not set to false. + _heap_map.set(u,Heap::PRE_HEAP); } + } + + ///Adds a new source node. + + ///Adds a new source node the the priority heap. + ///It checks if the node has already been added to the heap. + /// + ///The optional second parameter is the initial distance of the node. + /// + ///\todo Do we really want to check it? + void addSource(Node s,Value dst=0) + { + source = s; + if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); + } + + void processNode() + { + Node v=_heap.top(); + _reached->set(v,true); + Value oldvalue=_heap[v]; + _heap.pop(); + distance->set(v, oldvalue); - typename Graph::template NodeMap heap_map(*G,-1); - - Heap heap(heap_map); - - heap.push(s,0); - - while ( !heap.empty() ) { - - Node v=heap.top(); - _reached->set(v,true); - Value oldvalue=heap[v]; - heap.pop(); - distance->set(v, oldvalue); - - - for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { - Node w=G->target(e); - switch(heap.state(w)) { - case Heap::PRE_HEAP: - heap.push(w,oldvalue+(*length)[e]); + for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { + Node w=G->target(e); + switch(_heap.state(w)) { + case Heap::PRE_HEAP: + _heap.push(w,oldvalue+(*length)[e]); + _pred->set(w,e); + pred_node->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); - 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); - } - break; - case Heap::POST_HEAP: - break; } + break; + case Heap::POST_HEAP: + break; } } } + + ///Starts the execution of the algorithm. + + ///Starts the execution of the algorithm. + /// + ///\pre init() must be called before and at least one node should be added + ///with addSource(). + /// + ///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() + { + while ( !_heap.empty() ) processNode(); + } + ///Starts the execution of the algorithm until \c dest is reached. + + ///Starts the execution of the algorithm until \c dest is reached. + /// + ///\pre init() must be called before and at least one node should be added + ///with addSource(). + /// + ///This method runs the %Dijkstra algorithm from the root node(s) + ///in order to + ///compute the + ///shortest path to \c dest. The algorithm computes + ///- The shortest path to \c dest. + ///- The distance of \c dest from the root(s). + /// + void start(Node dest) + { + while ( !_heap.empty() && _heap.top()!=dest) processNode(); + } + + ///Runs %Dijkstra algorithm from node \c s. + + ///This method runs the %Dijkstra algorithm from a root node \c 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. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(); + ///\endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + ///@} + + ///\name Query Functions + ///The result of the %Dijkstra algorithm can be obtained using these + ///functions.\n + ///Before the use of these functions, + ///either run() or start() must be called. + + ///@{ + ///The distance of a node from the root. ///Returns the distance of a node from the root. @@ -513,11 +638,13 @@ ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the root. - ///\note The root node is reported to be reached! + ///\warning If the algorithm is started from multiple nodes, + ///this function may give false result for the source nodes. ///\pre \ref run() must be called before using this function. /// bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; } + ///@} }; /// Default traits used by \ref DijkstraWizard