2 * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
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
17 #ifndef LEMON_DIJKSTRA_H
18 #define LEMON_DIJKSTRA_H
22 ///\brief Dijkstra algorithm.
24 #include <lemon/list_graph.h>
25 #include <lemon/bin_heap.h>
26 #include <lemon/invalid.h>
30 /// \addtogroup flowalgs
33 ///Default traits class of Dijkstra class.
35 ///Default traits class of Dijkstra class.
36 ///\param GR Graph type.
37 ///\param LM Type of length map.
38 template<class GR, class LM>
39 struct DijkstraDefaultTraits
41 ///The graph type the algorithm runs on.
43 ///The type of the map that stores the edge lengths.
45 ///It must meet the \ref concept::ReadMap "ReadMap" concept.
48 //The type of the length of the edges.
49 typedef typename LM::Value Value;
50 ///The heap type used by Dijkstra algorithm.
52 ///The heap type used by Dijkstra algorithm.
56 typedef BinHeap<typename Graph::Node,
58 typename GR::template NodeMap<int>,
59 std::less<Value> > Heap;
61 ///\brief The type of the map that stores the last
62 ///edges of the shortest paths.
64 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
66 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
67 ///Instantiates a PredMap.
69 ///\todo Please document...
71 static PredMap *createPredMap(const GR &G)
73 return new PredMap(G);
75 ///\brief The type of the map that stores the last but one
76 ///nodes of the shortest paths.
78 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
80 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
81 ///Instantiates a PredNodeMap.
83 ///\todo Please document...
85 static PredNodeMap *createPredNodeMap(const GR &G)
87 return new PredNodeMap(G);
89 ///The type of the map that stores the dists of the nodes.
91 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
93 typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
94 ///Instantiates a DistMap.
96 ///\todo Please document...
98 static DistMap *createDistMap(const GR &G)
100 return new DistMap(G);
104 ///%Dijkstra algorithm class.
106 ///This class provides an efficient implementation of %Dijkstra algorithm.
107 ///The edge lengths are passed to the algorithm using a
108 ///\ref concept::ReadMap "ReadMap",
109 ///so it is easy to change it to any kind of length.
111 ///The type of the length is determined by the
112 ///\ref concept::ReadMap::Value "Value" of the length map.
114 ///It is also possible to change the underlying priority heap.
116 ///\param GR The graph type the algorithm runs on. The default value is
117 ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
118 ///is only passed to \ref DijkstraDefaultTraits.
119 ///\param LM This read-only
122 ///lengths of the edges. It is read once for each edge, so the map
123 ///may involve in relatively time consuming process to compute the edge
124 ///length if it is necessary. The default map type is
125 ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
126 ///The value of LM is not used directly by Dijkstra, it
127 ///is only passed to \ref DijkstraDefaultTraits.
128 ///\param TR Traits class to set various data types used by the algorithm.
129 ///The default traits class is
130 ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
131 ///See \ref DijkstraDefaultTraits for the documentation of
132 ///a Dijkstra traits class.
134 ///\author Jacint Szabo and Alpar Juttner
135 ///\todo We need a typedef-names should be standardized. (-:
138 template <typename GR,
142 template <typename GR=ListGraph,
143 typename LM=typename GR::template EdgeMap<int>,
144 typename TR=DijkstraDefaultTraits<GR,LM> >
149 ///The type of the underlying graph.
150 typedef typename TR::Graph Graph;
152 typedef typename Graph::Node Node;
154 typedef typename Graph::NodeIt NodeIt;
156 typedef typename Graph::Edge Edge;
158 typedef typename Graph::OutEdgeIt OutEdgeIt;
160 ///The type of the length of the edges.
161 typedef typename TR::LengthMap::Value Value;
162 ///The type of the map that stores the edge lengths.
163 typedef typename TR::LengthMap LengthMap;
164 ///\brief The type of the map that stores the last
165 ///edges of the shortest paths.
166 typedef typename TR::PredMap PredMap;
167 ///\brief The type of the map that stores the last but one
168 ///nodes of the shortest paths.
169 typedef typename TR::PredNodeMap PredNodeMap;
170 ///The type of the map that stores the dists of the nodes.
171 typedef typename TR::DistMap DistMap;
172 ///The heap type used by the dijkstra algorithm.
173 typedef typename TR::Heap Heap;
175 /// Pointer to the underlying graph.
177 /// Pointer to the length map
178 const LengthMap *length;
179 ///Pointer to the map of predecessors edges.
180 PredMap *predecessor;
181 ///Indicates if \ref predecessor is locally allocated (\c true) or not.
182 bool local_predecessor;
183 ///Pointer to the map of predecessors nodes.
184 PredNodeMap *pred_node;
185 ///Indicates if \ref pred_node is locally allocated (\c true) or not.
186 bool local_pred_node;
187 ///Pointer to the map of distances.
189 ///Indicates if \ref distance is locally allocated (\c true) or not.
192 ///The source node of the last execution.
195 ///Initializes the maps.
197 ///\todo Error if \c G or are \c NULL. What about \c length?
198 ///\todo Better memory allocation (instead of new).
202 local_predecessor = true;
203 predecessor = Traits::createPredMap(*G);
206 local_pred_node = true;
207 pred_node = Traits::createPredNodeMap(*G);
210 local_distance = true;
211 distance = Traits::createDistMap(*G);
218 struct DefPredMapTraits : public Traits {
220 ///\todo An exception should be thrown.
222 static PredMap *createPredMap(const Graph &G)
224 std::cerr << __FILE__ ":" << __LINE__ <<
225 ": error: Special maps should be manually created" << std::endl;
229 ///\ref named-templ-param "Named parameter" for setting PredMap type
231 ///\ref named-templ-param "Named parameter" for setting PredMap type
234 class DefPredMap : public Dijkstra< Graph,
236 DefPredMapTraits<T> > { };
239 struct DefPredNodeMapTraits : public Traits {
240 typedef T PredNodeMap;
241 ///\todo An exception should be thrown.
243 static PredNodeMap *createPredNodeMap(const Graph &G)
245 std::cerr << __FILE__ ":" << __LINE__ <<
246 ": error: Special maps should be manually created" << std::endl;
250 ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
252 ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
255 class DefPredNodeMap : public Dijkstra< Graph,
257 DefPredNodeMapTraits<T> > { };
260 struct DefDistMapTraits : public Traits {
262 ///\todo An exception should be thrown.
264 static DistMap *createDistMap(const Graph &G)
266 std::cerr << __FILE__ ":" << __LINE__ <<
267 ": error: Special maps should be manually created" << std::endl;
271 ///\ref named-templ-param "Named parameter" for setting DistMap type
273 ///\ref named-templ-param "Named parameter" for setting DistMap type
276 class DefDistMap : public Dijkstra< Graph,
278 DefDistMapTraits<T> > { };
282 ///\param _G the graph the algorithm will run on.
283 ///\param _length the length map used by the algorithm.
284 Dijkstra(const Graph& _G, const LengthMap& _length) :
285 G(&_G), length(&_length),
286 predecessor(NULL), local_predecessor(false),
287 pred_node(NULL), local_pred_node(false),
288 distance(NULL), local_distance(false)
294 if(local_predecessor) delete predecessor;
295 if(local_pred_node) delete pred_node;
296 if(local_distance) delete distance;
299 ///Sets the length map.
301 ///Sets the length map.
302 ///\return <tt> (*this) </tt>
303 Dijkstra &lengthMap(const LengthMap &m)
309 ///Sets the map storing the predecessor edges.
311 ///Sets the map storing the predecessor edges.
312 ///If you don't use this function before calling \ref run(),
313 ///it will allocate one. The destuctor deallocates this
314 ///automatically allocated map, of course.
315 ///\return <tt> (*this) </tt>
316 Dijkstra &predMap(PredMap &m)
318 if(local_predecessor) {
320 local_predecessor=false;
326 ///Sets the map storing the predecessor nodes.
328 ///Sets the map storing the predecessor nodes.
329 ///If you don't use this function before calling \ref run(),
330 ///it will allocate one. The destuctor deallocates this
331 ///automatically allocated map, of course.
332 ///\return <tt> (*this) </tt>
333 Dijkstra &predNodeMap(PredNodeMap &m)
335 if(local_pred_node) {
337 local_pred_node=false;
343 ///Sets the map storing the distances calculated by the algorithm.
345 ///Sets the map storing the distances calculated by the algorithm.
346 ///If you don't use this function before calling \ref run(),
347 ///it will allocate one. The destuctor deallocates this
348 ///automatically allocated map, of course.
349 ///\return <tt> (*this) </tt>
350 Dijkstra &distMap(DistMap &m)
354 local_distance=false;
360 ///Runs %Dijkstra algorithm from node \c s.
362 ///This method runs the %Dijkstra algorithm from a root node \c s
365 ///shortest path to each node. The algorithm computes
366 ///- The shortest path tree.
367 ///- The distance of each node from the root.
368 ///\todo heap_map's type could also be in the traits class.
375 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
376 predecessor->set(u,INVALID);
377 pred_node->set(u,INVALID);
380 typename Graph::template NodeMap<int> heap_map(*G,-1);
386 while ( !heap.empty() ) {
389 Value oldvalue=heap[v];
391 distance->set(v, oldvalue);
394 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
396 switch(heap.state(w)) {
398 heap.push(w,oldvalue+(*length)[e]);
399 predecessor->set(w,e);
403 if ( oldvalue+(*length)[e] < heap[w] ) {
404 heap.decrease(w, oldvalue+(*length)[e]);
405 predecessor->set(w,e);
409 case Heap::POST_HEAP:
416 ///The distance of a node from the root.
418 ///Returns the distance of a node from the root.
419 ///\pre \ref run() must be called before using this function.
420 ///\warning If node \c v in unreachable from the root the return value
421 ///of this funcion is undefined.
422 Value dist(Node v) const { return (*distance)[v]; }
424 ///Returns the 'previous edge' of the shortest path tree.
426 ///For a node \c v it returns the 'previous edge' of the shortest path tree,
427 ///i.e. it returns the last edge of a shortest path from the root to \c
428 ///v. It is \ref INVALID
429 ///if \c v is unreachable from the root or if \c v=s. The
430 ///shortest path tree used here is equal to the shortest path tree used in
431 ///\ref predNode(Node v). \pre \ref run() must be called before using
433 ///\todo predEdge could be a better name.
434 Edge pred(Node v) const { return (*predecessor)[v]; }
436 ///Returns the 'previous node' of the shortest path tree.
438 ///For a node \c v it returns the 'previous node' of the shortest path tree,
439 ///i.e. it returns the last but one node from a shortest path from the
440 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
441 ///\c v=s. The shortest path tree used here is equal to the shortest path
442 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
443 ///using this function.
444 Node predNode(Node v) const { return (*pred_node)[v]; }
446 ///Returns a reference to the NodeMap of distances.
448 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
449 ///be called before using this function.
450 const DistMap &distMap() const { return *distance;}
452 ///Returns a reference to the shortest path tree map.
454 ///Returns a reference to the NodeMap of the edges of the
455 ///shortest path tree.
456 ///\pre \ref run() must be called before using this function.
457 const PredMap &predMap() const { return *predecessor;}
459 ///Returns a reference to the map of nodes of shortest paths.
461 ///Returns a reference to the NodeMap of the last but one nodes of the
462 ///shortest path tree.
463 ///\pre \ref run() must be called before using this function.
464 const PredNodeMap &predNodeMap() const { return *pred_node;}
466 ///Checks if a node is reachable from the root.
468 ///Returns \c true if \c v is reachable from the root.
469 ///\note The root node is reported to be reached!
470 ///\pre \ref run() must be called before using this function.
472 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
476 template<class GR,class LM>
477 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
480 typedef DijkstraDefaultTraits<GR,LM> Base;
482 /// Pointer to the underlying graph.
484 /// Pointer to the length map
486 ///Pointer to the map of predecessors edges.
488 ///Pointer to the map of predecessors nodes.
490 ///Pointer to the map of distances.
492 ///Pointer to the source node.
495 typedef typename Base::Graph::Node Node;
498 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
499 _dist(0), _source(INVALID) {}
501 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
502 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
503 _dist(0), _source((void *)&s) {}
512 class DijkstraWizard : public TR
516 ///The type of the underlying graph.
517 typedef typename TR::Graph Graph;
519 typedef typename Graph::Node Node;
521 typedef typename Graph::NodeIt NodeIt;
523 typedef typename Graph::Edge Edge;
525 typedef typename Graph::OutEdgeIt OutEdgeIt;
527 ///The type of the map that stores the edge lengths.
528 typedef typename TR::LengthMap LengthMap;
529 ///The type of the length of the edges.
530 typedef typename LengthMap::Value Value;
531 ///\brief The type of the map that stores the last
532 ///edges of the shortest paths.
533 typedef typename TR::PredMap PredMap;
534 ///\brief The type of the map that stores the last but one
535 ///nodes of the shortest paths.
536 typedef typename TR::PredNodeMap PredNodeMap;
537 ///The type of the map that stores the dists of the nodes.
538 typedef typename TR::DistMap DistMap;
540 ///The heap type used by the dijkstra algorithm.
541 typedef typename TR::Heap Heap;
543 DijkstraWizard() : TR() {}
545 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
548 DijkstraWizard(const TR &b) : TR(b) {}
555 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
556 if(_pred) Dij.predMap(*(PredMap*)_pred);
557 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
558 if(_dist) Dij.distMap(*(DistMap*)_dist);
559 Dij.run(*(Node*)_source);
570 struct DefPredMapBase : public Base {
572 static PredMap *createPredMap(const Graph &G) {};
577 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
580 return DijkstraWizard<DefPredMapBase<T> >(*this);
585 struct DefPredNodeMapBase : public Base {
586 typedef T PredNodeMap;
587 static PredNodeMap *createPredNodeMap(const Graph &G) {};
592 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
594 _predNode=(void *)&t;
595 return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
599 struct DefDistMapBase : public Base {
601 static DistMap *createDistMap(const Graph &G) {};
606 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
609 return DijkstraWizard<DefDistMapBase<T> >(*this);
613 DijkstraWizard<TR> &setSource(Node s)
623 ///\todo Please document...
625 template<class GR, class LM>
626 DijkstraWizard<DijkstraWizardBase<GR,LM> >
627 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
629 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
634 } //END OF NAMESPACE LEMON