1.1 --- a/src/work/alpar/dijkstra.h Sun Feb 06 14:38:00 2005 +0000
1.2 +++ b/src/work/alpar/dijkstra.h Sun Feb 06 14:44:41 2005 +0000
1.3 @@ -158,7 +158,7 @@
1.4 ///a Dijkstra traits class.
1.5 ///
1.6 ///\author Jacint Szabo and Alpar Juttner
1.7 - ///\todo We need a typedef-names should be standardized. (-:
1.8 + ///\todo A compare object would be nice.
1.9
1.10 #ifdef DOXYGEN
1.11 template <typename GR,
1.12 @@ -237,11 +237,11 @@
1.13 ///The source node of the last execution.
1.14 Node source;
1.15
1.16 - ///Initializes the maps.
1.17 + ///Creates the maps if necessary.
1.18
1.19 ///\todo Error if \c G or are \c NULL. What about \c length?
1.20 ///\todo Better memory allocation (instead of new).
1.21 - void init_maps()
1.22 + void create_maps()
1.23 {
1.24 if(!_pred) {
1.25 local_pred = true;
1.26 @@ -263,11 +263,13 @@
1.27
1.28 public :
1.29
1.30 + ///\name Named template parameters
1.31 +
1.32 + ///@{
1.33 +
1.34 template <class T>
1.35 struct DefPredMapTraits : public Traits {
1.36 typedef T PredMap;
1.37 - ///\todo An exception should be thrown.
1.38 - ///
1.39 static PredMap *createPredMap(const Graph &G)
1.40 {
1.41 throw UninitializedParameter();
1.42 @@ -285,8 +287,6 @@
1.43 template <class T>
1.44 struct DefPredNodeMapTraits : public Traits {
1.45 typedef T PredNodeMap;
1.46 - ///\todo An exception should be thrown.
1.47 - ///
1.48 static PredNodeMap *createPredNodeMap(const Graph &G)
1.49 {
1.50 throw UninitializedParameter();
1.51 @@ -304,8 +304,6 @@
1.52 template <class T>
1.53 struct DefDistMapTraits : public Traits {
1.54 typedef T DistMap;
1.55 - ///\todo An exception should be thrown.
1.56 - ///
1.57 static DistMap *createDistMap(const Graph &G)
1.58 {
1.59 throw UninitializedParameter();
1.60 @@ -320,6 +318,50 @@
1.61 LengthMap,
1.62 DefDistMapTraits<T> > { };
1.63
1.64 + template <class T>
1.65 + struct DefReachedMapTraits : public Traits {
1.66 + typedef T ReachedMap;
1.67 + static ReachedMap *createReachedMap(const Graph &G)
1.68 + {
1.69 + throw UninitializedParameter();
1.70 + }
1.71 + };
1.72 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.73 +
1.74 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.75 + ///
1.76 + template <class T>
1.77 + class DefReachedMap : public Dijkstra< Graph,
1.78 + LengthMap,
1.79 + DefReachedMapTraits<T> > { };
1.80 +
1.81 + struct DefGraphReachedMapTraits : public Traits {
1.82 + typedef typename Graph::NodeMap<bool> ReachedMap;
1.83 + static ReachedMap *createReachedMap(const Graph &G)
1.84 + {
1.85 + return new ReachedMap(G);
1.86 + }
1.87 + };
1.88 + ///\brief \ref named-templ-param "Named parameter"
1.89 + ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
1.90 + ///
1.91 + ///\ref named-templ-param "Named parameter"
1.92 + ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
1.93 + ///If you don't set it explicitely, it will be automatically allocated.
1.94 + template <class T>
1.95 + class DefReachedMapToBeDefaultMap :
1.96 + public Dijkstra< Graph,
1.97 + LengthMap,
1.98 + DefGraphReachedMapTraits> { };
1.99 +
1.100 + ///@}
1.101 +
1.102 +
1.103 + private:
1.104 + typename Graph::template NodeMap<int> _heap_map;
1.105 + Heap _heap;
1.106 + public:
1.107 +
1.108 ///Constructor.
1.109
1.110 ///\param _G the graph the algorithm will run on.
1.111 @@ -329,7 +371,8 @@
1.112 _pred(NULL), local_pred(false),
1.113 pred_node(NULL), local_pred_node(false),
1.114 distance(NULL), local_distance(false),
1.115 - _reached(NULL), local_reached(false)
1.116 + _reached(NULL), local_reached(false),
1.117 + _heap_map(*G,-1),_heap(_heap_map)
1.118 { }
1.119
1.120 ///Destructor.
1.121 @@ -401,65 +444,147 @@
1.122 distance = &m;
1.123 return *this;
1.124 }
1.125 -
1.126 - ///Runs %Dijkstra algorithm from node \c s.
1.127
1.128 - ///This method runs the %Dijkstra algorithm from a root node \c s
1.129 - ///in order to
1.130 - ///compute the
1.131 - ///shortest path to each node. The algorithm computes
1.132 - ///- The shortest path tree.
1.133 - ///- The distance of each node from the root.
1.134 - ///\todo heap_map's type could also be in the traits class.
1.135 - void run(Node s) {
1.136 -
1.137 - init_maps();
1.138 -
1.139 - source = s;
1.140 + ///\name Excetution control
1.141 + ///The simplest way to execute the algorithm is to use
1.142 + ///\ref run().
1.143 + ///\n
1.144 + ///It you need more control on the execution,
1.145 + ///first you must call \ref init(), then you can add several source nodes
1.146 + ///with \ref addSource(). Finally \ref start() will perform the actual path
1.147 + ///computation.
1.148 +
1.149 + ///@{
1.150 +
1.151 + ///Initializes the internal data structures.
1.152 +
1.153 + ///Initializes the internal data structures.
1.154 + ///
1.155 + ///\todo _heap_map's type could also be in the traits class.
1.156 + void init()
1.157 + {
1.158 + create_maps();
1.159
1.160 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.161 _pred->set(u,INVALID);
1.162 pred_node->set(u,INVALID);
1.163 ///\todo *_reached is not set to false.
1.164 + _heap_map.set(u,Heap::PRE_HEAP);
1.165 }
1.166 + }
1.167 +
1.168 + ///Adds a new source node.
1.169 +
1.170 + ///Adds a new source node the the priority heap.
1.171 + ///It checks if the node has already been added to the heap.
1.172 + ///
1.173 + ///The optional second parameter is the initial distance of the node.
1.174 + ///
1.175 + ///\todo Do we really want to check it?
1.176 + void addSource(Node s,Value dst=0)
1.177 + {
1.178 + source = s;
1.179 + if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
1.180 + }
1.181 +
1.182 + void processNode()
1.183 + {
1.184 + Node v=_heap.top();
1.185 + _reached->set(v,true);
1.186 + Value oldvalue=_heap[v];
1.187 + _heap.pop();
1.188 + distance->set(v, oldvalue);
1.189
1.190 - typename Graph::template NodeMap<int> heap_map(*G,-1);
1.191 -
1.192 - Heap heap(heap_map);
1.193 -
1.194 - heap.push(s,0);
1.195 -
1.196 - while ( !heap.empty() ) {
1.197 -
1.198 - Node v=heap.top();
1.199 - _reached->set(v,true);
1.200 - Value oldvalue=heap[v];
1.201 - heap.pop();
1.202 - distance->set(v, oldvalue);
1.203 -
1.204 -
1.205 - for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
1.206 - Node w=G->target(e);
1.207 - switch(heap.state(w)) {
1.208 - case Heap::PRE_HEAP:
1.209 - heap.push(w,oldvalue+(*length)[e]);
1.210 + for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
1.211 + Node w=G->target(e);
1.212 + switch(_heap.state(w)) {
1.213 + case Heap::PRE_HEAP:
1.214 + _heap.push(w,oldvalue+(*length)[e]);
1.215 + _pred->set(w,e);
1.216 + pred_node->set(w,v);
1.217 + break;
1.218 + case Heap::IN_HEAP:
1.219 + if ( oldvalue+(*length)[e] < _heap[w] ) {
1.220 + _heap.decrease(w, oldvalue+(*length)[e]);
1.221 _pred->set(w,e);
1.222 pred_node->set(w,v);
1.223 - break;
1.224 - case Heap::IN_HEAP:
1.225 - if ( oldvalue+(*length)[e] < heap[w] ) {
1.226 - heap.decrease(w, oldvalue+(*length)[e]);
1.227 - _pred->set(w,e);
1.228 - pred_node->set(w,v);
1.229 - }
1.230 - break;
1.231 - case Heap::POST_HEAP:
1.232 - break;
1.233 }
1.234 + break;
1.235 + case Heap::POST_HEAP:
1.236 + break;
1.237 }
1.238 }
1.239 }
1.240 +
1.241 + ///Starts the execution of the algorithm.
1.242 +
1.243 + ///Starts the execution of the algorithm.
1.244 + ///
1.245 + ///\pre init() must be called before and at least one node should be added
1.246 + ///with addSource().
1.247 + ///
1.248 + ///This method runs the %Dijkstra algorithm from the root node(s)
1.249 + ///in order to
1.250 + ///compute the
1.251 + ///shortest path to each node. The algorithm computes
1.252 + ///- The shortest path tree.
1.253 + ///- The distance of each node from the root(s).
1.254 + ///
1.255 + void start()
1.256 + {
1.257 + while ( !_heap.empty() ) processNode();
1.258 + }
1.259
1.260 + ///Starts the execution of the algorithm until \c dest is reached.
1.261 +
1.262 + ///Starts the execution of the algorithm until \c dest is reached.
1.263 + ///
1.264 + ///\pre init() must be called before and at least one node should be added
1.265 + ///with addSource().
1.266 + ///
1.267 + ///This method runs the %Dijkstra algorithm from the root node(s)
1.268 + ///in order to
1.269 + ///compute the
1.270 + ///shortest path to \c dest. The algorithm computes
1.271 + ///- The shortest path to \c dest.
1.272 + ///- The distance of \c dest from the root(s).
1.273 + ///
1.274 + void start(Node dest)
1.275 + {
1.276 + while ( !_heap.empty() && _heap.top()!=dest) processNode();
1.277 + }
1.278 +
1.279 + ///Runs %Dijkstra algorithm from node \c s.
1.280 +
1.281 + ///This method runs the %Dijkstra algorithm from a root node \c s
1.282 + ///in order to
1.283 + ///compute the
1.284 + ///shortest path to each node. The algorithm computes
1.285 + ///- The shortest path tree.
1.286 + ///- The distance of each node from the root.
1.287 + ///
1.288 + ///\note d.run(s) is just a shortcut of the following code.
1.289 + ///\code
1.290 + /// d.init();
1.291 + /// d.addSource(s);
1.292 + /// d.start();
1.293 + ///\endcode
1.294 + void run(Node s) {
1.295 + init();
1.296 + addSource(s);
1.297 + start();
1.298 + }
1.299 +
1.300 + ///@}
1.301 +
1.302 + ///\name Query Functions
1.303 + ///The result of the %Dijkstra algorithm can be obtained using these
1.304 + ///functions.\n
1.305 + ///Before the use of these functions,
1.306 + ///either run() or start() must be called.
1.307 +
1.308 + ///@{
1.309 +
1.310 ///The distance of a node from the root.
1.311
1.312 ///Returns the distance of a node from the root.
1.313 @@ -513,11 +638,13 @@
1.314 ///Checks if a node is reachable from the root.
1.315
1.316 ///Returns \c true if \c v is reachable from the root.
1.317 - ///\note The root node is reported to be reached!
1.318 + ///\warning If the algorithm is started from multiple nodes,
1.319 + ///this function may give false result for the source nodes.
1.320 ///\pre \ref run() must be called before using this function.
1.321 ///
1.322 bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
1.323
1.324 + ///@}
1.325 };
1.326
1.327 /// Default traits used by \ref DijkstraWizard