Easy input-output function for common graphs.
Modified Exception handling in graph_reader.
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 #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>
34 ///Default traits class of Dijkstra class.
36 ///Default traits class of Dijkstra class.
37 ///\param GR Graph type.
38 ///\param LM Type of length map.
39 template<class GR, class LM>
40 struct DijkstraDefaultTraits
42 ///The graph type the algorithm runs on.
44 ///The type of the map that stores the edge lengths.
46 ///The type of the map that stores the edge lengths.
47 ///It must meet the \ref concept::ReadMap "ReadMap" concept.
49 //The type of the length of the edges.
50 typedef typename LM::Value Value;
51 ///The heap type used by Dijkstra algorithm.
53 ///The heap type used by Dijkstra algorithm.
57 typedef BinHeap<typename Graph::Node,
59 typename GR::template NodeMap<int>,
60 std::less<Value> > Heap;
62 ///\brief The type of the map that stores the last
63 ///edges of the shortest paths.
65 ///The type of the map that stores the last
66 ///edges of the shortest paths.
67 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
69 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
70 ///Instantiates a PredMap.
72 ///This function instantiates a \ref PredMap.
73 ///\param G is the graph, to which we would like to define the PredMap.
74 ///\todo The graph alone may be insufficient for the initialization
75 static PredMap *createPredMap(const GR &G)
77 return new PredMap(G);
79 ///\brief The type of the map that stores the last but one
80 ///nodes of the shortest paths.
82 ///The type of the map that stores the last but one
83 ///nodes of the shortest paths.
84 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
86 typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
87 ///Instantiates a PredNodeMap.
89 ///This function instantiates a \ref PredNodeMap.
90 ///\param G is the graph, to which
91 ///we would like to define the \ref PredNodeMap
92 static PredNodeMap *createPredNodeMap(const GR &G)
94 return new PredNodeMap();
97 ///The type of the map that stores whether a nodes is reached.
99 ///The type of the map that stores whether a nodes is reached.
100 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
101 ///By default it is a NullMap.
102 ///\todo If it is set to a real map, Dijkstra::reached() should read this.
103 ///\todo named parameter to set this type, function to read and write.
104 typedef NullMap<typename Graph::Node,bool> ReachedMap;
105 ///Instantiates a ReachedMap.
107 ///This function instantiates a \ref ReachedMap.
108 ///\param G is the graph, to which
109 ///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 /// \ingroup flowalgs
133 ///This class provides an efficient implementation of %Dijkstra algorithm.
134 ///The edge lengths are passed to the algorithm using a
135 ///\ref concept::ReadMap "ReadMap",
136 ///so it is easy to change it to any kind of length.
138 ///The type of the length is determined by the
139 ///\ref concept::ReadMap::Value "Value" of the length map.
141 ///It is also possible to change the underlying priority heap.
143 ///\param GR The graph type the algorithm runs on. The default value is
144 ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
145 ///is only passed to \ref DijkstraDefaultTraits.
146 ///\param LM This read-only
149 ///lengths of the edges. It is read once for each edge, so the map
150 ///may involve in relatively time consuming process to compute the edge
151 ///length if it is necessary. The default map type is
152 ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
153 ///The value of LM is not used directly by Dijkstra, it
154 ///is only passed to \ref DijkstraDefaultTraits.
155 ///\param TR Traits class to set various data types used by the algorithm.
156 ///The default traits class is
157 ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
158 ///See \ref DijkstraDefaultTraits for the documentation of
159 ///a Dijkstra traits class.
161 ///\author Jacint Szabo and Alpar Juttner
162 ///\todo A compare object would be nice.
165 template <typename GR,
169 template <typename GR=ListGraph,
170 typename LM=typename GR::template EdgeMap<int>,
171 typename TR=DijkstraDefaultTraits<GR,LM> >
176 * \brief \ref Exception for uninitialized parameters.
178 * This error represents problems in the initialization
179 * of the parameters of the algorithms.
181 class UninitializedParameter : public lemon::UninitializedParameter {
183 virtual const char* exceptionName() const {
184 return "lemon::Dijsktra::UninitializedParameter";
189 ///The type of the underlying graph.
190 typedef typename TR::Graph Graph;
192 typedef typename Graph::Node Node;
194 typedef typename Graph::NodeIt NodeIt;
196 typedef typename Graph::Edge Edge;
198 typedef typename Graph::OutEdgeIt OutEdgeIt;
200 ///The type of the length of the edges.
201 typedef typename TR::LengthMap::Value Value;
202 ///The type of the map that stores the edge lengths.
203 typedef typename TR::LengthMap LengthMap;
204 ///\brief The type of the map that stores the last
205 ///edges of the shortest paths.
206 typedef typename TR::PredMap PredMap;
207 ///\brief The type of the map that stores the last but one
208 ///nodes of the shortest paths.
209 typedef typename TR::PredNodeMap PredNodeMap;
210 ///The type of the map indicating if a node is reached.
211 typedef typename TR::ReachedMap ReachedMap;
212 ///The type of the map that stores the dists of the nodes.
213 typedef typename TR::DistMap DistMap;
214 ///The heap type used by the dijkstra algorithm.
215 typedef typename TR::Heap Heap;
217 /// Pointer to the underlying graph.
219 /// Pointer to the length map
220 const LengthMap *length;
221 ///Pointer to the map of predecessors edges.
223 ///Indicates if \ref _pred is locally allocated (\c true) or not.
225 ///Pointer to the map of predecessors nodes.
226 PredNodeMap *_predNode;
227 ///Indicates if \ref _predNode is locally allocated (\c true) or not.
229 ///Pointer to the map of distances.
231 ///Indicates if \ref _dist is locally allocated (\c true) or not.
233 ///Pointer to the map of reached status of the nodes.
234 ReachedMap *_reached;
235 ///Indicates if \ref _reached is locally allocated (\c true) or not.
238 ///The source node of the last execution.
241 ///Creates the maps if necessary.
243 ///\todo Error if \c G or are \c NULL. What about \c length?
244 ///\todo Better memory allocation (instead of new).
249 _pred = Traits::createPredMap(*G);
252 local_predNode = true;
253 _predNode = Traits::createPredNodeMap(*G);
257 _dist = Traits::createDistMap(*G);
260 local_reached = true;
261 _reached = Traits::createReachedMap(*G);
267 ///\name Named template parameters
272 struct DefPredMapTraits : public Traits {
274 static PredMap *createPredMap(const Graph &G)
276 throw UninitializedParameter();
279 ///\ref named-templ-param "Named parameter" for setting PredMap type
281 ///\ref named-templ-param "Named parameter" for setting PredMap type
284 class DefPredMap : public Dijkstra< Graph,
286 DefPredMapTraits<T> > { };
289 struct DefPredNodeMapTraits : public Traits {
290 typedef T PredNodeMap;
291 static PredNodeMap *createPredNodeMap(const Graph &G)
293 throw UninitializedParameter();
296 ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
298 ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
301 class DefPredNodeMap : public Dijkstra< Graph,
303 DefPredNodeMapTraits<T> > { };
306 struct DefDistMapTraits : public Traits {
308 static DistMap *createDistMap(const Graph &G)
310 throw UninitializedParameter();
313 ///\ref named-templ-param "Named parameter" for setting DistMap type
315 ///\ref named-templ-param "Named parameter" for setting DistMap type
318 class DefDistMap : public Dijkstra< Graph,
320 DefDistMapTraits<T> > { };
323 struct DefReachedMapTraits : public Traits {
324 typedef T ReachedMap;
325 static ReachedMap *createReachedMap(const Graph &G)
327 throw UninitializedParameter();
330 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
332 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
335 class DefReachedMap : public Dijkstra< Graph,
337 DefReachedMapTraits<T> > { };
339 struct DefGraphReachedMapTraits : public Traits {
340 typedef typename Graph::template NodeMap<bool> ReachedMap;
341 static ReachedMap *createReachedMap(const Graph &G)
343 return new ReachedMap(G);
346 ///\brief \ref named-templ-param "Named parameter"
347 ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
349 ///\ref named-templ-param "Named parameter"
350 ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
351 ///If you don't set it explicitely, it will be automatically allocated.
353 class DefReachedMapToBeDefaultMap :
354 public Dijkstra< Graph,
356 DefGraphReachedMapTraits> { };
362 typename Graph::template NodeMap<int> _heap_map;
368 ///\param _G the graph the algorithm will run on.
369 ///\param _length the length map used by the algorithm.
370 Dijkstra(const Graph& _G, const LengthMap& _length) :
371 G(&_G), length(&_length),
372 _pred(NULL), local_pred(false),
373 _predNode(NULL), local_predNode(false),
374 _dist(NULL), local_dist(false),
375 _reached(NULL), local_reached(false),
376 _heap_map(*G,-1),_heap(_heap_map)
382 if(local_pred) delete _pred;
383 if(local_predNode) delete _predNode;
384 if(local_dist) delete _dist;
385 if(local_reached) delete _reached;
388 ///Sets the length map.
390 ///Sets the length map.
391 ///\return <tt> (*this) </tt>
392 Dijkstra &lengthMap(const LengthMap &m)
398 ///Sets the map storing the predecessor edges.
400 ///Sets the map storing the predecessor edges.
401 ///If you don't use this function before calling \ref run(),
402 ///it will allocate one. The destuctor deallocates this
403 ///automatically allocated map, of course.
404 ///\return <tt> (*this) </tt>
405 Dijkstra &predMap(PredMap &m)
415 ///Sets the map storing the predecessor nodes.
417 ///Sets the map storing the predecessor nodes.
418 ///If you don't use this function before calling \ref run(),
419 ///it will allocate one. The destuctor deallocates this
420 ///automatically allocated map, of course.
421 ///\return <tt> (*this) </tt>
422 Dijkstra &predNodeMap(PredNodeMap &m)
426 local_predNode=false;
432 ///Sets the map storing the distances calculated by the algorithm.
434 ///Sets the map storing the distances calculated by the algorithm.
435 ///If you don't use this function before calling \ref run(),
436 ///it will allocate one. The destuctor deallocates this
437 ///automatically allocated map, of course.
438 ///\return <tt> (*this) </tt>
439 Dijkstra &distMap(DistMap &m)
450 void finalizeNodeData(Node v,Value dst)
452 _reached->set(v,true);
454 if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
458 ///\name Excetution control
459 ///The simplest way to execute the algorithm is to use
460 ///one of the member functions called \c run(...).
462 ///It you need more control on the execution,
463 ///first you must call \ref init(), then you can add several source nodes
464 ///with \ref addSource(). Finally \ref start() will perform the actual path
469 ///Initializes the internal data structures.
471 ///Initializes the internal data structures.
473 ///\todo _heap_map's type could also be in the traits class.
478 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
479 _pred->set(u,INVALID);
480 _predNode->set(u,INVALID);
481 ///\todo *_reached is not set to false.
482 _heap_map.set(u,Heap::PRE_HEAP);
486 ///Adds a new source node.
488 ///Adds a new source node to the priority heap.
490 ///The optional second parameter is the initial distance of the node.
492 ///It checks if the node has already been added to the heap and
493 ///It is pushed to the heap only if either it was not in the heap
494 ///or the shortest path found till then is longer then \c dst.
495 void addSource(Node s,Value dst=0)
498 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
499 else if(_heap[s]<dst) {
501 _pred->set(s,INVALID);
505 ///Processes the next node in the priority heap
507 ///Processes the next node in the priority heap.
509 ///\warning The priority heap must not be empty!
510 void processNextNode()
513 Value oldvalue=_heap[v];
515 finalizeNodeData(v,oldvalue);
517 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
519 switch(_heap.state(w)) {
521 _heap.push(w,oldvalue+(*length)[e]);
523 // _predNode->set(w,v);
526 if ( oldvalue+(*length)[e] < _heap[w] ) {
527 _heap.decrease(w, oldvalue+(*length)[e]);
529 // _predNode->set(w,v);
532 case Heap::POST_HEAP:
538 ///Returns \c false if there are nodes to be processed in the priority heap
540 ///Returns \c false if there are nodes to be processed in the priority heap
542 bool emptyHeap() { return _heap.empty(); }
543 ///Returns the number of the nodes to be processed in the priority heap
545 ///Returns the number of the nodes to be processed in the priority heap
547 int heapSize() { return _heap.size(); }
549 ///Executes the algorithm.
551 ///Executes the algorithm.
553 ///\pre init() must be called and at least one node should be added
554 ///with addSource() before using this function.
556 ///This method runs the %Dijkstra algorithm from the root node(s)
559 ///shortest path to each node. The algorithm computes
560 ///- The shortest path tree.
561 ///- The distance of each node from the root(s).
565 while ( !_heap.empty() ) processNextNode();
568 ///Executes the algorithm until \c dest is reached.
570 ///Executes the algorithm until \c dest is reached.
572 ///\pre init() must be called and at least one node should be added
573 ///with addSource() before using this function.
575 ///This method runs the %Dijkstra algorithm from the root node(s)
578 ///shortest path to \c dest. The algorithm computes
579 ///- The shortest path to \c dest.
580 ///- The distance of \c dest from the root(s).
582 void start(Node dest)
584 while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
585 if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
588 ///Executes the algorithm until a condition is met.
590 ///Executes the algorithm until a condition is met.
592 ///\pre init() must be called and at least one node should be added
593 ///with addSource() before using this function.
595 ///\param nm must be a bool (or convertible) node map. The algorithm
596 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
598 void start(const NM &nm)
600 while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
601 if ( !_heap.empty() ) finalizeNodeData(_heap.top());
604 ///Runs %Dijkstra algorithm from node \c s.
606 ///This method runs the %Dijkstra algorithm from a root node \c s
609 ///shortest path to each node. The algorithm computes
610 ///- The shortest path tree.
611 ///- The distance of each node from the root.
613 ///\note d.run(s) is just a shortcut of the following code.
625 ///Finds the shortest path between \c s and \c t.
627 ///Finds the shortest path between \c s and \c t.
629 ///\return The length of the shortest s---t path if there exists one,
631 ///\note Apart from the return value, d.run(s) is
632 ///just a shortcut of the following code.
638 Value run(Node s,Node t) {
642 return (*_pred)[t]==INVALID?0:(*_dist)[t];
647 ///\name Query Functions
648 ///The result of the %Dijkstra algorithm can be obtained using these
650 ///Before the use of these functions,
651 ///either run() or start() must be called.
655 ///The distance of a node from the root.
657 ///Returns the distance of a node from the root.
658 ///\pre \ref run() must be called before using this function.
659 ///\warning If node \c v in unreachable from the root the return value
660 ///of this funcion is undefined.
661 Value dist(Node v) const { return (*_dist)[v]; }
663 ///Returns the 'previous edge' of the shortest path tree.
665 ///For a node \c v it returns the 'previous edge' of the shortest path tree,
666 ///i.e. it returns the last edge of a shortest path from the root to \c
667 ///v. It is \ref INVALID
668 ///if \c v is unreachable from the root or if \c v=s. The
669 ///shortest path tree used here is equal to the shortest path tree used in
670 ///\ref predNode(Node v). \pre \ref run() must be called before using
672 ///\todo predEdge could be a better name.
673 Edge pred(Node v) const { return (*_pred)[v]; }
675 ///Returns the 'previous node' of the shortest path tree.
677 ///For a node \c v it returns the 'previous node' of the shortest path tree,
678 ///i.e. it returns the last but one node from a shortest path from the
679 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
680 ///\c v=s. The shortest path tree used here is equal to the shortest path
681 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
682 ///using this function.
683 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
684 G->source((*_pred)[v]); }
686 ///Returns a reference to the NodeMap of distances.
688 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
689 ///be called before using this function.
690 const DistMap &distMap() const { return *_dist;}
692 ///Returns a reference to the shortest path tree map.
694 ///Returns a reference to the NodeMap of the edges of the
695 ///shortest path tree.
696 ///\pre \ref run() must be called before using this function.
697 const PredMap &predMap() const { return *_pred;}
699 ///Returns a reference to the map of nodes of shortest paths.
701 ///Returns a reference to the NodeMap of the last but one nodes of the
702 ///shortest path tree.
703 ///\pre \ref run() must be called before using this function.
704 const PredNodeMap &predNodeMap() const { return *_predNode;}
706 ///Checks if a node is reachable from the root.
708 ///Returns \c true if \c v is reachable from the root.
709 ///\warning If the algorithm is started from multiple nodes,
710 ///this function may give false result for the source nodes.
711 ///\pre \ref run() must be called before using this function.
713 bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
718 /// Default traits used by \ref DijkstraWizard
720 /// To make it easier to use Dijkstra algorithm
721 ///we have created a wizard class.
722 /// This \ref DijkstraWizard class needs default traits,
723 ///as well as the \ref Dijkstra class.
724 /// The \ref DijkstraWizardBase is a class to be the default traits of the
725 /// \ref DijkstraWizard class.
726 template<class GR,class LM>
727 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
730 typedef DijkstraDefaultTraits<GR,LM> Base;
732 /// Type of the nodes in the graph.
733 typedef typename Base::Graph::Node Node;
735 /// Pointer to the underlying graph.
737 /// Pointer to the length map
739 ///Pointer to the map of predecessors edges.
741 ///Pointer to the map of predecessors nodes.
743 ///Pointer to the map of distances.
745 ///Pointer to the source node.
751 /// This constructor does not require parameters, therefore it initiates
752 /// all of the attributes to default values (0, INVALID).
753 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
754 _dist(0), _source(INVALID) {}
758 /// This constructor requires some parameters,
759 /// listed in the parameters list.
760 /// Others are initiated to 0.
761 /// \param g is the initial value of \ref _g
762 /// \param l is the initial value of \ref _length
763 /// \param s is the initial value of \ref _source
764 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
765 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
766 _dist(0), _source(s) {}
770 /// A class to make easier the usage of Dijkstra algorithm
772 /// \ingroup flowalgs
773 /// This class is created to make it easier to use Dijkstra algorithm.
774 /// It uses the functions and features of the plain \ref Dijkstra,
775 /// but it is much simpler to use it.
777 /// Simplicity means that the way to change the types defined
778 /// in the traits class is based on functions that returns the new class
779 /// and not on templatable built-in classes.
780 /// When using the plain \ref Dijkstra
781 /// the new class with the modified type comes from
782 /// the original class by using the ::
783 /// operator. In the case of \ref DijkstraWizard only
784 /// a function have to be called and it will
785 /// return the needed class.
787 /// It does not have own \ref run method. When its \ref run method is called
788 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
791 class DijkstraWizard : public TR
795 ///The type of the underlying graph.
796 typedef typename TR::Graph Graph;
798 typedef typename Graph::Node Node;
800 typedef typename Graph::NodeIt NodeIt;
802 typedef typename Graph::Edge Edge;
804 typedef typename Graph::OutEdgeIt OutEdgeIt;
806 ///The type of the map that stores the edge lengths.
807 typedef typename TR::LengthMap LengthMap;
808 ///The type of the length of the edges.
809 typedef typename LengthMap::Value Value;
810 ///\brief The type of the map that stores the last
811 ///edges of the shortest paths.
812 typedef typename TR::PredMap PredMap;
813 ///\brief The type of the map that stores the last but one
814 ///nodes of the shortest paths.
815 typedef typename TR::PredNodeMap PredNodeMap;
816 ///The type of the map that stores the dists of the nodes.
817 typedef typename TR::DistMap DistMap;
819 ///The heap type used by the dijkstra algorithm.
820 typedef typename TR::Heap Heap;
823 DijkstraWizard() : TR() {}
825 /// Constructor that requires parameters.
827 /// Constructor that requires parameters.
828 /// These parameters will be the default values for the traits class.
829 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
833 DijkstraWizard(const TR &b) : TR(b) {}
837 ///Runs Dijkstra algorithm from a given node.
839 ///Runs Dijkstra algorithm from a given node.
840 ///The node can be given by the \ref source function.
843 if(Base::_source==INVALID) throw UninitializedParameter();
844 Dijkstra<Graph,LengthMap,TR>
845 Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
846 if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred);
847 if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
848 if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist);
849 Dij.run(Base::_source);
852 ///Runs Dijkstra algorithm from the given node.
854 ///Runs Dijkstra algorithm from the given node.
855 ///\param s is the given source.
863 struct DefPredMapBase : public Base {
865 static PredMap *createPredMap(const Graph &G) { return 0; };
866 DefPredMapBase(const Base &b) : Base(b) {}
869 ///\brief \ref named-templ-param "Named parameter"
870 ///function for setting PredMap type
872 /// \ref named-templ-param "Named parameter"
873 ///function for setting PredMap type
876 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
878 Base::_pred=(void *)&t;
879 return DijkstraWizard<DefPredMapBase<T> >(*this);
884 struct DefPredNodeMapBase : public Base {
885 typedef T PredNodeMap;
886 static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
887 DefPredNodeMapBase(const Base &b) : Base(b) {}
890 ///\brief \ref named-templ-param "Named parameter"
891 ///function for setting PredNodeMap type
893 /// \ref named-templ-param "Named parameter"
894 ///function for setting PredNodeMap type
897 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
899 Base::_predNode=(void *)&t;
900 return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
904 struct DefDistMapBase : public Base {
906 static DistMap *createDistMap(const Graph &G) { return 0; };
907 DefDistMapBase(const Base &b) : Base(b) {}
910 ///\brief \ref named-templ-param "Named parameter"
911 ///function for setting DistMap type
913 /// \ref named-templ-param "Named parameter"
914 ///function for setting DistMap type
917 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
919 Base::_dist=(void *)&t;
920 return DijkstraWizard<DefDistMapBase<T> >(*this);
923 /// Sets the source node, from which the Dijkstra algorithm runs.
925 /// Sets the source node, from which the Dijkstra algorithm runs.
926 /// \param s is the source node.
927 DijkstraWizard<TR> &source(Node s)
937 /// \ingroup flowalgs
938 ///\todo Please document...
940 template<class GR, class LM>
941 DijkstraWizard<DijkstraWizardBase<GR,LM> >
942 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
944 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
949 } //END OF NAMESPACE LEMON