1 /* -*- C++ -*- |
|
2 * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_DIJKSTRA_H |
|
18 #define LEMON_DIJKSTRA_H |
|
19 |
|
20 ///\ingroup flowalgs |
|
21 ///\file |
|
22 ///\brief Dijkstra algorithm. |
|
23 /// |
|
24 ///\todo getPath() should be implemented! (also for BFS and DFS) |
|
25 |
|
26 #include <lemon/list_graph.h> |
|
27 #include <lemon/bin_heap.h> |
|
28 #include <lemon/invalid.h> |
|
29 #include <lemon/error.h> |
|
30 #include <lemon/maps.h> |
|
31 |
|
32 namespace lemon { |
|
33 |
|
34 |
|
35 |
|
36 ///Default traits class of Dijkstra class. |
|
37 |
|
38 ///Default traits class of Dijkstra class. |
|
39 ///\param GR Graph type. |
|
40 ///\param LM Type of length map. |
|
41 template<class GR, class LM> |
|
42 struct DijkstraDefaultTraits |
|
43 { |
|
44 ///The graph type the algorithm runs on. |
|
45 typedef GR Graph; |
|
46 ///The type of the map that stores the edge lengths. |
|
47 |
|
48 ///The type of the map that stores the edge lengths. |
|
49 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
|
50 typedef LM LengthMap; |
|
51 //The type of the length of the edges. |
|
52 typedef typename LM::Value Value; |
|
53 ///The heap type used by Dijkstra algorithm. |
|
54 |
|
55 ///The heap type used by Dijkstra algorithm. |
|
56 /// |
|
57 ///\sa BinHeap |
|
58 ///\sa Dijkstra |
|
59 typedef BinHeap<typename Graph::Node, |
|
60 typename LM::Value, |
|
61 typename GR::template NodeMap<int>, |
|
62 std::less<Value> > Heap; |
|
63 |
|
64 ///\brief The type of the map that stores the last |
|
65 ///edges of the shortest paths. |
|
66 /// |
|
67 ///The type of the map that stores the last |
|
68 ///edges of the shortest paths. |
|
69 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
70 /// |
|
71 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
|
72 ///Instantiates a PredMap. |
|
73 |
|
74 ///This function instantiates a \ref PredMap. |
|
75 ///\param G is the graph, to which we would like to define the PredMap. |
|
76 ///\todo The graph alone may be insufficient for the initialization |
|
77 static PredMap *createPredMap(const GR &G) |
|
78 { |
|
79 return new PredMap(G); |
|
80 } |
|
81 // ///\brief The type of the map that stores the last but one |
|
82 // ///nodes of the shortest paths. |
|
83 // /// |
|
84 // ///The type of the map that stores the last but one |
|
85 // ///nodes of the shortest paths. |
|
86 // ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
87 // /// |
|
88 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap; |
|
89 // ///Instantiates a PredNodeMap. |
|
90 |
|
91 // ///This function instantiates a \ref PredNodeMap. |
|
92 // ///\param G is the graph, to which |
|
93 // ///we would like to define the \ref PredNodeMap |
|
94 // static PredNodeMap *createPredNodeMap(const GR &G) |
|
95 // { |
|
96 // return new PredNodeMap(); |
|
97 // } |
|
98 |
|
99 ///The type of the map that stores whether a nodes is processed. |
|
100 |
|
101 ///The type of the map that stores whether a nodes is processed. |
|
102 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
103 ///By default it is a NullMap. |
|
104 ///\todo If it is set to a real map, |
|
105 ///Dijkstra::processed() should read this. |
|
106 ///\todo named parameter to set this type, function to read and write. |
|
107 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
|
108 ///Instantiates a ProcessedMap. |
|
109 |
|
110 ///This function instantiates a \ref ProcessedMap. |
|
111 ///\param G is the graph, to which |
|
112 ///we would like to define the \ref ProcessedMap |
|
113 static ProcessedMap *createProcessedMap(const GR &) |
|
114 { |
|
115 return new ProcessedMap(); |
|
116 } |
|
117 ///The type of the map that stores the dists of the nodes. |
|
118 |
|
119 ///The type of the map that stores the dists of the nodes. |
|
120 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
121 /// |
|
122 typedef typename Graph::template NodeMap<typename LM::Value> DistMap; |
|
123 ///Instantiates a DistMap. |
|
124 |
|
125 ///This function instantiates a \ref DistMap. |
|
126 ///\param G is the graph, to which we would like to define the \ref DistMap |
|
127 static DistMap *createDistMap(const GR &G) |
|
128 { |
|
129 return new DistMap(G); |
|
130 } |
|
131 }; |
|
132 |
|
133 ///%Dijkstra algorithm class. |
|
134 |
|
135 /// \ingroup flowalgs |
|
136 ///This class provides an efficient implementation of %Dijkstra algorithm. |
|
137 ///The edge lengths are passed to the algorithm using a |
|
138 ///\ref concept::ReadMap "ReadMap", |
|
139 ///so it is easy to change it to any kind of length. |
|
140 /// |
|
141 ///The type of the length is determined by the |
|
142 ///\ref concept::ReadMap::Value "Value" of the length map. |
|
143 /// |
|
144 ///It is also possible to change the underlying priority heap. |
|
145 /// |
|
146 ///\param GR The graph type the algorithm runs on. The default value |
|
147 ///is \ref ListGraph. The value of GR is not used directly by |
|
148 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. |
|
149 ///\param LM This read-only EdgeMap determines the lengths of the |
|
150 ///edges. It is read once for each edge, so the map may involve in |
|
151 ///relatively time consuming process to compute the edge length if |
|
152 ///it is necessary. The default map type is \ref |
|
153 ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value |
|
154 ///of LM is not used directly by Dijkstra, it is only passed to \ref |
|
155 ///DijkstraDefaultTraits. \param TR Traits class to set |
|
156 ///various data types used by the algorithm. The default traits |
|
157 ///class is \ref DijkstraDefaultTraits |
|
158 ///"DijkstraDefaultTraits<GR,LM>". See \ref |
|
159 ///DijkstraDefaultTraits for the documentation of a Dijkstra traits |
|
160 ///class. |
|
161 /// |
|
162 ///\author Jacint Szabo and Alpar Juttner |
|
163 ///\todo A compare object would be nice. |
|
164 |
|
165 #ifdef DOXYGEN |
|
166 template <typename GR, |
|
167 typename LM, |
|
168 typename TR> |
|
169 #else |
|
170 template <typename GR=ListGraph, |
|
171 typename LM=typename GR::template EdgeMap<int>, |
|
172 typename TR=DijkstraDefaultTraits<GR,LM> > |
|
173 #endif |
|
174 class Dijkstra { |
|
175 public: |
|
176 /** |
|
177 * \brief \ref Exception for uninitialized parameters. |
|
178 * |
|
179 * This error represents problems in the initialization |
|
180 * of the parameters of the algorithms. |
|
181 */ |
|
182 class UninitializedParameter : public lemon::UninitializedParameter { |
|
183 public: |
|
184 virtual const char* exceptionName() const { |
|
185 return "lemon::Dijkstra::UninitializedParameter"; |
|
186 } |
|
187 }; |
|
188 |
|
189 typedef TR Traits; |
|
190 ///The type of the underlying graph. |
|
191 typedef typename TR::Graph Graph; |
|
192 ///\e |
|
193 typedef typename Graph::Node Node; |
|
194 ///\e |
|
195 typedef typename Graph::NodeIt NodeIt; |
|
196 ///\e |
|
197 typedef typename Graph::Edge Edge; |
|
198 ///\e |
|
199 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
200 |
|
201 ///The type of the length of the edges. |
|
202 typedef typename TR::LengthMap::Value Value; |
|
203 ///The type of the map that stores the edge lengths. |
|
204 typedef typename TR::LengthMap LengthMap; |
|
205 ///\brief The type of the map that stores the last |
|
206 ///edges of the shortest paths. |
|
207 typedef typename TR::PredMap PredMap; |
|
208 // ///\brief The type of the map that stores the last but one |
|
209 // ///nodes of the shortest paths. |
|
210 // typedef typename TR::PredNodeMap PredNodeMap; |
|
211 ///The type of the map indicating if a node is processed. |
|
212 typedef typename TR::ProcessedMap ProcessedMap; |
|
213 ///The type of the map that stores the dists of the nodes. |
|
214 typedef typename TR::DistMap DistMap; |
|
215 ///The heap type used by the dijkstra algorithm. |
|
216 typedef typename TR::Heap Heap; |
|
217 private: |
|
218 /// Pointer to the underlying graph. |
|
219 const Graph *G; |
|
220 /// Pointer to the length map |
|
221 const LengthMap *length; |
|
222 ///Pointer to the map of predecessors edges. |
|
223 PredMap *_pred; |
|
224 ///Indicates if \ref _pred is locally allocated (\c true) or not. |
|
225 bool local_pred; |
|
226 // ///Pointer to the map of predecessors nodes. |
|
227 // PredNodeMap *_predNode; |
|
228 // ///Indicates if \ref _predNode is locally allocated (\c true) or not. |
|
229 // bool local_predNode; |
|
230 ///Pointer to the map of distances. |
|
231 DistMap *_dist; |
|
232 ///Indicates if \ref _dist is locally allocated (\c true) or not. |
|
233 bool local_dist; |
|
234 ///Pointer to the map of processed status of the nodes. |
|
235 ProcessedMap *_processed; |
|
236 ///Indicates if \ref _processed is locally allocated (\c true) or not. |
|
237 bool local_processed; |
|
238 |
|
239 // ///The source node of the last execution. |
|
240 // Node source; |
|
241 |
|
242 ///Creates the maps if necessary. |
|
243 |
|
244 ///\todo Error if \c G or are \c NULL. What about \c length? |
|
245 ///\todo Better memory allocation (instead of new). |
|
246 void create_maps() |
|
247 { |
|
248 if(!_pred) { |
|
249 local_pred = true; |
|
250 _pred = Traits::createPredMap(*G); |
|
251 } |
|
252 // if(!_predNode) { |
|
253 // local_predNode = true; |
|
254 // _predNode = Traits::createPredNodeMap(*G); |
|
255 // } |
|
256 if(!_dist) { |
|
257 local_dist = true; |
|
258 _dist = Traits::createDistMap(*G); |
|
259 } |
|
260 if(!_processed) { |
|
261 local_processed = true; |
|
262 _processed = Traits::createProcessedMap(*G); |
|
263 } |
|
264 } |
|
265 |
|
266 public : |
|
267 |
|
268 ///\name Named template parameters |
|
269 |
|
270 ///@{ |
|
271 |
|
272 template <class T> |
|
273 struct DefPredMapTraits : public Traits { |
|
274 typedef T PredMap; |
|
275 static PredMap *createPredMap(const Graph &G) |
|
276 { |
|
277 throw UninitializedParameter(); |
|
278 } |
|
279 }; |
|
280 ///\ref named-templ-param "Named parameter" for setting PredMap type |
|
281 |
|
282 ///\ref named-templ-param "Named parameter" for setting PredMap type |
|
283 /// |
|
284 template <class T> |
|
285 class DefPredMap : public Dijkstra< Graph, |
|
286 LengthMap, |
|
287 DefPredMapTraits<T> > { }; |
|
288 |
|
289 // template <class T> |
|
290 // struct DefPredNodeMapTraits : public Traits { |
|
291 // typedef T PredNodeMap; |
|
292 // static PredNodeMap *createPredNodeMap(const Graph &G) |
|
293 // { |
|
294 // throw UninitializedParameter(); |
|
295 // } |
|
296 // }; |
|
297 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type |
|
298 |
|
299 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type |
|
300 // /// |
|
301 // template <class T> |
|
302 // class DefPredNodeMap : public Dijkstra< Graph, |
|
303 // LengthMap, |
|
304 // DefPredNodeMapTraits<T> > { }; |
|
305 |
|
306 template <class T> |
|
307 struct DefDistMapTraits : public Traits { |
|
308 typedef T DistMap; |
|
309 static DistMap *createDistMap(const Graph &G) |
|
310 { |
|
311 throw UninitializedParameter(); |
|
312 } |
|
313 }; |
|
314 ///\ref named-templ-param "Named parameter" for setting DistMap type |
|
315 |
|
316 ///\ref named-templ-param "Named parameter" for setting DistMap type |
|
317 /// |
|
318 template <class T> |
|
319 class DefDistMap : public Dijkstra< Graph, |
|
320 LengthMap, |
|
321 DefDistMapTraits<T> > { }; |
|
322 |
|
323 template <class T> |
|
324 struct DefProcessedMapTraits : public Traits { |
|
325 typedef T ProcessedMap; |
|
326 static ProcessedMap *createProcessedMap(const Graph &G) |
|
327 { |
|
328 throw UninitializedParameter(); |
|
329 } |
|
330 }; |
|
331 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
|
332 |
|
333 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
|
334 /// |
|
335 template <class T> |
|
336 class DefProcessedMap : public Dijkstra< Graph, |
|
337 LengthMap, |
|
338 DefProcessedMapTraits<T> > { }; |
|
339 |
|
340 struct DefGraphProcessedMapTraits : public Traits { |
|
341 typedef typename Graph::template NodeMap<bool> ProcessedMap; |
|
342 static ProcessedMap *createProcessedMap(const Graph &G) |
|
343 { |
|
344 return new ProcessedMap(G); |
|
345 } |
|
346 }; |
|
347 ///\brief \ref named-templ-param "Named parameter" |
|
348 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
|
349 /// |
|
350 ///\ref named-templ-param "Named parameter" |
|
351 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
|
352 ///If you don't set it explicitely, it will be automatically allocated. |
|
353 template <class T> |
|
354 class DefProcessedMapToBeDefaultMap : |
|
355 public Dijkstra< Graph, |
|
356 LengthMap, |
|
357 DefGraphProcessedMapTraits> { }; |
|
358 |
|
359 ///@} |
|
360 |
|
361 |
|
362 private: |
|
363 typename Graph::template NodeMap<int> _heap_map; |
|
364 Heap _heap; |
|
365 public: |
|
366 |
|
367 ///Constructor. |
|
368 |
|
369 ///\param _G the graph the algorithm will run on. |
|
370 ///\param _length the length map used by the algorithm. |
|
371 Dijkstra(const Graph& _G, const LengthMap& _length) : |
|
372 G(&_G), length(&_length), |
|
373 _pred(NULL), local_pred(false), |
|
374 // _predNode(NULL), local_predNode(false), |
|
375 _dist(NULL), local_dist(false), |
|
376 _processed(NULL), local_processed(false), |
|
377 _heap_map(*G,-1),_heap(_heap_map) |
|
378 { } |
|
379 |
|
380 ///Destructor. |
|
381 ~Dijkstra() |
|
382 { |
|
383 if(local_pred) delete _pred; |
|
384 // if(local_predNode) delete _predNode; |
|
385 if(local_dist) delete _dist; |
|
386 if(local_processed) delete _processed; |
|
387 } |
|
388 |
|
389 ///Sets the length map. |
|
390 |
|
391 ///Sets the length map. |
|
392 ///\return <tt> (*this) </tt> |
|
393 Dijkstra &lengthMap(const LengthMap &m) |
|
394 { |
|
395 length = &m; |
|
396 return *this; |
|
397 } |
|
398 |
|
399 ///Sets the map storing the predecessor edges. |
|
400 |
|
401 ///Sets the map storing the predecessor edges. |
|
402 ///If you don't use this function before calling \ref run(), |
|
403 ///it will allocate one. The destuctor deallocates this |
|
404 ///automatically allocated map, of course. |
|
405 ///\return <tt> (*this) </tt> |
|
406 Dijkstra &predMap(PredMap &m) |
|
407 { |
|
408 if(local_pred) { |
|
409 delete _pred; |
|
410 local_pred=false; |
|
411 } |
|
412 _pred = &m; |
|
413 return *this; |
|
414 } |
|
415 |
|
416 // ///Sets the map storing the predecessor nodes. |
|
417 |
|
418 // ///Sets the map storing the predecessor nodes. |
|
419 // ///If you don't use this function before calling \ref run(), |
|
420 // ///it will allocate one. The destuctor deallocates this |
|
421 // ///automatically allocated map, of course. |
|
422 // ///\return <tt> (*this) </tt> |
|
423 // Dijkstra &predNodeMap(PredNodeMap &m) |
|
424 // { |
|
425 // if(local_predNode) { |
|
426 // delete _predNode; |
|
427 // local_predNode=false; |
|
428 // } |
|
429 // _predNode = &m; |
|
430 // return *this; |
|
431 // } |
|
432 |
|
433 ///Sets the map storing the distances calculated by the algorithm. |
|
434 |
|
435 ///Sets the map storing the distances calculated by the algorithm. |
|
436 ///If you don't use this function before calling \ref run(), |
|
437 ///it will allocate one. The destuctor deallocates this |
|
438 ///automatically allocated map, of course. |
|
439 ///\return <tt> (*this) </tt> |
|
440 Dijkstra &distMap(DistMap &m) |
|
441 { |
|
442 if(local_dist) { |
|
443 delete _dist; |
|
444 local_dist=false; |
|
445 } |
|
446 _dist = &m; |
|
447 return *this; |
|
448 } |
|
449 |
|
450 private: |
|
451 void finalizeNodeData(Node v,Value dst) |
|
452 { |
|
453 _processed->set(v,true); |
|
454 _dist->set(v, dst); |
|
455 // if((*_pred)[v]!=INVALID) |
|
456 // _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do? |
|
457 } |
|
458 |
|
459 public: |
|
460 ///\name Execution control |
|
461 ///The simplest way to execute the algorithm is to use |
|
462 ///one of the member functions called \c run(...). |
|
463 ///\n |
|
464 ///If you need more control on the execution, |
|
465 ///first you must call \ref init(), then you can add several source nodes |
|
466 ///with \ref addSource(). |
|
467 ///Finally \ref start() will perform the actual path |
|
468 ///computation. |
|
469 |
|
470 ///@{ |
|
471 |
|
472 ///Initializes the internal data structures. |
|
473 |
|
474 ///Initializes the internal data structures. |
|
475 /// |
|
476 ///\todo _heap_map's type could also be in the traits class. |
|
477 ///\todo The heaps should be able to make themselves empty directly. |
|
478 void init() |
|
479 { |
|
480 create_maps(); |
|
481 while(!_heap.empty()) _heap.pop(); |
|
482 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
|
483 _pred->set(u,INVALID); |
|
484 // _predNode->set(u,INVALID); |
|
485 _processed->set(u,false); |
|
486 _heap_map.set(u,Heap::PRE_HEAP); |
|
487 } |
|
488 } |
|
489 |
|
490 ///Adds a new source node. |
|
491 |
|
492 ///Adds a new source node to the priority heap. |
|
493 /// |
|
494 ///The optional second parameter is the initial distance of the node. |
|
495 /// |
|
496 ///It checks if the node has already been added to the heap and |
|
497 ///It is pushed to the heap only if either it was not in the heap |
|
498 ///or the shortest path found till then is longer then \c dst. |
|
499 void addSource(Node s,Value dst=0) |
|
500 { |
|
501 // source = s; |
|
502 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); |
|
503 else if(_heap[s]<dst) { |
|
504 _heap.push(s,dst); |
|
505 _pred->set(s,INVALID); |
|
506 } |
|
507 } |
|
508 |
|
509 ///Processes the next node in the priority heap |
|
510 |
|
511 ///Processes the next node in the priority heap. |
|
512 /// |
|
513 ///\warning The priority heap must not be empty! |
|
514 void processNextNode() |
|
515 { |
|
516 Node v=_heap.top(); |
|
517 Value oldvalue=_heap[v]; |
|
518 _heap.pop(); |
|
519 finalizeNodeData(v,oldvalue); |
|
520 |
|
521 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
|
522 Node w=G->target(e); |
|
523 switch(_heap.state(w)) { |
|
524 case Heap::PRE_HEAP: |
|
525 _heap.push(w,oldvalue+(*length)[e]); |
|
526 _pred->set(w,e); |
|
527 // _predNode->set(w,v); |
|
528 break; |
|
529 case Heap::IN_HEAP: |
|
530 if ( oldvalue+(*length)[e] < _heap[w] ) { |
|
531 _heap.decrease(w, oldvalue+(*length)[e]); |
|
532 _pred->set(w,e); |
|
533 // _predNode->set(w,v); |
|
534 } |
|
535 break; |
|
536 case Heap::POST_HEAP: |
|
537 break; |
|
538 } |
|
539 } |
|
540 } |
|
541 |
|
542 ///\brief Returns \c false if there are nodes |
|
543 ///to be processed in the priority heap |
|
544 /// |
|
545 ///Returns \c false if there are nodes |
|
546 ///to be processed in the priority heap |
|
547 bool emptyQueue() { return _heap.empty(); } |
|
548 ///Returns the number of the nodes to be processed in the priority heap |
|
549 |
|
550 ///Returns the number of the nodes to be processed in the priority heap |
|
551 /// |
|
552 int queueSize() { return _heap.size(); } |
|
553 |
|
554 ///Executes the algorithm. |
|
555 |
|
556 ///Executes the algorithm. |
|
557 /// |
|
558 ///\pre init() must be called and at least one node should be added |
|
559 ///with addSource() before using this function. |
|
560 /// |
|
561 ///This method runs the %Dijkstra algorithm from the root node(s) |
|
562 ///in order to |
|
563 ///compute the |
|
564 ///shortest path to each node. The algorithm computes |
|
565 ///- The shortest path tree. |
|
566 ///- The distance of each node from the root(s). |
|
567 /// |
|
568 void start() |
|
569 { |
|
570 while ( !_heap.empty() ) processNextNode(); |
|
571 } |
|
572 |
|
573 ///Executes the algorithm until \c dest is reached. |
|
574 |
|
575 ///Executes the algorithm until \c dest is reached. |
|
576 /// |
|
577 ///\pre init() must be called and at least one node should be added |
|
578 ///with addSource() before using this function. |
|
579 /// |
|
580 ///This method runs the %Dijkstra algorithm from the root node(s) |
|
581 ///in order to |
|
582 ///compute the |
|
583 ///shortest path to \c dest. The algorithm computes |
|
584 ///- The shortest path to \c dest. |
|
585 ///- The distance of \c dest from the root(s). |
|
586 /// |
|
587 void start(Node dest) |
|
588 { |
|
589 while ( !_heap.empty() && _heap.top()!=dest ) processNextNode(); |
|
590 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); |
|
591 } |
|
592 |
|
593 ///Executes the algorithm until a condition is met. |
|
594 |
|
595 ///Executes the algorithm until a condition is met. |
|
596 /// |
|
597 ///\pre init() must be called and at least one node should be added |
|
598 ///with addSource() before using this function. |
|
599 /// |
|
600 ///\param nm must be a bool (or convertible) node map. The algorithm |
|
601 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
|
602 template<class NodeBoolMap> |
|
603 void start(const NodeBoolMap &nm) |
|
604 { |
|
605 while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode(); |
|
606 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); |
|
607 } |
|
608 |
|
609 ///Runs %Dijkstra algorithm from node \c s. |
|
610 |
|
611 ///This method runs the %Dijkstra algorithm from a root node \c s |
|
612 ///in order to |
|
613 ///compute the |
|
614 ///shortest path to each node. The algorithm computes |
|
615 ///- The shortest path tree. |
|
616 ///- The distance of each node from the root. |
|
617 /// |
|
618 ///\note d.run(s) is just a shortcut of the following code. |
|
619 ///\code |
|
620 /// d.init(); |
|
621 /// d.addSource(s); |
|
622 /// d.start(); |
|
623 ///\endcode |
|
624 void run(Node s) { |
|
625 init(); |
|
626 addSource(s); |
|
627 start(); |
|
628 } |
|
629 |
|
630 ///Finds the shortest path between \c s and \c t. |
|
631 |
|
632 ///Finds the shortest path between \c s and \c t. |
|
633 /// |
|
634 ///\return The length of the shortest s---t path if there exists one, |
|
635 ///0 otherwise. |
|
636 ///\note Apart from the return value, d.run(s) is |
|
637 ///just a shortcut of the following code. |
|
638 ///\code |
|
639 /// d.init(); |
|
640 /// d.addSource(s); |
|
641 /// d.start(t); |
|
642 ///\endcode |
|
643 Value run(Node s,Node t) { |
|
644 init(); |
|
645 addSource(s); |
|
646 start(t); |
|
647 return (*_pred)[t]==INVALID?0:(*_dist)[t]; |
|
648 } |
|
649 |
|
650 ///@} |
|
651 |
|
652 ///\name Query Functions |
|
653 ///The result of the %Dijkstra algorithm can be obtained using these |
|
654 ///functions.\n |
|
655 ///Before the use of these functions, |
|
656 ///either run() or start() must be called. |
|
657 |
|
658 ///@{ |
|
659 |
|
660 ///Copies the shortest path to \c t into \c p |
|
661 |
|
662 ///This function copies the shortest path to \c t into \c p. |
|
663 ///If it \c \t is a source itself or unreachable, then it does not |
|
664 ///alter \c p. |
|
665 ///\todo Is it the right way to handle unreachable nodes? |
|
666 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
|
667 ///\c false otherwise. |
|
668 ///\sa DirPath |
|
669 template<class P> |
|
670 bool getPath(P &p,Node t) |
|
671 { |
|
672 if(reached(t)) { |
|
673 p.clear(); |
|
674 typename P::Builder b(p); |
|
675 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) |
|
676 b.pushFront(pred(t)); |
|
677 b.commit(); |
|
678 return true; |
|
679 } |
|
680 return false; |
|
681 } |
|
682 |
|
683 ///The distance of a node from the root. |
|
684 |
|
685 ///Returns the distance of a node from the root. |
|
686 ///\pre \ref run() must be called before using this function. |
|
687 ///\warning If node \c v in unreachable from the root the return value |
|
688 ///of this funcion is undefined. |
|
689 Value dist(Node v) const { return (*_dist)[v]; } |
|
690 |
|
691 ///Returns the 'previous edge' of the shortest path tree. |
|
692 |
|
693 ///For a node \c v it returns the 'previous edge' of the shortest path tree, |
|
694 ///i.e. it returns the last edge of a shortest path from the root to \c |
|
695 ///v. It is \ref INVALID |
|
696 ///if \c v is unreachable from the root or if \c v=s. The |
|
697 ///shortest path tree used here is equal to the shortest path tree used in |
|
698 ///\ref predNode(Node v). \pre \ref run() must be called before using |
|
699 ///this function. |
|
700 ///\todo predEdge could be a better name. |
|
701 Edge pred(Node v) const { return (*_pred)[v]; } |
|
702 |
|
703 ///Returns the 'previous node' of the shortest path tree. |
|
704 |
|
705 ///For a node \c v it returns the 'previous node' of the shortest path tree, |
|
706 ///i.e. it returns the last but one node from a shortest path from the |
|
707 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if |
|
708 ///\c v=s. The shortest path tree used here is equal to the shortest path |
|
709 ///tree used in \ref pred(Node v). \pre \ref run() must be called before |
|
710 ///using this function. |
|
711 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
|
712 G->source((*_pred)[v]); } |
|
713 |
|
714 ///Returns a reference to the NodeMap of distances. |
|
715 |
|
716 ///Returns a reference to the NodeMap of distances. \pre \ref run() must |
|
717 ///be called before using this function. |
|
718 const DistMap &distMap() const { return *_dist;} |
|
719 |
|
720 ///Returns a reference to the shortest path tree map. |
|
721 |
|
722 ///Returns a reference to the NodeMap of the edges of the |
|
723 ///shortest path tree. |
|
724 ///\pre \ref run() must be called before using this function. |
|
725 const PredMap &predMap() const { return *_pred;} |
|
726 |
|
727 // ///Returns a reference to the map of nodes of shortest paths. |
|
728 |
|
729 // ///Returns a reference to the NodeMap of the last but one nodes of the |
|
730 // ///shortest path tree. |
|
731 // ///\pre \ref run() must be called before using this function. |
|
732 // const PredNodeMap &predNodeMap() const { return *_predNode;} |
|
733 |
|
734 ///Checks if a node is reachable from the root. |
|
735 |
|
736 ///Returns \c true if \c v is reachable from the root. |
|
737 ///\warning The source nodes are inditated as unreached. |
|
738 ///\pre \ref run() must be called before using this function. |
|
739 /// |
|
740 bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; } |
|
741 |
|
742 ///@} |
|
743 }; |
|
744 |
|
745 |
|
746 |
|
747 |
|
748 |
|
749 ///Default traits class of Dijkstra function. |
|
750 |
|
751 ///Default traits class of Dijkstra function. |
|
752 ///\param GR Graph type. |
|
753 ///\param LM Type of length map. |
|
754 template<class GR, class LM> |
|
755 struct DijkstraWizardDefaultTraits |
|
756 { |
|
757 ///The graph type the algorithm runs on. |
|
758 typedef GR Graph; |
|
759 ///The type of the map that stores the edge lengths. |
|
760 |
|
761 ///The type of the map that stores the edge lengths. |
|
762 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
|
763 typedef LM LengthMap; |
|
764 //The type of the length of the edges. |
|
765 typedef typename LM::Value Value; |
|
766 ///The heap type used by Dijkstra algorithm. |
|
767 |
|
768 ///The heap type used by Dijkstra algorithm. |
|
769 /// |
|
770 ///\sa BinHeap |
|
771 ///\sa Dijkstra |
|
772 typedef BinHeap<typename Graph::Node, |
|
773 typename LM::Value, |
|
774 typename GR::template NodeMap<int>, |
|
775 std::less<Value> > Heap; |
|
776 |
|
777 ///\brief The type of the map that stores the last |
|
778 ///edges of the shortest paths. |
|
779 /// |
|
780 ///The type of the map that stores the last |
|
781 ///edges of the shortest paths. |
|
782 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
783 /// |
|
784 typedef NullMap <typename GR::Node,typename GR::Edge> PredMap; |
|
785 ///Instantiates a PredMap. |
|
786 |
|
787 ///This function instantiates a \ref PredMap. |
|
788 ///\param G is the graph, to which we would like to define the PredMap. |
|
789 ///\todo The graph alone may be insufficient for the initialization |
|
790 static PredMap *createPredMap(const GR &) |
|
791 { |
|
792 return new PredMap(); |
|
793 } |
|
794 ///The type of the map that stores whether a nodes is processed. |
|
795 |
|
796 ///The type of the map that stores whether a nodes is processed. |
|
797 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
798 ///By default it is a NullMap. |
|
799 ///\todo If it is set to a real map, |
|
800 ///Dijkstra::processed() should read this. |
|
801 ///\todo named parameter to set this type, function to read and write. |
|
802 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
|
803 ///Instantiates a ProcessedMap. |
|
804 |
|
805 ///This function instantiates a \ref ProcessedMap. |
|
806 ///\param G is the graph, to which |
|
807 ///we would like to define the \ref ProcessedMap |
|
808 static ProcessedMap *createProcessedMap(const GR &) |
|
809 { |
|
810 return new ProcessedMap(); |
|
811 } |
|
812 ///The type of the map that stores the dists of the nodes. |
|
813 |
|
814 ///The type of the map that stores the dists of the nodes. |
|
815 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
816 /// |
|
817 typedef NullMap<typename Graph::Node,typename LM::Value> DistMap; |
|
818 ///Instantiates a DistMap. |
|
819 |
|
820 ///This function instantiates a \ref DistMap. |
|
821 ///\param G is the graph, to which we would like to define the \ref DistMap |
|
822 static DistMap *createDistMap(const GR &) |
|
823 { |
|
824 return new DistMap(); |
|
825 } |
|
826 }; |
|
827 |
|
828 /// Default traits used by \ref DijkstraWizard |
|
829 |
|
830 /// To make it easier to use Dijkstra algorithm |
|
831 ///we have created a wizard class. |
|
832 /// This \ref DijkstraWizard class needs default traits, |
|
833 ///as well as the \ref Dijkstra class. |
|
834 /// The \ref DijkstraWizardBase is a class to be the default traits of the |
|
835 /// \ref DijkstraWizard class. |
|
836 /// \todo More named parameters are required... |
|
837 template<class GR,class LM> |
|
838 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM> |
|
839 { |
|
840 |
|
841 typedef DijkstraWizardDefaultTraits<GR,LM> Base; |
|
842 protected: |
|
843 /// Type of the nodes in the graph. |
|
844 typedef typename Base::Graph::Node Node; |
|
845 |
|
846 /// Pointer to the underlying graph. |
|
847 void *_g; |
|
848 /// Pointer to the length map |
|
849 void *_length; |
|
850 ///Pointer to the map of predecessors edges. |
|
851 void *_pred; |
|
852 // ///Pointer to the map of predecessors nodes. |
|
853 // void *_predNode; |
|
854 ///Pointer to the map of distances. |
|
855 void *_dist; |
|
856 ///Pointer to the source node. |
|
857 Node _source; |
|
858 |
|
859 public: |
|
860 /// Constructor. |
|
861 |
|
862 /// This constructor does not require parameters, therefore it initiates |
|
863 /// all of the attributes to default values (0, INVALID). |
|
864 DijkstraWizardBase() : _g(0), _length(0), _pred(0), |
|
865 // _predNode(0), |
|
866 _dist(0), _source(INVALID) {} |
|
867 |
|
868 /// Constructor. |
|
869 |
|
870 /// This constructor requires some parameters, |
|
871 /// listed in the parameters list. |
|
872 /// Others are initiated to 0. |
|
873 /// \param g is the initial value of \ref _g |
|
874 /// \param l is the initial value of \ref _length |
|
875 /// \param s is the initial value of \ref _source |
|
876 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : |
|
877 _g((void *)&g), _length((void *)&l), _pred(0), |
|
878 // _predNode(0), |
|
879 _dist(0), _source(s) {} |
|
880 |
|
881 }; |
|
882 |
|
883 /// A class to make the usage of Dijkstra algorithm easier |
|
884 |
|
885 /// This class is created to make it easier to use Dijkstra algorithm. |
|
886 /// It uses the functions and features of the plain \ref Dijkstra, |
|
887 /// but it is much simpler to use it. |
|
888 /// |
|
889 /// Simplicity means that the way to change the types defined |
|
890 /// in the traits class is based on functions that returns the new class |
|
891 /// and not on templatable built-in classes. |
|
892 /// When using the plain \ref Dijkstra |
|
893 /// the new class with the modified type comes from |
|
894 /// the original class by using the :: |
|
895 /// operator. In the case of \ref DijkstraWizard only |
|
896 /// a function have to be called and it will |
|
897 /// return the needed class. |
|
898 /// |
|
899 /// It does not have own \ref run method. When its \ref run method is called |
|
900 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run |
|
901 /// method of it. |
|
902 template<class TR> |
|
903 class DijkstraWizard : public TR |
|
904 { |
|
905 typedef TR Base; |
|
906 |
|
907 ///The type of the underlying graph. |
|
908 typedef typename TR::Graph Graph; |
|
909 //\e |
|
910 typedef typename Graph::Node Node; |
|
911 //\e |
|
912 typedef typename Graph::NodeIt NodeIt; |
|
913 //\e |
|
914 typedef typename Graph::Edge Edge; |
|
915 //\e |
|
916 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
917 |
|
918 ///The type of the map that stores the edge lengths. |
|
919 typedef typename TR::LengthMap LengthMap; |
|
920 ///The type of the length of the edges. |
|
921 typedef typename LengthMap::Value Value; |
|
922 ///\brief The type of the map that stores the last |
|
923 ///edges of the shortest paths. |
|
924 typedef typename TR::PredMap PredMap; |
|
925 // ///\brief The type of the map that stores the last but one |
|
926 // ///nodes of the shortest paths. |
|
927 // typedef typename TR::PredNodeMap PredNodeMap; |
|
928 ///The type of the map that stores the dists of the nodes. |
|
929 typedef typename TR::DistMap DistMap; |
|
930 |
|
931 ///The heap type used by the dijkstra algorithm. |
|
932 typedef typename TR::Heap Heap; |
|
933 public: |
|
934 /// Constructor. |
|
935 DijkstraWizard() : TR() {} |
|
936 |
|
937 /// Constructor that requires parameters. |
|
938 |
|
939 /// Constructor that requires parameters. |
|
940 /// These parameters will be the default values for the traits class. |
|
941 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) : |
|
942 TR(g,l,s) {} |
|
943 |
|
944 ///Copy constructor |
|
945 DijkstraWizard(const TR &b) : TR(b) {} |
|
946 |
|
947 ~DijkstraWizard() {} |
|
948 |
|
949 ///Runs Dijkstra algorithm from a given node. |
|
950 |
|
951 ///Runs Dijkstra algorithm from a given node. |
|
952 ///The node can be given by the \ref source function. |
|
953 void run() |
|
954 { |
|
955 if(Base::_source==INVALID) throw UninitializedParameter(); |
|
956 Dijkstra<Graph,LengthMap,TR> |
|
957 dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length); |
|
958 if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred); |
|
959 // if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode); |
|
960 if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist); |
|
961 dij.run(Base::_source); |
|
962 } |
|
963 |
|
964 ///Runs Dijkstra algorithm from the given node. |
|
965 |
|
966 ///Runs Dijkstra algorithm from the given node. |
|
967 ///\param s is the given source. |
|
968 void run(Node s) |
|
969 { |
|
970 Base::_source=s; |
|
971 run(); |
|
972 } |
|
973 |
|
974 template<class T> |
|
975 struct DefPredMapBase : public Base { |
|
976 typedef T PredMap; |
|
977 static PredMap *createPredMap(const Graph &) { return 0; }; |
|
978 DefPredMapBase(const TR &b) : TR(b) {} |
|
979 }; |
|
980 |
|
981 ///\brief \ref named-templ-param "Named parameter" |
|
982 ///function for setting PredMap type |
|
983 /// |
|
984 /// \ref named-templ-param "Named parameter" |
|
985 ///function for setting PredMap type |
|
986 /// |
|
987 template<class T> |
|
988 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) |
|
989 { |
|
990 Base::_pred=(void *)&t; |
|
991 return DijkstraWizard<DefPredMapBase<T> >(*this); |
|
992 } |
|
993 |
|
994 |
|
995 // template<class T> |
|
996 // struct DefPredNodeMapBase : public Base { |
|
997 // typedef T PredNodeMap; |
|
998 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; |
|
999 // DefPredNodeMapBase(const TR &b) : TR(b) {} |
|
1000 // }; |
|
1001 |
|
1002 // ///\brief \ref named-templ-param "Named parameter" |
|
1003 // ///function for setting PredNodeMap type |
|
1004 // /// |
|
1005 // /// \ref named-templ-param "Named parameter" |
|
1006 // ///function for setting PredNodeMap type |
|
1007 // /// |
|
1008 // template<class T> |
|
1009 // DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) |
|
1010 // { |
|
1011 // Base::_predNode=(void *)&t; |
|
1012 // return DijkstraWizard<DefPredNodeMapBase<T> >(*this); |
|
1013 // } |
|
1014 |
|
1015 template<class T> |
|
1016 struct DefDistMapBase : public Base { |
|
1017 typedef T DistMap; |
|
1018 static DistMap *createDistMap(const Graph &) { return 0; }; |
|
1019 DefDistMapBase(const TR &b) : TR(b) {} |
|
1020 }; |
|
1021 |
|
1022 ///\brief \ref named-templ-param "Named parameter" |
|
1023 ///function for setting DistMap type |
|
1024 /// |
|
1025 /// \ref named-templ-param "Named parameter" |
|
1026 ///function for setting DistMap type |
|
1027 /// |
|
1028 template<class T> |
|
1029 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) |
|
1030 { |
|
1031 Base::_dist=(void *)&t; |
|
1032 return DijkstraWizard<DefDistMapBase<T> >(*this); |
|
1033 } |
|
1034 |
|
1035 /// Sets the source node, from which the Dijkstra algorithm runs. |
|
1036 |
|
1037 /// Sets the source node, from which the Dijkstra algorithm runs. |
|
1038 /// \param s is the source node. |
|
1039 DijkstraWizard<TR> &source(Node s) |
|
1040 { |
|
1041 Base::_source=s; |
|
1042 return *this; |
|
1043 } |
|
1044 |
|
1045 }; |
|
1046 |
|
1047 ///Function type interface for Dijkstra algorithm. |
|
1048 |
|
1049 /// \ingroup flowalgs |
|
1050 ///Function type interface for Dijkstra algorithm. |
|
1051 /// |
|
1052 ///This function also has several |
|
1053 ///\ref named-templ-func-param "named parameters", |
|
1054 ///they are declared as the members of class \ref DijkstraWizard. |
|
1055 ///The following |
|
1056 ///example shows how to use these parameters. |
|
1057 ///\code |
|
1058 /// dijkstra(g,length,source).predMap(preds).run(); |
|
1059 ///\endcode |
|
1060 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" |
|
1061 ///to the end of the parameter list. |
|
1062 ///\sa DijkstraWizard |
|
1063 ///\sa Dijkstra |
|
1064 template<class GR, class LM> |
|
1065 DijkstraWizard<DijkstraWizardBase<GR,LM> > |
|
1066 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) |
|
1067 { |
|
1068 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s); |
|
1069 } |
|
1070 |
|
1071 } //END OF NAMESPACE LEMON |
|
1072 |
|
1073 #endif |
|
1074 |
|