19 |
19 |
20 ///\ingroup flowalgs |
20 ///\ingroup flowalgs |
21 ///\file |
21 ///\file |
22 ///\brief Dijkstra algorithm. |
22 ///\brief Dijkstra algorithm. |
23 |
23 |
|
24 #include <lemon/list_graph.h> |
24 #include <lemon/bin_heap.h> |
25 #include <lemon/bin_heap.h> |
25 #include <lemon/invalid.h> |
26 #include <lemon/invalid.h> |
26 |
27 |
27 namespace lemon { |
28 namespace lemon { |
28 |
29 |
29 /// \addtogroup flowalgs |
30 /// \addtogroup flowalgs |
30 /// @{ |
31 /// @{ |
31 |
32 |
|
33 template<class GR, class LM> |
|
34 struct DijkstraDefaultTraits |
|
35 { |
|
36 ///\e |
|
37 typedef GR Graph; |
|
38 ///\e |
|
39 typedef typename Graph::Node Node; |
|
40 ///\e |
|
41 typedef typename Graph::Edge Edge; |
|
42 ///The type of the map that stores the edge lengths. |
|
43 |
|
44 ///It must meet the \ref ReadMap concept. |
|
45 /// |
|
46 typedef LM LengthMap; |
|
47 ///The type of the length of the edges. |
|
48 typedef typename LM::ValueType ValueType; |
|
49 ///The heap type used by the dijkstra algorithm. |
|
50 typedef BinHeap<typename Graph::Node, |
|
51 typename LM::ValueType, |
|
52 typename GR::template NodeMap<int>, |
|
53 std::less<ValueType> > Heap; |
|
54 |
|
55 ///\brief The type of the map that stores the last |
|
56 ///edges of the shortest paths. |
|
57 /// |
|
58 ///It must meet the \ref WriteMap concept. |
|
59 /// |
|
60 typedef typename Graph::template NodeMap<Edge> PredMap; |
|
61 /// |
|
62 |
|
63 ///\todo Please document... |
|
64 /// |
|
65 static PredMap *createPredMap(const Graph &G) |
|
66 { |
|
67 return new PredMap(G); |
|
68 } |
|
69 ///\brief The type of the map that stores the last but one |
|
70 ///nodes of the shortest paths. |
|
71 /// |
|
72 ///It must meet the \ref WriteMap concept. |
|
73 /// |
|
74 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
|
75 /// |
|
76 |
|
77 ///\todo Please document... |
|
78 /// |
|
79 static PredNodeMap *createPredNodeMap(const Graph &G) |
|
80 { |
|
81 return new PredNodeMap(G); |
|
82 } |
|
83 ///The type of the map that stores the dists of the nodes. |
|
84 |
|
85 ///It must meet the \ref WriteMap concept. |
|
86 /// |
|
87 typedef typename Graph::template NodeMap<ValueType> DistMap; |
|
88 /// |
|
89 |
|
90 ///\todo Please document... |
|
91 /// |
|
92 static DistMap *createDistMap(const Graph &G) |
|
93 { |
|
94 return new DistMap(G); |
|
95 } |
|
96 }; |
|
97 |
32 ///%Dijkstra algorithm class. |
98 ///%Dijkstra algorithm class. |
33 |
99 |
34 ///This class provides an efficient implementation of %Dijkstra algorithm. |
100 ///This class provides an efficient implementation of %Dijkstra algorithm. |
35 ///The edge lengths are passed to the algorithm using a |
101 ///The edge lengths are passed to the algorithm using a |
36 ///\ref skeleton::ReadMap "ReadMap", |
102 ///\ref skeleton::ReadMap "ReadMap", |
39 ///The type of the length is determined by the |
105 ///The type of the length is determined by the |
40 ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map. |
106 ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map. |
41 /// |
107 /// |
42 ///It is also possible to change the underlying priority heap. |
108 ///It is also possible to change the underlying priority heap. |
43 /// |
109 /// |
44 ///\param GR The graph type the algorithm runs on. |
110 ///\param GR The graph type the algorithm runs on. The default value is |
|
111 ///\ref ListGraph |
45 ///\param LM This read-only |
112 ///\param LM This read-only |
46 ///EdgeMap |
113 ///EdgeMap |
47 ///determines the |
114 ///determines the |
48 ///lengths of the edges. It is read once for each edge, so the map |
115 ///lengths of the edges. It is read once for each edge, so the map |
49 ///may involve in relatively time consuming process to compute the edge |
116 ///may involve in relatively time consuming process to compute the edge |
59 ///should not be fixed. (Problematic to solve). |
126 ///should not be fixed. (Problematic to solve). |
60 |
127 |
61 #ifdef DOXYGEN |
128 #ifdef DOXYGEN |
62 template <typename GR, |
129 template <typename GR, |
63 typename LM, |
130 typename LM, |
64 typename Heap> |
131 typename TR> |
65 #else |
132 #else |
66 template <typename GR, |
133 template <typename GR=ListGraph, |
67 typename LM=typename GR::template EdgeMap<int>, |
134 typename LM=typename GR::template EdgeMap<int>, |
68 template <class,class,class,class> class Heap = BinHeap > |
135 typename TR=DijkstraDefaultTraits<GR,LM> > |
69 #endif |
136 #endif |
70 class Dijkstra{ |
137 class Dijkstra{ |
71 public: |
138 public: |
|
139 typedef TR Traits; |
72 ///The type of the underlying graph. |
140 ///The type of the underlying graph. |
73 typedef GR Graph; |
141 typedef GR Graph; |
74 ///\e |
142 ///\e |
75 typedef typename Graph::Node Node; |
143 typedef typename Graph::Node Node; |
76 ///\e |
144 ///\e |
84 typedef typename LM::ValueType ValueType; |
152 typedef typename LM::ValueType ValueType; |
85 ///The type of the map that stores the edge lengths. |
153 ///The type of the map that stores the edge lengths. |
86 typedef LM LengthMap; |
154 typedef LM LengthMap; |
87 ///\brief The type of the map that stores the last |
155 ///\brief The type of the map that stores the last |
88 ///edges of the shortest paths. |
156 ///edges of the shortest paths. |
89 typedef typename Graph::template NodeMap<Edge> PredMap; |
157 typedef typename TR::PredMap PredMap; |
90 ///\brief The type of the map that stores the last but one |
158 ///\brief The type of the map that stores the last but one |
91 ///nodes of the shortest paths. |
159 ///nodes of the shortest paths. |
92 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
160 typedef typename TR::PredNodeMap PredNodeMap; |
93 ///The type of the map that stores the dists of the nodes. |
161 ///The type of the map that stores the dists of the nodes. |
94 typedef typename Graph::template NodeMap<ValueType> DistMap; |
162 typedef typename TR::DistMap DistMap; |
|
163 |
|
164 ///The heap type used by the dijkstra algorithm. |
|
165 typedef typename TR::Heap Heap; |
95 |
166 |
96 private: |
167 private: |
97 /// Pointer to the underlying graph. |
168 /// Pointer to the underlying graph. |
98 const Graph *G; |
169 const Graph *G; |
99 /// Pointer to the length map |
170 /// Pointer to the length map |
120 ///\todo Better memory allocation (instead of new). |
191 ///\todo Better memory allocation (instead of new). |
121 void init_maps() |
192 void init_maps() |
122 { |
193 { |
123 if(!predecessor) { |
194 if(!predecessor) { |
124 local_predecessor = true; |
195 local_predecessor = true; |
125 predecessor = new PredMap(*G); |
196 predecessor = Traits::createPredMap(*G); |
126 } |
197 } |
127 if(!pred_node) { |
198 if(!pred_node) { |
128 local_pred_node = true; |
199 local_pred_node = true; |
129 pred_node = new PredNodeMap(*G); |
200 pred_node = Traits::createPredNodeMap(*G); |
130 } |
201 } |
131 if(!distance) { |
202 if(!distance) { |
132 local_distance = true; |
203 local_distance = true; |
133 distance = new DistMap(*G); |
204 distance = Traits::createDistMap(*G); |
134 } |
205 } |
135 } |
206 } |
136 |
207 |
137 public : |
208 public : |
|
209 |
|
210 template <class T> |
|
211 struct SetPredMapTraits : public Traits { |
|
212 typedef T PredMap; |
|
213 ///\todo An exception should be thrown. |
|
214 /// |
|
215 static PredMap *createPredMap(const Graph &G) |
|
216 { |
|
217 std::cerr << __FILE__ ":" << __LINE__ << |
|
218 ": error: Special maps should be manually created" << std::endl; |
|
219 exit(1); |
|
220 } |
|
221 }; |
|
222 ///\ref named-templ-param "Named parameter" for setting PredMap's type |
|
223 template <class T> |
|
224 class SetPredMap : public Dijkstra< Graph, |
|
225 LengthMap, |
|
226 SetPredMapTraits<T> > { }; |
|
227 |
|
228 template <class T> |
|
229 struct SetPredNodeMapTraits : public Traits { |
|
230 typedef T PredNodeMap; |
|
231 ///\todo An exception should be thrown. |
|
232 /// |
|
233 static PredNodeMap *createPredNodeMap(const Graph &G) |
|
234 { |
|
235 std::cerr << __FILE__ ":" << __LINE__ << |
|
236 ": error: Special maps should be manually created" << std::endl; |
|
237 exit(1); |
|
238 } |
|
239 }; |
|
240 ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type |
|
241 template <class T> |
|
242 class SetPredNodeMap : public Dijkstra< Graph, |
|
243 LengthMap, |
|
244 SetPredNodeMapTraits<T> > { }; |
|
245 |
|
246 template <class T> |
|
247 struct SetDistMapTraits : public Traits { |
|
248 typedef T DistMap; |
|
249 ///\todo An exception should be thrown. |
|
250 /// |
|
251 static DistMap *createDistMap(const Graph &G) |
|
252 { |
|
253 std::cerr << __FILE__ ":" << __LINE__ << |
|
254 ": error: Special maps should be manually created" << std::endl; |
|
255 exit(1); |
|
256 } |
|
257 }; |
|
258 ///\ref named-templ-param "Named parameter" for setting DistMap's type |
|
259 template <class T> |
|
260 class SetDistMap : public Dijkstra< Graph, |
|
261 LengthMap, |
|
262 SetDistMapTraits<T> > { }; |
|
263 |
138 ///Constructor. |
264 ///Constructor. |
139 |
265 |
140 ///\param _G the graph the algorithm will run on. |
266 ///\param _G the graph the algorithm will run on. |
141 ///\param _length the length map used by the algorithm. |
267 ///\param _length the length map used by the algorithm. |
142 Dijkstra(const Graph& _G, const LM& _length) : |
268 Dijkstra(const Graph& _G, const LM& _length) : |
254 |
376 |
255 |
377 |
256 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
378 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { |
257 Node w=G->head(e); |
379 Node w=G->head(e); |
258 switch(heap.state(w)) { |
380 switch(heap.state(w)) { |
259 case HeapType::PRE_HEAP: |
381 case Heap::PRE_HEAP: |
260 heap.push(w,oldvalue+(*length)[e]); |
382 heap.push(w,oldvalue+(*length)[e]); |
261 predecessor->set(w,e); |
383 predecessor->set(w,e); |
262 pred_node->set(w,v); |
384 pred_node->set(w,v); |
263 break; |
385 break; |
264 case HeapType::IN_HEAP: |
386 case Heap::IN_HEAP: |
265 if ( oldvalue+(*length)[e] < heap[w] ) { |
387 if ( oldvalue+(*length)[e] < heap[w] ) { |
266 heap.decrease(w, oldvalue+(*length)[e]); |
388 heap.decrease(w, oldvalue+(*length)[e]); |
267 predecessor->set(w,e); |
389 predecessor->set(w,e); |
268 pred_node->set(w,v); |
390 pred_node->set(w,v); |
269 } |
391 } |
270 break; |
392 break; |
271 case HeapType::POST_HEAP: |
393 case Heap::POST_HEAP: |
272 break; |
394 break; |
273 } |
395 } |
274 } |
396 } |
275 } |
397 } |
276 } |
398 } |
332 ///\pre \ref run() must be called before using this function. |
454 ///\pre \ref run() must be called before using this function. |
333 /// |
455 /// |
334 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
456 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
335 |
457 |
336 }; |
458 }; |
|
459 |
|
460 ///\e |
|
461 |
|
462 ///\e |
|
463 /// |
|
464 template<class TR> |
|
465 class _Dijkstra |
|
466 { |
|
467 typedef TR Traits; |
|
468 |
|
469 ///The type of the underlying graph. |
|
470 typedef typename TR::Graph Graph; |
|
471 ///\e |
|
472 typedef typename Graph::Node Node; |
|
473 ///\e |
|
474 typedef typename Graph::NodeIt NodeIt; |
|
475 ///\e |
|
476 typedef typename Graph::Edge Edge; |
|
477 ///\e |
|
478 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
479 |
|
480 ///The type of the map that stores the edge lengths. |
|
481 typedef typename TR::LengthMap LengthMap; |
|
482 ///The type of the length of the edges. |
|
483 typedef typename LengthMap::ValueType ValueType; |
|
484 ///\brief The type of the map that stores the last |
|
485 ///edges of the shortest paths. |
|
486 typedef typename TR::PredMap PredMap; |
|
487 ///\brief The type of the map that stores the last but one |
|
488 ///nodes of the shortest paths. |
|
489 typedef typename TR::PredNodeMap PredNodeMap; |
|
490 ///The type of the map that stores the dists of the nodes. |
|
491 typedef typename TR::DistMap DistMap; |
|
492 |
|
493 ///The heap type used by the dijkstra algorithm. |
|
494 typedef typename TR::Heap Heap; |
|
495 |
|
496 /// Pointer to the underlying graph. |
|
497 const Graph *G; |
|
498 /// Pointer to the length map |
|
499 const LengthMap *length; |
|
500 ///Pointer to the map of predecessors edges. |
|
501 PredMap *predecessor; |
|
502 ///Pointer to the map of predecessors nodes. |
|
503 PredNodeMap *pred_node; |
|
504 ///Pointer to the map of distances. |
|
505 DistMap *distance; |
|
506 |
|
507 Node source; |
|
508 |
|
509 public: |
|
510 _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0), |
|
511 distance(0), source(INVALID) {} |
|
512 |
|
513 _Dijkstra(const Graph &g,const LengthMap &l, Node s) : |
|
514 G(&g), length(&l), predecessor(0), pred_node(0), |
|
515 distance(0), source(s) {} |
|
516 |
|
517 ~_Dijkstra() |
|
518 { |
|
519 Dijkstra<Graph,LengthMap,TR> Dij(*G,*length); |
|
520 if(predecessor) Dij.setPredMap(*predecessor); |
|
521 if(pred_node) Dij.setPredNodeMap(*pred_node); |
|
522 if(distance) Dij.setDistMap(*distance); |
|
523 Dij.run(source); |
|
524 } |
|
525 |
|
526 template<class T> |
|
527 struct SetPredMapTraits : public Traits {typedef T PredMap;}; |
|
528 |
|
529 ///\e |
|
530 template<class T> |
|
531 _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t) |
|
532 { |
|
533 _Dijkstra<SetPredMapTraits<T> > r; |
|
534 r.G=G; |
|
535 r.length=length; |
|
536 r.predecessor=&t; |
|
537 r.pred_node=pred_node; |
|
538 r.distance=distance; |
|
539 r.source=source; |
|
540 return r; |
|
541 } |
|
542 |
|
543 template<class T> |
|
544 struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;}; |
|
545 ///\e |
|
546 template<class T> |
|
547 _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t) |
|
548 { |
|
549 _Dijkstra<SetPredNodeMapTraits<T> > r; |
|
550 r.G=G; |
|
551 r.length=length; |
|
552 r.predecessor=predecessor; |
|
553 r.pred_node=&t; |
|
554 r.distance=distance; |
|
555 r.source=source; |
|
556 return r; |
|
557 } |
|
558 |
|
559 template<class T> |
|
560 struct SetDistMapTraits : public Traits {typedef T DistMap;}; |
|
561 ///\e |
|
562 template<class T> |
|
563 _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t) |
|
564 { |
|
565 _Dijkstra<SetPredMapTraits<T> > r; |
|
566 r.G=G; |
|
567 r.length=length; |
|
568 r.predecessor=predecessor; |
|
569 r.pred_node=pred_node; |
|
570 r.distance=&t; |
|
571 r.source=source; |
|
572 return r; |
|
573 } |
|
574 |
|
575 ///\e |
|
576 _Dijkstra<TR> &setSource(Node s) |
|
577 { |
|
578 source=s; |
|
579 return *this; |
|
580 } |
|
581 |
|
582 }; |
337 |
583 |
|
584 ///\e |
|
585 |
|
586 ///\e |
|
587 /// |
|
588 template<class GR, class LM> |
|
589 _Dijkstra<DijkstraDefaultTraits<GR,LM> > |
|
590 dijkstra(const GR &g,const LM &l,typename GR::Node s) |
|
591 { |
|
592 return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s); |
|
593 } |
|
594 |
338 /// @} |
595 /// @} |
339 |
596 |
340 } //END OF NAMESPACE LEMON |
597 } //END OF NAMESPACE LEMON |
341 |
598 |
342 #endif |
599 #endif |