Added copyright header and description.
2 * lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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 ///\todo getPath() should be implemented! (also for BFS and DFS)
26 #include <lemon/list_graph.h>
27 #include <lemon/bin_heap.h>
28 #include <lemon/invalid.h>
29 #include <lemon/error.h>
30 #include <lemon/maps.h>
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 NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
89 // ///Instantiates a PredNodeMap.
91 // ///This function instantiates a \ref PredNodeMap.
92 // ///\param G is the graph, to which
93 // ///we would like to define the \ref PredNodeMap
94 // static PredNodeMap *createPredNodeMap(const GR &G)
96 // return new PredNodeMap();
99 ///The type of the map that stores whether a nodes is processed.
101 ///The type of the map that stores whether a nodes is processed.
102 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
103 ///By default it is a NullMap.
104 ///\todo If it is set to a real map,
105 ///Dijkstra::processed() should read this.
106 ///\todo named parameter to set this type, function to read and write.
107 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
108 ///Instantiates a ProcessedMap.
110 ///This function instantiates a \ref ProcessedMap.
111 ///\param g is the graph, to which
112 ///we would like to define the \ref ProcessedMap
114 static ProcessedMap *createProcessedMap(const GR &g)
116 static ProcessedMap *createProcessedMap(const GR &)
119 return new ProcessedMap();
121 ///The type of the map that stores the dists of the nodes.
123 ///The type of the map that stores the dists of the nodes.
124 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
126 typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
127 ///Instantiates a DistMap.
129 ///This function instantiates a \ref DistMap.
130 ///\param G is the graph, to which we would like to define the \ref DistMap
131 static DistMap *createDistMap(const GR &G)
133 return new DistMap(G);
137 ///%Dijkstra algorithm class.
139 /// \ingroup flowalgs
140 ///This class provides an efficient implementation of %Dijkstra algorithm.
141 ///The edge lengths are passed to the algorithm using a
142 ///\ref concept::ReadMap "ReadMap",
143 ///so it is easy to change it to any kind of length.
145 ///The type of the length is determined by the
146 ///\ref concept::ReadMap::Value "Value" of the length map.
148 ///It is also possible to change the underlying priority heap.
150 ///\param GR The graph type the algorithm runs on. The default value
151 ///is \ref ListGraph. The value of GR is not used directly by
152 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
153 ///\param LM This read-only EdgeMap determines the lengths of the
154 ///edges. It is read once for each edge, so the map may involve in
155 ///relatively time consuming process to compute the edge length if
156 ///it is necessary. The default map type is \ref
157 ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
158 ///of LM is not used directly by Dijkstra, it is only passed to \ref
159 ///DijkstraDefaultTraits. \param TR Traits class to set
160 ///various data types used by the algorithm. The default traits
161 ///class is \ref DijkstraDefaultTraits
162 ///"DijkstraDefaultTraits<GR,LM>". See \ref
163 ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
166 ///\author Jacint Szabo and Alpar Juttner
167 ///\todo A compare object would be nice.
170 template <typename GR,
174 template <typename GR=ListGraph,
175 typename LM=typename GR::template EdgeMap<int>,
176 typename TR=DijkstraDefaultTraits<GR,LM> >
181 * \brief \ref Exception for uninitialized parameters.
183 * This error represents problems in the initialization
184 * of the parameters of the algorithms.
186 class UninitializedParameter : public lemon::UninitializedParameter {
188 virtual const char* exceptionName() const {
189 return "lemon::Dijkstra::UninitializedParameter";
194 ///The type of the underlying graph.
195 typedef typename TR::Graph Graph;
197 typedef typename Graph::Node Node;
199 typedef typename Graph::NodeIt NodeIt;
201 typedef typename Graph::Edge Edge;
203 typedef typename Graph::OutEdgeIt OutEdgeIt;
205 ///The type of the length of the edges.
206 typedef typename TR::LengthMap::Value Value;
207 ///The type of the map that stores the edge lengths.
208 typedef typename TR::LengthMap LengthMap;
209 ///\brief The type of the map that stores the last
210 ///edges of the shortest paths.
211 typedef typename TR::PredMap PredMap;
212 // ///\brief The type of the map that stores the last but one
213 // ///nodes of the shortest paths.
214 // typedef typename TR::PredNodeMap PredNodeMap;
215 ///The type of the map indicating if a node is processed.
216 typedef typename TR::ProcessedMap ProcessedMap;
217 ///The type of the map that stores the dists of the nodes.
218 typedef typename TR::DistMap DistMap;
219 ///The heap type used by the dijkstra algorithm.
220 typedef typename TR::Heap Heap;
222 /// Pointer to the underlying graph.
224 /// Pointer to the length map
225 const LengthMap *length;
226 ///Pointer to the map of predecessors edges.
228 ///Indicates if \ref _pred is locally allocated (\c true) or not.
230 // ///Pointer to the map of predecessors nodes.
231 // PredNodeMap *_predNode;
232 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.
233 // bool local_predNode;
234 ///Pointer to the map of distances.
236 ///Indicates if \ref _dist is locally allocated (\c true) or not.
238 ///Pointer to the map of processed status of the nodes.
239 ProcessedMap *_processed;
240 ///Indicates if \ref _processed is locally allocated (\c true) or not.
241 bool local_processed;
243 // ///The source node of the last execution.
246 ///Creates the maps if necessary.
248 ///\todo Error if \c G or are \c NULL. What about \c length?
249 ///\todo Better memory allocation (instead of new).
254 _pred = Traits::createPredMap(*G);
257 // local_predNode = true;
258 // _predNode = Traits::createPredNodeMap(*G);
262 _dist = Traits::createDistMap(*G);
265 local_processed = true;
266 _processed = Traits::createProcessedMap(*G);
272 ///\name Named template parameters
277 struct DefPredMapTraits : public Traits {
279 static PredMap *createPredMap(const Graph &G)
281 throw UninitializedParameter();
284 ///\ref named-templ-param "Named parameter" for setting PredMap type
286 ///\ref named-templ-param "Named parameter" for setting PredMap type
289 class DefPredMap : public Dijkstra< Graph,
291 DefPredMapTraits<T> > { };
293 // template <class T>
294 // struct DefPredNodeMapTraits : public Traits {
295 // typedef T PredNodeMap;
296 // static PredNodeMap *createPredNodeMap(const Graph &G)
298 // throw UninitializedParameter();
301 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
303 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
305 // template <class T>
306 // class DefPredNodeMap : public Dijkstra< Graph,
308 // DefPredNodeMapTraits<T> > { };
311 struct DefDistMapTraits : public Traits {
313 static DistMap *createDistMap(const Graph &G)
315 throw UninitializedParameter();
318 ///\ref named-templ-param "Named parameter" for setting DistMap type
320 ///\ref named-templ-param "Named parameter" for setting DistMap type
323 class DefDistMap : public Dijkstra< Graph,
325 DefDistMapTraits<T> > { };
328 struct DefProcessedMapTraits : public Traits {
329 typedef T ProcessedMap;
330 static ProcessedMap *createProcessedMap(const Graph &G)
332 throw UninitializedParameter();
335 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
337 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
340 class DefProcessedMap : public Dijkstra< Graph,
342 DefProcessedMapTraits<T> > { };
344 struct DefGraphProcessedMapTraits : public Traits {
345 typedef typename Graph::template NodeMap<bool> ProcessedMap;
346 static ProcessedMap *createProcessedMap(const Graph &G)
348 return new ProcessedMap(G);
351 ///\brief \ref named-templ-param "Named parameter"
352 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
354 ///\ref named-templ-param "Named parameter"
355 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
356 ///If you don't set it explicitely, it will be automatically allocated.
358 class DefProcessedMapToBeDefaultMap :
359 public Dijkstra< Graph,
361 DefGraphProcessedMapTraits> { };
367 typename Graph::template NodeMap<int> _heap_map;
373 ///\param _G the graph the algorithm will run on.
374 ///\param _length the length map used by the algorithm.
375 Dijkstra(const Graph& _G, const LengthMap& _length) :
376 G(&_G), length(&_length),
377 _pred(NULL), local_pred(false),
378 // _predNode(NULL), local_predNode(false),
379 _dist(NULL), local_dist(false),
380 _processed(NULL), local_processed(false),
381 _heap_map(*G,-1),_heap(_heap_map)
387 if(local_pred) delete _pred;
388 // if(local_predNode) delete _predNode;
389 if(local_dist) delete _dist;
390 if(local_processed) delete _processed;
393 ///Sets the length map.
395 ///Sets the length map.
396 ///\return <tt> (*this) </tt>
397 Dijkstra &lengthMap(const LengthMap &m)
403 ///Sets the map storing the predecessor edges.
405 ///Sets the map storing the predecessor edges.
406 ///If you don't use this function before calling \ref run(),
407 ///it will allocate one. The destuctor deallocates this
408 ///automatically allocated map, of course.
409 ///\return <tt> (*this) </tt>
410 Dijkstra &predMap(PredMap &m)
420 // ///Sets the map storing the predecessor nodes.
422 // ///Sets the map storing the predecessor nodes.
423 // ///If you don't use this function before calling \ref run(),
424 // ///it will allocate one. The destuctor deallocates this
425 // ///automatically allocated map, of course.
426 // ///\return <tt> (*this) </tt>
427 // Dijkstra &predNodeMap(PredNodeMap &m)
429 // if(local_predNode) {
431 // local_predNode=false;
437 ///Sets the map storing the distances calculated by the algorithm.
439 ///Sets the map storing the distances calculated by the algorithm.
440 ///If you don't use this function before calling \ref run(),
441 ///it will allocate one. The destuctor deallocates this
442 ///automatically allocated map, of course.
443 ///\return <tt> (*this) </tt>
444 Dijkstra &distMap(DistMap &m)
455 void finalizeNodeData(Node v,Value dst)
457 _processed->set(v,true);
459 // if((*_pred)[v]!=INVALID)
460 // _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
464 ///\name Execution control
465 ///The simplest way to execute the algorithm is to use
466 ///one of the member functions called \c run(...).
468 ///If you need more control on the execution,
469 ///first you must call \ref init(), then you can add several source nodes
470 ///with \ref addSource().
471 ///Finally \ref start() will perform the actual path
476 ///Initializes the internal data structures.
478 ///Initializes the internal data structures.
480 ///\todo _heap_map's type could also be in the traits class.
481 ///\todo The heaps should be able to make themselves empty directly.
485 while(!_heap.empty()) _heap.pop();
486 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
487 _pred->set(u,INVALID);
488 // _predNode->set(u,INVALID);
489 _processed->set(u,false);
490 _heap_map.set(u,Heap::PRE_HEAP);
494 ///Adds a new source node.
496 ///Adds a new source node to the priority heap.
498 ///The optional second parameter is the initial distance of the node.
500 ///It checks if the node has already been added to the heap and
501 ///It is pushed to the heap only if either it was not in the heap
502 ///or the shortest path found till then is longer then \c dst.
503 void addSource(Node s,Value dst=0)
506 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
507 else if(_heap[s]<dst) {
509 _pred->set(s,INVALID);
513 ///Processes the next node in the priority heap
515 ///Processes the next node in the priority heap.
517 ///\return The processed node.
519 ///\warning The priority heap must not be empty!
520 Node processNextNode()
523 Value oldvalue=_heap[v];
525 finalizeNodeData(v,oldvalue);
527 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
529 switch(_heap.state(w)) {
531 _heap.push(w,oldvalue+(*length)[e]);
533 // _predNode->set(w,v);
536 if ( oldvalue+(*length)[e] < _heap[w] ) {
537 _heap.decrease(w, oldvalue+(*length)[e]);
539 // _predNode->set(w,v);
542 case Heap::POST_HEAP:
549 ///\brief Returns \c false if there are nodes
550 ///to be processed in the priority heap
552 ///Returns \c false if there are nodes
553 ///to be processed in the priority heap
554 bool emptyQueue() { return _heap.empty(); }
555 ///Returns the number of the nodes to be processed in the priority heap
557 ///Returns the number of the nodes to be processed in the priority heap
559 int queueSize() { return _heap.size(); }
561 ///Executes the algorithm.
563 ///Executes the algorithm.
565 ///\pre init() must be called and at least one node should be added
566 ///with addSource() before using this function.
568 ///This method runs the %Dijkstra algorithm from the root node(s)
571 ///shortest path to each node. The algorithm computes
572 ///- The shortest path tree.
573 ///- The distance of each node from the root(s).
577 while ( !_heap.empty() ) processNextNode();
580 ///Executes the algorithm until \c dest is reached.
582 ///Executes the algorithm until \c dest is reached.
584 ///\pre init() must be called and at least one node should be added
585 ///with addSource() before using this function.
587 ///This method runs the %Dijkstra algorithm from the root node(s)
590 ///shortest path to \c dest. The algorithm computes
591 ///- The shortest path to \c dest.
592 ///- The distance of \c dest from the root(s).
594 void start(Node dest)
596 while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
597 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
600 ///Executes the algorithm until a condition is met.
602 ///Executes the algorithm until a condition is met.
604 ///\pre init() must be called and at least one node should be added
605 ///with addSource() before using this function.
607 ///\param nm must be a bool (or convertible) node map. The algorithm
608 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
609 template<class NodeBoolMap>
610 void start(const NodeBoolMap &nm)
612 while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
613 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
616 ///Runs %Dijkstra algorithm from node \c s.
618 ///This method runs the %Dijkstra algorithm from a root node \c s
621 ///shortest path to each node. The algorithm computes
622 ///- The shortest path tree.
623 ///- The distance of each node from the root.
625 ///\note d.run(s) is just a shortcut of the following code.
637 ///Finds the shortest path between \c s and \c t.
639 ///Finds the shortest path between \c s and \c t.
641 ///\return The length of the shortest s---t path if there exists one,
643 ///\note Apart from the return value, d.run(s) is
644 ///just a shortcut of the following code.
650 Value run(Node s,Node t) {
654 return (*_pred)[t]==INVALID?0:(*_dist)[t];
659 ///\name Query Functions
660 ///The result of the %Dijkstra algorithm can be obtained using these
662 ///Before the use of these functions,
663 ///either run() or start() must be called.
667 ///Copies the shortest path to \c t into \c p
669 ///This function copies the shortest path to \c t into \c p.
670 ///If it \c t is a source itself or unreachable, then it does not
672 ///\todo Is it the right way to handle unreachable nodes?
673 ///\return Returns \c true if a path to \c t was actually copied to \c p,
674 ///\c false otherwise.
677 bool getPath(P &p,Node t)
681 typename P::Builder b(p);
682 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
683 b.pushFront(pred(t));
690 ///The distance of a node from the root.
692 ///Returns the distance of a node from the root.
693 ///\pre \ref run() must be called before using this function.
694 ///\warning If node \c v in unreachable from the root the return value
695 ///of this funcion is undefined.
696 Value dist(Node v) const { return (*_dist)[v]; }
698 ///Returns the 'previous edge' of the shortest path tree.
700 ///For a node \c v it returns the 'previous edge' of the shortest path tree,
701 ///i.e. it returns the last edge of a shortest path from the root to \c
702 ///v. It is \ref INVALID
703 ///if \c v is unreachable from the root or if \c v=s. The
704 ///shortest path tree used here is equal to the shortest path tree used in
705 ///\ref predNode(Node v). \pre \ref run() must be called before using
707 ///\todo predEdge could be a better name.
708 Edge pred(Node v) const { return (*_pred)[v]; }
710 ///Returns the 'previous node' of the shortest path tree.
712 ///For a node \c v it returns the 'previous node' of the shortest path tree,
713 ///i.e. it returns the last but one node from a shortest path from the
714 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
715 ///\c v=s. The shortest path tree used here is equal to the shortest path
716 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
717 ///using this function.
718 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
719 G->source((*_pred)[v]); }
721 ///Returns a reference to the NodeMap of distances.
723 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
724 ///be called before using this function.
725 const DistMap &distMap() const { return *_dist;}
727 ///Returns a reference to the shortest path tree map.
729 ///Returns a reference to the NodeMap of the edges of the
730 ///shortest path tree.
731 ///\pre \ref run() must be called before using this function.
732 const PredMap &predMap() const { return *_pred;}
734 // ///Returns a reference to the map of nodes of shortest paths.
736 // ///Returns a reference to the NodeMap of the last but one nodes of the
737 // ///shortest path tree.
738 // ///\pre \ref run() must be called before using this function.
739 // const PredNodeMap &predNodeMap() const { return *_predNode;}
741 ///Checks if a node is reachable from the root.
743 ///Returns \c true if \c v is reachable from the root.
744 ///\warning The source nodes are inditated as unreached.
745 ///\pre \ref run() must be called before using this function.
747 bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
756 ///Default traits class of Dijkstra function.
758 ///Default traits class of Dijkstra function.
759 ///\param GR Graph type.
760 ///\param LM Type of length map.
761 template<class GR, class LM>
762 struct DijkstraWizardDefaultTraits
764 ///The graph type the algorithm runs on.
766 ///The type of the map that stores the edge lengths.
768 ///The type of the map that stores the edge lengths.
769 ///It must meet the \ref concept::ReadMap "ReadMap" concept.
770 typedef LM LengthMap;
771 //The type of the length of the edges.
772 typedef typename LM::Value Value;
773 ///The heap type used by Dijkstra algorithm.
775 ///The heap type used by Dijkstra algorithm.
779 typedef BinHeap<typename Graph::Node,
781 typename GR::template NodeMap<int>,
782 std::less<Value> > Heap;
784 ///\brief The type of the map that stores the last
785 ///edges of the shortest paths.
787 ///The type of the map that stores the last
788 ///edges of the shortest paths.
789 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
791 typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
792 ///Instantiates a PredMap.
794 ///This function instantiates a \ref PredMap.
795 ///\param g is the graph, to which we would like to define the PredMap.
796 ///\todo The graph alone may be insufficient for the initialization
798 static PredMap *createPredMap(const GR &g)
800 static PredMap *createPredMap(const GR &)
803 return new PredMap();
805 ///The type of the map that stores whether a nodes is processed.
807 ///The type of the map that stores whether a nodes is processed.
808 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
809 ///By default it is a NullMap.
810 ///\todo If it is set to a real map,
811 ///Dijkstra::processed() should read this.
812 ///\todo named parameter to set this type, function to read and write.
813 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
814 ///Instantiates a ProcessedMap.
816 ///This function instantiates a \ref ProcessedMap.
817 ///\param g is the graph, to which
818 ///we would like to define the \ref ProcessedMap
820 static ProcessedMap *createProcessedMap(const GR &g)
822 static ProcessedMap *createProcessedMap(const GR &)
825 return new ProcessedMap();
827 ///The type of the map that stores the dists of the nodes.
829 ///The type of the map that stores the dists of the nodes.
830 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
832 typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
833 ///Instantiates a DistMap.
835 ///This function instantiates a \ref DistMap.
836 ///\param g is the graph, to which we would like to define the \ref DistMap
838 static DistMap *createDistMap(const GR &g)
840 static DistMap *createDistMap(const GR &)
843 return new DistMap();
847 /// Default traits used by \ref DijkstraWizard
849 /// To make it easier to use Dijkstra algorithm
850 ///we have created a wizard class.
851 /// This \ref DijkstraWizard class needs default traits,
852 ///as well as the \ref Dijkstra class.
853 /// The \ref DijkstraWizardBase is a class to be the default traits of the
854 /// \ref DijkstraWizard class.
855 /// \todo More named parameters are required...
856 template<class GR,class LM>
857 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
860 typedef DijkstraWizardDefaultTraits<GR,LM> Base;
862 /// Type of the nodes in the graph.
863 typedef typename Base::Graph::Node Node;
865 /// Pointer to the underlying graph.
867 /// Pointer to the length map
869 ///Pointer to the map of predecessors edges.
871 // ///Pointer to the map of predecessors nodes.
873 ///Pointer to the map of distances.
875 ///Pointer to the source node.
881 /// This constructor does not require parameters, therefore it initiates
882 /// all of the attributes to default values (0, INVALID).
883 DijkstraWizardBase() : _g(0), _length(0), _pred(0),
885 _dist(0), _source(INVALID) {}
889 /// This constructor requires some parameters,
890 /// listed in the parameters list.
891 /// Others are initiated to 0.
892 /// \param g is the initial value of \ref _g
893 /// \param l is the initial value of \ref _length
894 /// \param s is the initial value of \ref _source
895 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
896 _g((void *)&g), _length((void *)&l), _pred(0),
898 _dist(0), _source(s) {}
902 /// A class to make the usage of Dijkstra algorithm easier
904 /// This class is created to make it easier to use Dijkstra algorithm.
905 /// It uses the functions and features of the plain \ref Dijkstra,
906 /// but it is much simpler to use it.
908 /// Simplicity means that the way to change the types defined
909 /// in the traits class is based on functions that returns the new class
910 /// and not on templatable built-in classes.
911 /// When using the plain \ref Dijkstra
912 /// the new class with the modified type comes from
913 /// the original class by using the ::
914 /// operator. In the case of \ref DijkstraWizard only
915 /// a function have to be called and it will
916 /// return the needed class.
918 /// It does not have own \ref run method. When its \ref run method is called
919 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
922 class DijkstraWizard : public TR
926 ///The type of the underlying graph.
927 typedef typename TR::Graph Graph;
929 typedef typename Graph::Node Node;
931 typedef typename Graph::NodeIt NodeIt;
933 typedef typename Graph::Edge Edge;
935 typedef typename Graph::OutEdgeIt OutEdgeIt;
937 ///The type of the map that stores the edge lengths.
938 typedef typename TR::LengthMap LengthMap;
939 ///The type of the length of the edges.
940 typedef typename LengthMap::Value Value;
941 ///\brief The type of the map that stores the last
942 ///edges of the shortest paths.
943 typedef typename TR::PredMap PredMap;
944 // ///\brief The type of the map that stores the last but one
945 // ///nodes of the shortest paths.
946 // typedef typename TR::PredNodeMap PredNodeMap;
947 ///The type of the map that stores the dists of the nodes.
948 typedef typename TR::DistMap DistMap;
950 ///The heap type used by the dijkstra algorithm.
951 typedef typename TR::Heap Heap;
954 DijkstraWizard() : TR() {}
956 /// Constructor that requires parameters.
958 /// Constructor that requires parameters.
959 /// These parameters will be the default values for the traits class.
960 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
964 DijkstraWizard(const TR &b) : TR(b) {}
968 ///Runs Dijkstra algorithm from a given node.
970 ///Runs Dijkstra algorithm from a given node.
971 ///The node can be given by the \ref source function.
974 if(Base::_source==INVALID) throw UninitializedParameter();
975 Dijkstra<Graph,LengthMap,TR>
976 dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
977 if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred);
978 // if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
979 if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist);
980 dij.run(Base::_source);
983 ///Runs Dijkstra algorithm from the given node.
985 ///Runs Dijkstra algorithm from the given node.
986 ///\param s is the given source.
994 struct DefPredMapBase : public Base {
996 static PredMap *createPredMap(const Graph &) { return 0; };
997 DefPredMapBase(const TR &b) : TR(b) {}
1000 ///\brief \ref named-templ-param "Named parameter"
1001 ///function for setting PredMap type
1003 /// \ref named-templ-param "Named parameter"
1004 ///function for setting PredMap type
1007 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1009 Base::_pred=(void *)&t;
1010 return DijkstraWizard<DefPredMapBase<T> >(*this);
1014 // template<class T>
1015 // struct DefPredNodeMapBase : public Base {
1016 // typedef T PredNodeMap;
1017 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1018 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1021 // ///\brief \ref named-templ-param "Named parameter"
1022 // ///function for setting PredNodeMap type
1024 // /// \ref named-templ-param "Named parameter"
1025 // ///function for setting PredNodeMap type
1027 // template<class T>
1028 // DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1030 // Base::_predNode=(void *)&t;
1031 // return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
1035 struct DefDistMapBase : public Base {
1037 static DistMap *createDistMap(const Graph &) { return 0; };
1038 DefDistMapBase(const TR &b) : TR(b) {}
1041 ///\brief \ref named-templ-param "Named parameter"
1042 ///function for setting DistMap type
1044 /// \ref named-templ-param "Named parameter"
1045 ///function for setting DistMap type
1048 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1050 Base::_dist=(void *)&t;
1051 return DijkstraWizard<DefDistMapBase<T> >(*this);
1054 /// Sets the source node, from which the Dijkstra algorithm runs.
1056 /// Sets the source node, from which the Dijkstra algorithm runs.
1057 /// \param s is the source node.
1058 DijkstraWizard<TR> &source(Node s)
1066 ///Function type interface for Dijkstra algorithm.
1068 /// \ingroup flowalgs
1069 ///Function type interface for Dijkstra algorithm.
1071 ///This function also has several
1072 ///\ref named-templ-func-param "named parameters",
1073 ///they are declared as the members of class \ref DijkstraWizard.
1075 ///example shows how to use these parameters.
1077 /// dijkstra(g,length,source).predMap(preds).run();
1079 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1080 ///to the end of the parameter list.
1081 ///\sa DijkstraWizard
1083 template<class GR, class LM>
1084 DijkstraWizard<DijkstraWizardBase<GR,LM> >
1085 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1087 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1090 } //END OF NAMESPACE LEMON