An icc warning resolved.
2 * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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 ///\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
113 static ProcessedMap *createProcessedMap(const GR &G)
115 return new ProcessedMap();
117 ///The type of the map that stores the dists of the nodes.
119 ///The type of the map that stores the dists of the nodes.
120 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
122 typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
123 ///Instantiates a DistMap.
125 ///This function instantiates a \ref DistMap.
126 ///\param G is the graph, to which we would like to define the \ref DistMap
127 static DistMap *createDistMap(const GR &G)
129 return new DistMap(G);
133 ///%Dijkstra algorithm class.
135 /// \ingroup flowalgs
136 ///This class provides an efficient implementation of %Dijkstra algorithm.
137 ///The edge lengths are passed to the algorithm using a
138 ///\ref concept::ReadMap "ReadMap",
139 ///so it is easy to change it to any kind of length.
141 ///The type of the length is determined by the
142 ///\ref concept::ReadMap::Value "Value" of the length map.
144 ///It is also possible to change the underlying priority heap.
146 ///\param GR The graph type the algorithm runs on. The default value
147 ///is \ref ListGraph. The value of GR is not used directly by
148 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
149 ///\param LM This read-only EdgeMap determines the lengths of the
150 ///edges. It is read once for each edge, so the map may involve in
151 ///relatively time consuming process to compute the edge length if
152 ///it is necessary. The default map type is \ref
153 ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
154 ///of LM is not used directly by Dijkstra, it is only passed to \ref
155 ///DijkstraDefaultTraits. \param TR Traits class to set
156 ///various data types used by the algorithm. The default traits
157 ///class is \ref DijkstraDefaultTraits
158 ///"DijkstraDefaultTraits<GR,LM>". See \ref
159 ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
162 ///\author Jacint Szabo and Alpar Juttner
163 ///\todo A compare object would be nice.
166 template <typename GR,
170 template <typename GR=ListGraph,
171 typename LM=typename GR::template EdgeMap<int>,
172 typename TR=DijkstraDefaultTraits<GR,LM> >
177 * \brief \ref Exception for uninitialized parameters.
179 * This error represents problems in the initialization
180 * of the parameters of the algorithms.
182 class UninitializedParameter : public lemon::UninitializedParameter {
184 virtual const char* exceptionName() const {
185 return "lemon::Dijkstra::UninitializedParameter";
190 ///The type of the underlying graph.
191 typedef typename TR::Graph Graph;
193 typedef typename Graph::Node Node;
195 typedef typename Graph::NodeIt NodeIt;
197 typedef typename Graph::Edge Edge;
199 typedef typename Graph::OutEdgeIt OutEdgeIt;
201 ///The type of the length of the edges.
202 typedef typename TR::LengthMap::Value Value;
203 ///The type of the map that stores the edge lengths.
204 typedef typename TR::LengthMap LengthMap;
205 ///\brief The type of the map that stores the last
206 ///edges of the shortest paths.
207 typedef typename TR::PredMap PredMap;
208 // ///\brief The type of the map that stores the last but one
209 // ///nodes of the shortest paths.
210 // typedef typename TR::PredNodeMap PredNodeMap;
211 ///The type of the map indicating if a node is processed.
212 typedef typename TR::ProcessedMap ProcessedMap;
213 ///The type of the map that stores the dists of the nodes.
214 typedef typename TR::DistMap DistMap;
215 ///The heap type used by the dijkstra algorithm.
216 typedef typename TR::Heap Heap;
218 /// Pointer to the underlying graph.
220 /// Pointer to the length map
221 const LengthMap *length;
222 ///Pointer to the map of predecessors edges.
224 ///Indicates if \ref _pred is locally allocated (\c true) or not.
226 // ///Pointer to the map of predecessors nodes.
227 // PredNodeMap *_predNode;
228 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.
229 // bool local_predNode;
230 ///Pointer to the map of distances.
232 ///Indicates if \ref _dist is locally allocated (\c true) or not.
234 ///Pointer to the map of processed status of the nodes.
235 ProcessedMap *_processed;
236 ///Indicates if \ref _processed is locally allocated (\c true) or not.
237 bool local_processed;
239 // ///The source node of the last execution.
242 ///Creates the maps if necessary.
244 ///\todo Error if \c G or are \c NULL. What about \c length?
245 ///\todo Better memory allocation (instead of new).
250 _pred = Traits::createPredMap(*G);
253 // local_predNode = true;
254 // _predNode = Traits::createPredNodeMap(*G);
258 _dist = Traits::createDistMap(*G);
261 local_processed = true;
262 _processed = Traits::createProcessedMap(*G);
268 ///\name Named template parameters
273 struct DefPredMapTraits : public Traits {
275 static PredMap *createPredMap(const Graph &G)
277 throw UninitializedParameter();
280 ///\ref named-templ-param "Named parameter" for setting PredMap type
282 ///\ref named-templ-param "Named parameter" for setting PredMap type
285 class DefPredMap : public Dijkstra< Graph,
287 DefPredMapTraits<T> > { };
289 // template <class T>
290 // struct DefPredNodeMapTraits : public Traits {
291 // typedef T PredNodeMap;
292 // static PredNodeMap *createPredNodeMap(const Graph &G)
294 // throw UninitializedParameter();
297 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
299 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
301 // template <class T>
302 // class DefPredNodeMap : public Dijkstra< Graph,
304 // DefPredNodeMapTraits<T> > { };
307 struct DefDistMapTraits : public Traits {
309 static DistMap *createDistMap(const Graph &G)
311 throw UninitializedParameter();
314 ///\ref named-templ-param "Named parameter" for setting DistMap type
316 ///\ref named-templ-param "Named parameter" for setting DistMap type
319 class DefDistMap : public Dijkstra< Graph,
321 DefDistMapTraits<T> > { };
324 struct DefProcessedMapTraits : public Traits {
325 typedef T ProcessedMap;
326 static ProcessedMap *createProcessedMap(const Graph &G)
328 throw UninitializedParameter();
331 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
333 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
336 class DefProcessedMap : public Dijkstra< Graph,
338 DefProcessedMapTraits<T> > { };
340 struct DefGraphProcessedMapTraits : public Traits {
341 typedef typename Graph::template NodeMap<bool> ProcessedMap;
342 static ProcessedMap *createProcessedMap(const Graph &G)
344 return new ProcessedMap(G);
347 ///\brief \ref named-templ-param "Named parameter"
348 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
350 ///\ref named-templ-param "Named parameter"
351 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
352 ///If you don't set it explicitely, it will be automatically allocated.
354 class DefProcessedMapToBeDefaultMap :
355 public Dijkstra< Graph,
357 DefGraphProcessedMapTraits> { };
363 typename Graph::template NodeMap<int> _heap_map;
369 ///\param _G the graph the algorithm will run on.
370 ///\param _length the length map used by the algorithm.
371 Dijkstra(const Graph& _G, const LengthMap& _length) :
372 G(&_G), length(&_length),
373 _pred(NULL), local_pred(false),
374 // _predNode(NULL), local_predNode(false),
375 _dist(NULL), local_dist(false),
376 _processed(NULL), local_processed(false),
377 _heap_map(*G,-1),_heap(_heap_map)
383 if(local_pred) delete _pred;
384 // if(local_predNode) delete _predNode;
385 if(local_dist) delete _dist;
386 if(local_processed) delete _processed;
389 ///Sets the length map.
391 ///Sets the length map.
392 ///\return <tt> (*this) </tt>
393 Dijkstra &lengthMap(const LengthMap &m)
399 ///Sets the map storing the predecessor edges.
401 ///Sets the map storing the predecessor edges.
402 ///If you don't use this function before calling \ref run(),
403 ///it will allocate one. The destuctor deallocates this
404 ///automatically allocated map, of course.
405 ///\return <tt> (*this) </tt>
406 Dijkstra &predMap(PredMap &m)
416 // ///Sets the map storing the predecessor nodes.
418 // ///Sets the map storing the predecessor nodes.
419 // ///If you don't use this function before calling \ref run(),
420 // ///it will allocate one. The destuctor deallocates this
421 // ///automatically allocated map, of course.
422 // ///\return <tt> (*this) </tt>
423 // Dijkstra &predNodeMap(PredNodeMap &m)
425 // if(local_predNode) {
427 // local_predNode=false;
433 ///Sets the map storing the distances calculated by the algorithm.
435 ///Sets the map storing the distances calculated by the algorithm.
436 ///If you don't use this function before calling \ref run(),
437 ///it will allocate one. The destuctor deallocates this
438 ///automatically allocated map, of course.
439 ///\return <tt> (*this) </tt>
440 Dijkstra &distMap(DistMap &m)
451 void finalizeNodeData(Node v,Value dst)
453 _processed->set(v,true);
455 // if((*_pred)[v]!=INVALID)
456 // _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
460 ///\name Execution control
461 ///The simplest way to execute the algorithm is to use
462 ///one of the member functions called \c run(...).
464 ///If you need more control on the execution,
465 ///first you must call \ref init(), then you can add several source nodes
466 ///with \ref addSource().
467 ///Finally \ref start() will perform the actual path
472 ///Initializes the internal data structures.
474 ///Initializes the internal data structures.
476 ///\todo _heap_map's type could also be in the traits class.
477 ///\todo The heaps should be able to make themselves empty directly.
481 while(!_heap.empty()) _heap.pop();
482 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
483 _pred->set(u,INVALID);
484 // _predNode->set(u,INVALID);
485 _processed->set(u,false);
486 _heap_map.set(u,Heap::PRE_HEAP);
490 ///Adds a new source node.
492 ///Adds a new source node to the priority heap.
494 ///The optional second parameter is the initial distance of the node.
496 ///It checks if the node has already been added to the heap and
497 ///It is pushed to the heap only if either it was not in the heap
498 ///or the shortest path found till then is longer then \c dst.
499 void addSource(Node s,Value dst=0)
502 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
503 else if(_heap[s]<dst) {
505 _pred->set(s,INVALID);
509 ///Processes the next node in the priority heap
511 ///Processes the next node in the priority heap.
513 ///\warning The priority heap must not be empty!
514 void processNextNode()
517 Value oldvalue=_heap[v];
519 finalizeNodeData(v,oldvalue);
521 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
523 switch(_heap.state(w)) {
525 _heap.push(w,oldvalue+(*length)[e]);
527 // _predNode->set(w,v);
530 if ( oldvalue+(*length)[e] < _heap[w] ) {
531 _heap.decrease(w, oldvalue+(*length)[e]);
533 // _predNode->set(w,v);
536 case Heap::POST_HEAP:
542 ///\brief Returns \c false if there are nodes
543 ///to be processed in the priority heap
545 ///Returns \c false if there are nodes
546 ///to be processed in the priority heap
547 bool emptyQueue() { return _heap.empty(); }
548 ///Returns the number of the nodes to be processed in the priority heap
550 ///Returns the number of the nodes to be processed in the priority heap
552 int queueSize() { return _heap.size(); }
554 ///Executes the algorithm.
556 ///Executes the algorithm.
558 ///\pre init() must be called and at least one node should be added
559 ///with addSource() before using this function.
561 ///This method runs the %Dijkstra algorithm from the root node(s)
564 ///shortest path to each node. The algorithm computes
565 ///- The shortest path tree.
566 ///- The distance of each node from the root(s).
570 while ( !_heap.empty() ) processNextNode();
573 ///Executes the algorithm until \c dest is reached.
575 ///Executes the algorithm until \c dest is reached.
577 ///\pre init() must be called and at least one node should be added
578 ///with addSource() before using this function.
580 ///This method runs the %Dijkstra algorithm from the root node(s)
583 ///shortest path to \c dest. The algorithm computes
584 ///- The shortest path to \c dest.
585 ///- The distance of \c dest from the root(s).
587 void start(Node dest)
589 while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
590 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
593 ///Executes the algorithm until a condition is met.
595 ///Executes the algorithm until a condition is met.
597 ///\pre init() must be called and at least one node should be added
598 ///with addSource() before using this function.
600 ///\param nm must be a bool (or convertible) node map. The algorithm
601 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
603 void start(const NM &nm)
605 while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
606 if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
609 ///Runs %Dijkstra algorithm from node \c s.
611 ///This method runs the %Dijkstra algorithm from a root node \c s
614 ///shortest path to each node. The algorithm computes
615 ///- The shortest path tree.
616 ///- The distance of each node from the root.
618 ///\note d.run(s) is just a shortcut of the following code.
630 ///Finds the shortest path between \c s and \c t.
632 ///Finds the shortest path between \c s and \c t.
634 ///\return The length of the shortest s---t path if there exists one,
636 ///\note Apart from the return value, d.run(s) is
637 ///just a shortcut of the following code.
643 Value run(Node s,Node t) {
647 return (*_pred)[t]==INVALID?0:(*_dist)[t];
652 ///\name Query Functions
653 ///The result of the %Dijkstra algorithm can be obtained using these
655 ///Before the use of these functions,
656 ///either run() or start() must be called.
660 ///Copies the shortest path to \c t into \c p
662 ///This function copies the shortest path to \c t into \c p.
663 ///If it \c \t is a source itself or unreachable, then it does not
665 ///\todo Is it the right way to handle unreachable nodes?
666 ///\return Returns \c true if a path to \c t was actually copied to \c p,
667 ///\c false otherwise.
670 bool getPath(P &p,Node t)
674 typename P::Builder b(p);
675 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
676 b.pushFront(pred(t));
683 ///The distance of a node from the root.
685 ///Returns the distance of a node from the root.
686 ///\pre \ref run() must be called before using this function.
687 ///\warning If node \c v in unreachable from the root the return value
688 ///of this funcion is undefined.
689 Value dist(Node v) const { return (*_dist)[v]; }
691 ///Returns the 'previous edge' of the shortest path tree.
693 ///For a node \c v it returns the 'previous edge' of the shortest path tree,
694 ///i.e. it returns the last edge of a shortest path from the root to \c
695 ///v. It is \ref INVALID
696 ///if \c v is unreachable from the root or if \c v=s. The
697 ///shortest path tree used here is equal to the shortest path tree used in
698 ///\ref predNode(Node v). \pre \ref run() must be called before using
700 ///\todo predEdge could be a better name.
701 Edge pred(Node v) const { return (*_pred)[v]; }
703 ///Returns the 'previous node' of the shortest path tree.
705 ///For a node \c v it returns the 'previous node' of the shortest path tree,
706 ///i.e. it returns the last but one node from a shortest path from the
707 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
708 ///\c v=s. The shortest path tree used here is equal to the shortest path
709 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
710 ///using this function.
711 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
712 G->source((*_pred)[v]); }
714 ///Returns a reference to the NodeMap of distances.
716 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
717 ///be called before using this function.
718 const DistMap &distMap() const { return *_dist;}
720 ///Returns a reference to the shortest path tree map.
722 ///Returns a reference to the NodeMap of the edges of the
723 ///shortest path tree.
724 ///\pre \ref run() must be called before using this function.
725 const PredMap &predMap() const { return *_pred;}
727 // ///Returns a reference to the map of nodes of shortest paths.
729 // ///Returns a reference to the NodeMap of the last but one nodes of the
730 // ///shortest path tree.
731 // ///\pre \ref run() must be called before using this function.
732 // const PredNodeMap &predNodeMap() const { return *_predNode;}
734 ///Checks if a node is reachable from the root.
736 ///Returns \c true if \c v is reachable from the root.
737 ///\warning The source nodes are inditated as unreached.
738 ///\pre \ref run() must be called before using this function.
740 bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
749 ///Default traits class of Dijkstra function.
751 ///Default traits class of Dijkstra function.
752 ///\param GR Graph type.
753 ///\param LM Type of length map.
754 template<class GR, class LM>
755 struct DijkstraWizardDefaultTraits
757 ///The graph type the algorithm runs on.
759 ///The type of the map that stores the edge lengths.
761 ///The type of the map that stores the edge lengths.
762 ///It must meet the \ref concept::ReadMap "ReadMap" concept.
763 typedef LM LengthMap;
764 //The type of the length of the edges.
765 typedef typename LM::Value Value;
766 ///The heap type used by Dijkstra algorithm.
768 ///The heap type used by Dijkstra algorithm.
772 typedef BinHeap<typename Graph::Node,
774 typename GR::template NodeMap<int>,
775 std::less<Value> > Heap;
777 ///\brief The type of the map that stores the last
778 ///edges of the shortest paths.
780 ///The type of the map that stores the last
781 ///edges of the shortest paths.
782 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
784 typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
785 ///Instantiates a PredMap.
787 ///This function instantiates a \ref PredMap.
788 ///\param G is the graph, to which we would like to define the PredMap.
789 ///\todo The graph alone may be insufficient for the initialization
790 static PredMap *createPredMap(const GR &G)
792 return new PredMap();
794 ///The type of the map that stores whether a nodes is processed.
796 ///The type of the map that stores whether a nodes is processed.
797 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
798 ///By default it is a NullMap.
799 ///\todo If it is set to a real map,
800 ///Dijkstra::processed() should read this.
801 ///\todo named parameter to set this type, function to read and write.
802 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
803 ///Instantiates a ProcessedMap.
805 ///This function instantiates a \ref ProcessedMap.
806 ///\param G is the graph, to which
807 ///we would like to define the \ref ProcessedMap
808 static ProcessedMap *createProcessedMap(const GR &G)
810 return new ProcessedMap();
812 ///The type of the map that stores the dists of the nodes.
814 ///The type of the map that stores the dists of the nodes.
815 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
817 typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
818 ///Instantiates a DistMap.
820 ///This function instantiates a \ref DistMap.
821 ///\param G is the graph, to which we would like to define the \ref DistMap
822 static DistMap *createDistMap(const GR &G)
824 return new DistMap();
828 /// Default traits used by \ref DijkstraWizard
830 /// To make it easier to use Dijkstra algorithm
831 ///we have created a wizard class.
832 /// This \ref DijkstraWizard class needs default traits,
833 ///as well as the \ref Dijkstra class.
834 /// The \ref DijkstraWizardBase is a class to be the default traits of the
835 /// \ref DijkstraWizard class.
836 /// \todo More named parameters are required...
837 template<class GR,class LM>
838 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
841 typedef DijkstraWizardDefaultTraits<GR,LM> Base;
843 /// Type of the nodes in the graph.
844 typedef typename Base::Graph::Node Node;
846 /// Pointer to the underlying graph.
848 /// Pointer to the length map
850 ///Pointer to the map of predecessors edges.
852 // ///Pointer to the map of predecessors nodes.
854 ///Pointer to the map of distances.
856 ///Pointer to the source node.
862 /// This constructor does not require parameters, therefore it initiates
863 /// all of the attributes to default values (0, INVALID).
864 DijkstraWizardBase() : _g(0), _length(0), _pred(0),
866 _dist(0), _source(INVALID) {}
870 /// This constructor requires some parameters,
871 /// listed in the parameters list.
872 /// Others are initiated to 0.
873 /// \param g is the initial value of \ref _g
874 /// \param l is the initial value of \ref _length
875 /// \param s is the initial value of \ref _source
876 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
877 _g((void *)&g), _length((void *)&l), _pred(0),
879 _dist(0), _source(s) {}
883 /// A class to make the usage of Dijkstra algorithm easier
885 /// This class is created to make it easier to use Dijkstra algorithm.
886 /// It uses the functions and features of the plain \ref Dijkstra,
887 /// but it is much simpler to use it.
889 /// Simplicity means that the way to change the types defined
890 /// in the traits class is based on functions that returns the new class
891 /// and not on templatable built-in classes.
892 /// When using the plain \ref Dijkstra
893 /// the new class with the modified type comes from
894 /// the original class by using the ::
895 /// operator. In the case of \ref DijkstraWizard only
896 /// a function have to be called and it will
897 /// return the needed class.
899 /// It does not have own \ref run method. When its \ref run method is called
900 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
903 class DijkstraWizard : public TR
907 ///The type of the underlying graph.
908 typedef typename TR::Graph Graph;
910 typedef typename Graph::Node Node;
912 typedef typename Graph::NodeIt NodeIt;
914 typedef typename Graph::Edge Edge;
916 typedef typename Graph::OutEdgeIt OutEdgeIt;
918 ///The type of the map that stores the edge lengths.
919 typedef typename TR::LengthMap LengthMap;
920 ///The type of the length of the edges.
921 typedef typename LengthMap::Value Value;
922 ///\brief The type of the map that stores the last
923 ///edges of the shortest paths.
924 typedef typename TR::PredMap PredMap;
925 // ///\brief The type of the map that stores the last but one
926 // ///nodes of the shortest paths.
927 // typedef typename TR::PredNodeMap PredNodeMap;
928 ///The type of the map that stores the dists of the nodes.
929 typedef typename TR::DistMap DistMap;
931 ///The heap type used by the dijkstra algorithm.
932 typedef typename TR::Heap Heap;
935 DijkstraWizard() : TR() {}
937 /// Constructor that requires parameters.
939 /// Constructor that requires parameters.
940 /// These parameters will be the default values for the traits class.
941 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
945 DijkstraWizard(const TR &b) : TR(b) {}
949 ///Runs Dijkstra algorithm from a given node.
951 ///Runs Dijkstra algorithm from a given node.
952 ///The node can be given by the \ref source function.
955 if(Base::_source==INVALID) throw UninitializedParameter();
956 Dijkstra<Graph,LengthMap,TR>
957 Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
958 if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred);
959 // if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
960 if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist);
961 Dij.run(Base::_source);
964 ///Runs Dijkstra algorithm from the given node.
966 ///Runs Dijkstra algorithm from the given node.
967 ///\param s is the given source.
975 struct DefPredMapBase : public Base {
977 static PredMap *createPredMap(const Graph &G) { return 0; };
978 DefPredMapBase(const TR &b) : TR(b) {}
981 ///\brief \ref named-templ-param "Named parameter"
982 ///function for setting PredMap type
984 /// \ref named-templ-param "Named parameter"
985 ///function for setting PredMap type
988 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
990 Base::_pred=(void *)&t;
991 return DijkstraWizard<DefPredMapBase<T> >(*this);
996 // struct DefPredNodeMapBase : public Base {
997 // typedef T PredNodeMap;
998 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
999 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1002 // ///\brief \ref named-templ-param "Named parameter"
1003 // ///function for setting PredNodeMap type
1005 // /// \ref named-templ-param "Named parameter"
1006 // ///function for setting PredNodeMap type
1008 // template<class T>
1009 // DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1011 // Base::_predNode=(void *)&t;
1012 // return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
1016 struct DefDistMapBase : public Base {
1018 static DistMap *createDistMap(const Graph &G) { return 0; };
1019 DefDistMapBase(const TR &b) : TR(b) {}
1022 ///\brief \ref named-templ-param "Named parameter"
1023 ///function for setting DistMap type
1025 /// \ref named-templ-param "Named parameter"
1026 ///function for setting DistMap type
1029 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1031 Base::_dist=(void *)&t;
1032 return DijkstraWizard<DefDistMapBase<T> >(*this);
1035 /// Sets the source node, from which the Dijkstra algorithm runs.
1037 /// Sets the source node, from which the Dijkstra algorithm runs.
1038 /// \param s is the source node.
1039 DijkstraWizard<TR> &source(Node s)
1047 ///Function type interface for Dijkstra algorithm.
1049 /// \ingroup flowalgs
1050 ///Function type interface for Dijkstra algorithm.
1052 ///This function also has several
1053 ///\ref named-templ-func-param "named parameters",
1054 ///they are declared as the members of class \ref DijkstraWizard.
1056 ///example shows how to use these parameters.
1058 /// dijkstra(g,length,source).predMap(preds).run();
1060 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1061 ///to the end of the parameter list.
1062 ///\sa DijkstraWizard
1064 template<class GR, class LM>
1065 DijkstraWizard<DijkstraWizardBase<GR,LM> >
1066 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1068 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1071 } //END OF NAMESPACE LEMON