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>
27 #include <lemon/error.h>
28 #include <lemon/maps.h>
33 /// \addtogroup flowalgs
36 ///Default traits class of Dijkstra class.
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
44 ///The graph type the algorithm runs on.
46 ///The type of the map that stores the edge lengths.
48 ///The type of the map that stores the edge lengths.
49 ///It must meet the \ref concept::ReadMap "ReadMap" concept.
51 //The type of the length of the edges.
52 typedef typename LM::Value Value;
53 ///The heap type used by Dijkstra algorithm.
55 ///The heap type used by Dijkstra algorithm.
59 typedef BinHeap<typename Graph::Node,
61 typename GR::template NodeMap<int>,
62 std::less<Value> > Heap;
64 ///\brief The type of the map that stores the last
65 ///edges of the shortest paths.
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.
71 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
72 ///Instantiates a PredMap.
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)
79 return new PredMap(G);
81 ///\brief The type of the map that stores the last but one
82 ///nodes of the shortest paths.
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.
88 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
89 ///Instantiates a PredNodeMap.
91 ///This function instantiates a \ref PredNodeMap.
92 ///\param G is the graph, to which we would like to define the \ref PredNodeMap
93 static PredNodeMap *createPredNodeMap(const GR &G)
95 return new PredNodeMap(G);
98 ///The type of the map that stores whether a nodes is reached.
100 ///The type of the map that stores whether a nodes is reached.
101 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
102 ///By default it is a NullMap.
103 ///\todo If it is set to a real map, Dijkstra::reached() should read this.
104 ///\todo named parameter to set this type, function to read and write.
105 typedef NullMap<typename Graph::Node,bool> ReachedMap;
106 ///Instantiates a ReachedMap.
108 ///This function instantiates a \ref ReachedMap.
109 ///\param G is the graph, to which we would like to define the \ref ReachedMap
110 static ReachedMap *createReachedMap(const GR &G)
112 return new ReachedMap();
114 ///The type of the map that stores the dists of the nodes.
116 ///The type of the map that stores the dists of the nodes.
117 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
119 typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
120 ///Instantiates a DistMap.
122 ///This function instantiates a \ref DistMap.
123 ///\param G is the graph, to which we would like to define the \ref DistMap
124 static DistMap *createDistMap(const GR &G)
126 return new DistMap(G);
130 ///%Dijkstra algorithm class.
132 ///This class provides an efficient implementation of %Dijkstra algorithm.
133 ///The edge lengths are passed to the algorithm using a
134 ///\ref concept::ReadMap "ReadMap",
135 ///so it is easy to change it to any kind of length.
137 ///The type of the length is determined by the
138 ///\ref concept::ReadMap::Value "Value" of the length map.
140 ///It is also possible to change the underlying priority heap.
142 ///\param GR The graph type the algorithm runs on. The default value is
143 ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
144 ///is only passed to \ref DijkstraDefaultTraits.
145 ///\param LM This read-only
148 ///lengths of the edges. It is read once for each edge, so the map
149 ///may involve in relatively time consuming process to compute the edge
150 ///length if it is necessary. The default map type is
151 ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
152 ///The value of LM is not used directly by Dijkstra, it
153 ///is only passed to \ref DijkstraDefaultTraits.
154 ///\param TR Traits class to set various data types used by the algorithm.
155 ///The default traits class is
156 ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
157 ///See \ref DijkstraDefaultTraits for the documentation of
158 ///a Dijkstra traits class.
160 ///\author Jacint Szabo and Alpar Juttner
161 ///\todo A compare object would be nice.
164 template <typename GR,
168 template <typename GR=ListGraph,
169 typename LM=typename GR::template EdgeMap<int>,
170 typename TR=DijkstraDefaultTraits<GR,LM> >
175 * \brief \ref Exception for uninitialized parameters.
177 * This error represents problems in the initialization
178 * of the parameters of the algorithms.
180 class UninitializedParameter : public lemon::UninitializedParameter {
182 virtual const char* exceptionName() const {
183 return "lemon::Dijsktra::UninitializedParameter";
188 ///The type of the underlying graph.
189 typedef typename TR::Graph Graph;
191 typedef typename Graph::Node Node;
193 typedef typename Graph::NodeIt NodeIt;
195 typedef typename Graph::Edge Edge;
197 typedef typename Graph::OutEdgeIt OutEdgeIt;
199 ///The type of the length of the edges.
200 typedef typename TR::LengthMap::Value Value;
201 ///The type of the map that stores the edge lengths.
202 typedef typename TR::LengthMap LengthMap;
203 ///\brief The type of the map that stores the last
204 ///edges of the shortest paths.
205 typedef typename TR::PredMap PredMap;
206 ///\brief The type of the map that stores the last but one
207 ///nodes of the shortest paths.
208 typedef typename TR::PredNodeMap PredNodeMap;
209 ///The type of the map indicating if a node is reached.
210 typedef typename TR::ReachedMap ReachedMap;
211 ///The type of the map that stores the dists of the nodes.
212 typedef typename TR::DistMap DistMap;
213 ///The heap type used by the dijkstra algorithm.
214 typedef typename TR::Heap Heap;
216 /// Pointer to the underlying graph.
218 /// Pointer to the length map
219 const LengthMap *length;
220 ///Pointer to the map of predecessors edges.
222 ///Indicates if \ref _pred is locally allocated (\c true) or not.
224 ///Pointer to the map of predecessors nodes.
225 PredNodeMap *pred_node;
226 ///Indicates if \ref pred_node is locally allocated (\c true) or not.
227 bool local_pred_node;
228 ///Pointer to the map of distances.
230 ///Indicates if \ref distance is locally allocated (\c true) or not.
232 ///Pointer to the map of reached status of the nodes.
233 ReachedMap *_reached;
234 ///Indicates if \ref _reached is locally allocated (\c true) or not.
237 ///The source node of the last execution.
240 ///Creates the maps if necessary.
242 ///\todo Error if \c G or are \c NULL. What about \c length?
243 ///\todo Better memory allocation (instead of new).
248 _pred = Traits::createPredMap(*G);
251 local_pred_node = true;
252 pred_node = Traits::createPredNodeMap(*G);
255 local_distance = true;
256 distance = Traits::createDistMap(*G);
259 local_reached = true;
260 _reached = Traits::createReachedMap(*G);
266 ///\name Named template parameters
271 struct DefPredMapTraits : public Traits {
273 static PredMap *createPredMap(const Graph &G)
275 throw UninitializedParameter();
278 ///\ref named-templ-param "Named parameter" for setting PredMap type
280 ///\ref named-templ-param "Named parameter" for setting PredMap type
283 class DefPredMap : public Dijkstra< Graph,
285 DefPredMapTraits<T> > { };
288 struct DefPredNodeMapTraits : public Traits {
289 typedef T PredNodeMap;
290 static PredNodeMap *createPredNodeMap(const Graph &G)
292 throw UninitializedParameter();
295 ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
297 ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
300 class DefPredNodeMap : public Dijkstra< Graph,
302 DefPredNodeMapTraits<T> > { };
305 struct DefDistMapTraits : public Traits {
307 static DistMap *createDistMap(const Graph &G)
309 throw UninitializedParameter();
312 ///\ref named-templ-param "Named parameter" for setting DistMap type
314 ///\ref named-templ-param "Named parameter" for setting DistMap type
317 class DefDistMap : public Dijkstra< Graph,
319 DefDistMapTraits<T> > { };
322 struct DefReachedMapTraits : public Traits {
323 typedef T ReachedMap;
324 static ReachedMap *createReachedMap(const Graph &G)
326 throw UninitializedParameter();
329 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
331 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
334 class DefReachedMap : public Dijkstra< Graph,
336 DefReachedMapTraits<T> > { };
338 struct DefGraphReachedMapTraits : public Traits {
339 typedef typename Graph::NodeMap<bool> ReachedMap;
340 static ReachedMap *createReachedMap(const Graph &G)
342 return new ReachedMap(G);
345 ///\brief \ref named-templ-param "Named parameter"
346 ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
348 ///\ref named-templ-param "Named parameter"
349 ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
350 ///If you don't set it explicitely, it will be automatically allocated.
352 class DefReachedMapToBeDefaultMap :
353 public Dijkstra< Graph,
355 DefGraphReachedMapTraits> { };
361 typename Graph::template NodeMap<int> _heap_map;
367 ///\param _G the graph the algorithm will run on.
368 ///\param _length the length map used by the algorithm.
369 Dijkstra(const Graph& _G, const LengthMap& _length) :
370 G(&_G), length(&_length),
371 _pred(NULL), local_pred(false),
372 pred_node(NULL), local_pred_node(false),
373 distance(NULL), local_distance(false),
374 _reached(NULL), local_reached(false),
375 _heap_map(*G,-1),_heap(_heap_map)
381 if(local_pred) delete _pred;
382 if(local_pred_node) delete pred_node;
383 if(local_distance) delete distance;
384 if(local_reached) delete _reached;
387 ///Sets the length map.
389 ///Sets the length map.
390 ///\return <tt> (*this) </tt>
391 Dijkstra &lengthMap(const LengthMap &m)
397 ///Sets the map storing the predecessor edges.
399 ///Sets the map storing the predecessor edges.
400 ///If you don't use this function before calling \ref run(),
401 ///it will allocate one. The destuctor deallocates this
402 ///automatically allocated map, of course.
403 ///\return <tt> (*this) </tt>
404 Dijkstra &predMap(PredMap &m)
414 ///Sets the map storing the predecessor nodes.
416 ///Sets the map storing the predecessor nodes.
417 ///If you don't use this function before calling \ref run(),
418 ///it will allocate one. The destuctor deallocates this
419 ///automatically allocated map, of course.
420 ///\return <tt> (*this) </tt>
421 Dijkstra &predNodeMap(PredNodeMap &m)
423 if(local_pred_node) {
425 local_pred_node=false;
431 ///Sets the map storing the distances calculated by the algorithm.
433 ///Sets the map storing the distances calculated by the algorithm.
434 ///If you don't use this function before calling \ref run(),
435 ///it will allocate one. The destuctor deallocates this
436 ///automatically allocated map, of course.
437 ///\return <tt> (*this) </tt>
438 Dijkstra &distMap(DistMap &m)
442 local_distance=false;
448 ///\name Excetution control
449 ///The simplest way to execute the algorithm is to use
452 ///It you need more control on the execution,
453 ///first you must call \ref init(), then you can add several source nodes
454 ///with \ref addSource(). Finally \ref start() will perform the actual path
459 ///Initializes the internal data structures.
461 ///Initializes the internal data structures.
463 ///\todo _heap_map's type could also be in the traits class.
468 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
469 _pred->set(u,INVALID);
470 pred_node->set(u,INVALID);
471 ///\todo *_reached is not set to false.
472 _heap_map.set(u,Heap::PRE_HEAP);
476 ///Adds a new source node.
478 ///Adds a new source node the the priority heap.
479 ///It checks if the node has already been added to the heap.
481 ///The optional second parameter is the initial distance of the node.
483 ///\todo Do we really want to check it?
484 void addSource(Node s,Value dst=0)
487 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
493 _reached->set(v,true);
494 Value oldvalue=_heap[v];
496 distance->set(v, oldvalue);
498 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
500 switch(_heap.state(w)) {
502 _heap.push(w,oldvalue+(*length)[e]);
507 if ( oldvalue+(*length)[e] < _heap[w] ) {
508 _heap.decrease(w, oldvalue+(*length)[e]);
513 case Heap::POST_HEAP:
519 ///Starts the execution of the algorithm.
521 ///Starts the execution of the algorithm.
523 ///\pre init() must be called before and at least one node should be added
526 ///This method runs the %Dijkstra algorithm from the root node(s)
529 ///shortest path to each node. The algorithm computes
530 ///- The shortest path tree.
531 ///- The distance of each node from the root(s).
535 while ( !_heap.empty() ) processNode();
538 ///Starts the execution of the algorithm until \c dest is reached.
540 ///Starts the execution of the algorithm until \c dest is reached.
542 ///\pre init() must be called before and at least one node should be added
545 ///This method runs the %Dijkstra algorithm from the root node(s)
548 ///shortest path to \c dest. The algorithm computes
549 ///- The shortest path to \c dest.
550 ///- The distance of \c dest from the root(s).
552 void start(Node dest)
554 while ( !_heap.empty() && _heap.top()!=dest) processNode();
557 ///Runs %Dijkstra algorithm from node \c s.
559 ///This method runs the %Dijkstra algorithm from a root node \c s
562 ///shortest path to each node. The algorithm computes
563 ///- The shortest path tree.
564 ///- The distance of each node from the root.
566 ///\note d.run(s) is just a shortcut of the following code.
580 ///\name Query Functions
581 ///The result of the %Dijkstra algorithm can be obtained using these
583 ///Before the use of these functions,
584 ///either run() or start() must be called.
588 ///The distance of a node from the root.
590 ///Returns the distance of a node from the root.
591 ///\pre \ref run() must be called before using this function.
592 ///\warning If node \c v in unreachable from the root the return value
593 ///of this funcion is undefined.
594 Value dist(Node v) const { return (*distance)[v]; }
596 ///Returns the 'previous edge' of the shortest path tree.
598 ///For a node \c v it returns the 'previous edge' of the shortest path tree,
599 ///i.e. it returns the last edge of a shortest path from the root to \c
600 ///v. It is \ref INVALID
601 ///if \c v is unreachable from the root or if \c v=s. The
602 ///shortest path tree used here is equal to the shortest path tree used in
603 ///\ref predNode(Node v). \pre \ref run() must be called before using
605 ///\todo predEdge could be a better name.
606 Edge pred(Node v) const { return (*_pred)[v]; }
608 ///Returns the 'previous node' of the shortest path tree.
610 ///For a node \c v it returns the 'previous node' of the shortest path tree,
611 ///i.e. it returns the last but one node from a shortest path from the
612 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
613 ///\c v=s. The shortest path tree used here is equal to the shortest path
614 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
615 ///using this function.
616 Node predNode(Node v) const { return (*pred_node)[v]; }
618 ///Returns a reference to the NodeMap of distances.
620 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
621 ///be called before using this function.
622 const DistMap &distMap() const { return *distance;}
624 ///Returns a reference to the shortest path tree map.
626 ///Returns a reference to the NodeMap of the edges of the
627 ///shortest path tree.
628 ///\pre \ref run() must be called before using this function.
629 const PredMap &predMap() const { return *_pred;}
631 ///Returns a reference to the map of nodes of shortest paths.
633 ///Returns a reference to the NodeMap of the last but one nodes of the
634 ///shortest path tree.
635 ///\pre \ref run() must be called before using this function.
636 const PredNodeMap &predNodeMap() const { return *pred_node;}
638 ///Checks if a node is reachable from the root.
640 ///Returns \c true if \c v is reachable from the root.
641 ///\warning If the algorithm is started from multiple nodes,
642 ///this function may give false result for the source nodes.
643 ///\pre \ref run() must be called before using this function.
645 bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
650 /// Default traits used by \ref DijkstraWizard
652 /// To make it easier to use Dijkstra algorithm we have created a wizard class.
653 /// This \ref DijkstraWizard class needs default traits, as well as the \ref Dijkstra class.
654 /// The \ref DijkstraWizardBase is a class to be the default traits of the
655 /// \ref DijkstraWizard class.
656 template<class GR,class LM>
657 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
660 typedef DijkstraDefaultTraits<GR,LM> Base;
662 /// Pointer to the underlying graph.
664 /// Pointer to the length map
666 ///Pointer to the map of predecessors edges.
668 ///Pointer to the map of predecessors nodes.
670 ///Pointer to the map of distances.
672 ///Pointer to the source node.
675 /// Type of the nodes in the graph.
676 typedef typename Base::Graph::Node Node;
681 /// This constructor does not require parameters, therefore it initiates
682 /// all of the attributes to default values (0, INVALID).
683 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
684 _dist(0), _source(INVALID) {}
688 /// This constructor requires some parameters, listed in the parameters list.
689 /// Others are initiated to 0.
690 /// \param g is the initial value of \ref _g
691 /// \param l is the initial value of \ref _length
692 /// \param s is the initial value of \ref _source
693 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
694 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
695 _dist(0), _source((void *)&s) {}
699 /// A class to make easier the usage of Dijkstra algorithm
701 /// This class is created to make it easier to use Dijkstra algorithm.
702 /// It uses the functions and features of the plain \ref Dijkstra,
703 /// but it is much more simple to use it.
705 /// Simplicity means that the way to change the types defined
706 /// in the traits class is based on functions that returns the new class
707 /// and not on templatable built-in classes. When using the plain \ref Dijkstra
708 /// the new class with the modified type comes from the original class by using the ::
709 /// operator. In the case of \ref DijkstraWizard only a function have to be called and it will
710 /// return the needed class.
712 /// It does not have own \ref run method. When its \ref run method is called
713 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
716 class DijkstraWizard : public TR
720 ///The type of the underlying graph.
721 typedef typename TR::Graph Graph;
723 typedef typename Graph::Node Node;
725 typedef typename Graph::NodeIt NodeIt;
727 typedef typename Graph::Edge Edge;
729 typedef typename Graph::OutEdgeIt OutEdgeIt;
731 ///The type of the map that stores the edge lengths.
732 typedef typename TR::LengthMap LengthMap;
733 ///The type of the length of the edges.
734 typedef typename LengthMap::Value Value;
735 ///\brief The type of the map that stores the last
736 ///edges of the shortest paths.
737 typedef typename TR::PredMap PredMap;
738 ///\brief The type of the map that stores the last but one
739 ///nodes of the shortest paths.
740 typedef typename TR::PredNodeMap PredNodeMap;
741 ///The type of the map that stores the dists of the nodes.
742 typedef typename TR::DistMap DistMap;
744 ///The heap type used by the dijkstra algorithm.
745 typedef typename TR::Heap Heap;
748 DijkstraWizard() : TR() {}
750 /// Constructor that requires parameters.
752 /// Constructor that requires parameters.
753 /// These parameters will be the default values for the traits class.
754 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
758 DijkstraWizard(const TR &b) : TR(b) {}
762 ///Runs Dijkstra algorithm from a given node.
764 ///Runs Dijkstra algorithm from a given node.
765 ///The node can be given by the \ref source function.
768 if(_source==0) throw UninitializedParameter();
769 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
770 if(_pred) Dij.predMap(*(PredMap*)_pred);
771 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
772 if(_dist) Dij.distMap(*(DistMap*)_dist);
773 Dij.run(*(Node*)_source);
776 ///Runs Dijkstra algorithm from the given node.
778 ///Runs Dijkstra algorithm from the given node.
779 ///\param s is the given source.
787 struct DefPredMapBase : public Base {
789 static PredMap *createPredMap(const Graph &G) { return 0; };
790 DefPredMapBase(const Base &b) : Base(b) {}
793 /// \ref named-templ-param "Named parameter" function for setting PredMap type
795 /// \ref named-templ-param "Named parameter" function for setting PredMap type
798 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
801 return DijkstraWizard<DefPredMapBase<T> >(*this);
806 struct DefPredNodeMapBase : public Base {
807 typedef T PredNodeMap;
808 static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
809 DefPredNodeMapBase(const Base &b) : Base(b) {}
812 /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
814 /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
817 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
819 _predNode=(void *)&t;
820 return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
824 struct DefDistMapBase : public Base {
826 static DistMap *createDistMap(const Graph &G) { return 0; };
827 DefDistMapBase(const Base &b) : Base(b) {}
830 /// \ref named-templ-param "Named parameter" function for setting DistMap type
832 /// \ref named-templ-param "Named parameter" function for setting DistMap type
835 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
838 return DijkstraWizard<DefDistMapBase<T> >(*this);
841 /// Sets the source node, from which the Dijkstra algorithm runs.
843 /// Sets the source node, from which the Dijkstra algorithm runs.
844 /// \param s is the source node.
845 DijkstraWizard<TR> &source(Node s)
855 ///\todo Please document...
857 template<class GR, class LM>
858 DijkstraWizard<DijkstraWizardBase<GR,LM> >
859 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
861 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
866 } //END OF NAMESPACE LEMON