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