NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
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 dijkstraZero() solution should be revised.
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>
34 template<class T> T dijkstraZero() {return 0;}
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 cross reference type used by heap.
55 /// The cross reference type used by heap.
56 /// Usually it is \c Graph::NodeMap<int>.
57 typedef typename Graph::template NodeMap<int> HeapCrossRef;
58 ///Instantiates a HeapCrossRef.
60 ///This function instantiates a \ref HeapCrossRef.
61 /// \param G is the graph, to which we would like to define the
63 static HeapCrossRef *createHeapCrossRef(const GR &G)
65 return new HeapCrossRef(G);
68 ///The heap type used by Dijkstra algorithm.
70 ///The heap type used by Dijkstra algorithm.
74 typedef BinHeap<typename Graph::Node, typename LM::Value,
75 HeapCrossRef, std::less<Value> > Heap;
77 static Heap *createHeap(HeapCrossRef& R)
82 ///\brief The type of the map that stores the last
83 ///edges of the shortest paths.
85 ///The type of the map that stores the last
86 ///edges of the shortest paths.
87 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
89 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
90 ///Instantiates a PredMap.
92 ///This function instantiates a \ref PredMap.
93 ///\param G is the graph, to which we would like to define the PredMap.
94 ///\todo The graph alone may be insufficient for the initialization
95 static PredMap *createPredMap(const GR &G)
97 return new PredMap(G);
100 ///The type of the map that stores whether a nodes is processed.
102 ///The type of the map that stores whether a nodes is processed.
103 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
104 ///By default it is a NullMap.
105 ///\todo If it is set to a real map,
106 ///Dijkstra::processed() should read this.
107 ///\todo named parameter to set this type, function to read and write.
108 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
109 ///Instantiates a ProcessedMap.
111 ///This function instantiates a \ref ProcessedMap.
112 ///\param g is the graph, to which
113 ///we would like to define the \ref ProcessedMap
115 static ProcessedMap *createProcessedMap(const GR &g)
117 static ProcessedMap *createProcessedMap(const GR &)
120 return new ProcessedMap();
122 ///The type of the map that stores the dists of the nodes.
124 ///The type of the map that stores the dists of the nodes.
125 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
127 typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
128 ///Instantiates a DistMap.
130 ///This function instantiates a \ref DistMap.
131 ///\param G is the graph, to which we would like to define the \ref DistMap
132 static DistMap *createDistMap(const GR &G)
134 return new DistMap(G);
138 ///%Dijkstra algorithm class.
140 /// \ingroup flowalgs
141 ///This class provides an efficient implementation of %Dijkstra algorithm.
142 ///The edge lengths are passed to the algorithm using a
143 ///\ref concept::ReadMap "ReadMap",
144 ///so it is easy to change it to any kind of length.
146 ///The type of the length is determined by the
147 ///\ref concept::ReadMap::Value "Value" of the length map.
149 ///It is also possible to change the underlying priority heap.
151 ///\param GR The graph type the algorithm runs on. The default value
152 ///is \ref ListGraph. The value of GR is not used directly by
153 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
154 ///\param LM This read-only EdgeMap determines the lengths of the
155 ///edges. It is read once for each edge, so the map may involve in
156 ///relatively time consuming process to compute the edge length if
157 ///it is necessary. The default map type is \ref
158 ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
159 ///of LM is not used directly by Dijkstra, it is only passed to \ref
160 ///DijkstraDefaultTraits. \param TR Traits class to set
161 ///various data types used by the algorithm. The default traits
162 ///class is \ref DijkstraDefaultTraits
163 ///"DijkstraDefaultTraits<GR,LM>". See \ref
164 ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
167 ///\author Jacint Szabo and Alpar Juttner
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 ///The type of the map indicating if a node is processed.
213 typedef typename TR::ProcessedMap ProcessedMap;
214 ///The type of the map that stores the dists of the nodes.
215 typedef typename TR::DistMap DistMap;
216 ///The cross reference type used for the current heap.
217 typedef typename TR::HeapCrossRef HeapCrossRef;
218 ///The heap type used by the dijkstra algorithm.
219 typedef typename TR::Heap Heap;
221 /// Pointer to the underlying graph.
223 /// Pointer to the length map
224 const LengthMap *length;
225 ///Pointer to the map of predecessors edges.
227 ///Indicates if \ref _pred 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 processed status of the nodes.
234 ProcessedMap *_processed;
235 ///Indicates if \ref _processed is locally allocated (\c true) or not.
236 bool local_processed;
237 ///Pointer to the heap cross references.
238 HeapCrossRef *_heap_cross_ref;
239 ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
240 bool local_heap_cross_ref;
241 ///Pointer to the heap.
243 ///Indicates if \ref _heap is locally allocated (\c true) or not.
246 ///Creates the maps if necessary.
248 ///\todo Better memory allocation (instead of new).
253 _pred = Traits::createPredMap(*G);
257 _dist = Traits::createDistMap(*G);
260 local_processed = true;
261 _processed = Traits::createProcessedMap(*G);
263 if (!_heap_cross_ref) {
264 local_heap_cross_ref = true;
265 _heap_cross_ref = Traits::createHeapCrossRef(*G);
269 _heap = Traits::createHeap(*_heap_cross_ref);
275 typedef Dijkstra Create;
277 ///\name Named template parameters
282 struct DefPredMapTraits : public Traits {
284 static PredMap *createPredMap(const Graph &G)
286 throw UninitializedParameter();
289 ///\ref named-templ-param "Named parameter" for setting PredMap type
291 ///\ref named-templ-param "Named parameter" for setting PredMap type
295 : public Dijkstra< Graph, LengthMap, DefPredMapTraits<T> > {
296 typedef Dijkstra< Graph, LengthMap, DefPredMapTraits<T> > Create;
300 struct DefDistMapTraits : public Traits {
302 static DistMap *createDistMap(const Graph &G)
304 throw UninitializedParameter();
307 ///\ref named-templ-param "Named parameter" for setting DistMap type
309 ///\ref named-templ-param "Named parameter" for setting DistMap type
313 : public Dijkstra< Graph, LengthMap, DefDistMapTraits<T> > {
314 typedef Dijkstra< Graph, LengthMap, DefDistMapTraits<T> > Create;
318 struct DefProcessedMapTraits : public Traits {
319 typedef T ProcessedMap;
320 static ProcessedMap *createProcessedMap(const Graph &G)
322 throw UninitializedParameter();
325 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
327 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
330 struct DefProcessedMap
331 : public Dijkstra< Graph, LengthMap, DefProcessedMapTraits<T> > {
332 typedef Dijkstra< Graph, LengthMap, DefProcessedMapTraits<T> > Create;
335 struct DefGraphProcessedMapTraits : public Traits {
336 typedef typename Graph::template NodeMap<bool> ProcessedMap;
337 static ProcessedMap *createProcessedMap(const Graph &G)
339 return new ProcessedMap(G);
342 ///\brief \ref named-templ-param "Named parameter"
343 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
345 ///\ref named-templ-param "Named parameter"
346 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
347 ///If you don't set it explicitely, it will be automatically allocated.
349 struct DefProcessedMapToBeDefaultMap
350 : public Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> {
351 typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create;
354 template <class H, class CR>
355 struct DefHeapTraits : public Traits {
356 typedef CR HeapCrossRef;
358 static HeapCrossRef *createHeapCrossRef(const Graph &) {
359 throw UninitializedParameter();
361 static Heap *createHeap(HeapCrossRef &)
363 throw UninitializedParameter();
366 ///\ref named-templ-param "Named parameter" for setting heap and cross
369 ///\ref named-templ-param "Named parameter" for setting heap and cross
372 template <class H, class CR = typename Graph::template NodeMap<int> >
374 : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > {
375 typedef Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
378 template <class H, class CR>
379 struct DefStandardHeapTraits : public Traits {
380 typedef CR HeapCrossRef;
382 static HeapCrossRef *createHeapCrossRef(const Graph &G) {
383 return new HeapCrossRef(G);
385 static Heap *createHeap(HeapCrossRef &R)
390 ///\ref named-templ-param "Named parameter" for setting heap and cross
391 ///reference type with automatic allocation
393 ///\ref named-templ-param "Named parameter" for setting heap and cross
394 ///reference type. It can allocate the heap and the cross reference
395 ///object if the cross reference's constructor waits for the graph as
396 ///parameter and the heap's constructor waits for the cross reference.
397 template <class H, class CR = typename Graph::template NodeMap<int> >
398 struct DefStandardHeap
399 : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
400 typedef Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
415 ///\param _G the graph the algorithm will run on.
416 ///\param _length the length map used by the algorithm.
417 Dijkstra(const Graph& _G, const LengthMap& _length) :
418 G(&_G), length(&_length),
419 _pred(NULL), local_pred(false),
420 _dist(NULL), local_dist(false),
421 _processed(NULL), local_processed(false),
422 _heap_cross_ref(NULL), local_heap_cross_ref(false),
423 _heap(NULL), local_heap(false)
429 if(local_pred) delete _pred;
430 if(local_dist) delete _dist;
431 if(local_processed) delete _processed;
432 if(local_heap_cross_ref) delete _heap_cross_ref;
433 if(local_heap) delete _heap;
436 ///Sets the length map.
438 ///Sets the length map.
439 ///\return <tt> (*this) </tt>
440 Dijkstra &lengthMap(const LengthMap &m)
446 ///Sets the map storing the predecessor edges.
448 ///Sets the map storing the predecessor edges.
449 ///If you don't use this function before calling \ref run(),
450 ///it will allocate one. The destuctor deallocates this
451 ///automatically allocated map, of course.
452 ///\return <tt> (*this) </tt>
453 Dijkstra &predMap(PredMap &m)
463 ///Sets the map storing the distances calculated by the algorithm.
465 ///Sets the map storing the distances calculated by the algorithm.
466 ///If you don't use this function before calling \ref run(),
467 ///it will allocate one. The destuctor deallocates this
468 ///automatically allocated map, of course.
469 ///\return <tt> (*this) </tt>
470 Dijkstra &distMap(DistMap &m)
480 ///Sets the heap and the cross reference used by algorithm.
482 ///Sets the heap and the cross reference used by algorithm.
483 ///If you don't use this function before calling \ref run(),
484 ///it will allocate one. The destuctor deallocates this
485 ///automatically allocated map, of course.
486 ///\return <tt> (*this) </tt>
487 Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef)
489 if(local_heap_cross_ref) {
490 delete _heap_cross_ref;
491 local_heap_cross_ref=false;
493 _heap_cross_ref = &crossRef;
503 void finalizeNodeData(Node v,Value dst)
505 _processed->set(v,true);
510 ///\name Execution control
511 ///The simplest way to execute the algorithm is to use
512 ///one of the member functions called \c run(...).
514 ///If you need more control on the execution,
515 ///first you must call \ref init(), then you can add several source nodes
516 ///with \ref addSource().
517 ///Finally \ref start() will perform the actual path
522 ///Initializes the internal data structures.
524 ///Initializes the internal data structures.
530 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
531 _pred->set(u,INVALID);
532 _processed->set(u,false);
533 _heap_cross_ref->set(u,Heap::PRE_HEAP);
537 ///Adds a new source node.
539 ///Adds a new source node to the priority heap.
541 ///The optional second parameter is the initial distance of the node.
543 ///It checks if the node has already been added to the heap and
544 ///It is pushed to the heap only if either it was not in the heap
545 ///or the shortest path found till then is longer then \c dst.
546 void addSource(Node s,Value dst=dijkstraZero<Value>())
548 if(_heap->state(s) != Heap::IN_HEAP) {
550 } else if((*_heap)[s]<dst) {
552 _pred->set(s,INVALID);
556 ///Processes the next node in the priority heap
558 ///Processes the next node in the priority heap.
560 ///\return The processed node.
562 ///\warning The priority heap must not be empty!
563 Node processNextNode()
566 Value oldvalue=_heap->prio();
568 finalizeNodeData(v,oldvalue);
570 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
572 switch(_heap->state(w)) {
574 _heap->push(w,oldvalue+(*length)[e]);
578 if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
579 _heap->decrease(w, oldvalue+(*length)[e]);
583 case Heap::POST_HEAP:
590 ///Next node to be processed.
592 ///Next node to be processed.
594 ///\return The next node to be processed or INVALID if the priority heap
598 return _heap->empty()?_heap->top():INVALID;
601 ///\brief Returns \c false if there are nodes
602 ///to be processed in the priority heap
604 ///Returns \c false if there are nodes
605 ///to be processed in the priority heap
606 bool emptyQueue() { return _heap->empty(); }
607 ///Returns the number of the nodes to be processed in the priority heap
609 ///Returns the number of the nodes to be processed in the priority heap
611 int queueSize() { return _heap->size(); }
613 ///Executes the algorithm.
615 ///Executes the algorithm.
617 ///\pre init() must be called and at least one node should be added
618 ///with addSource() before using this function.
620 ///This method runs the %Dijkstra algorithm from the root node(s)
623 ///shortest path to each node. The algorithm computes
624 ///- The shortest path tree.
625 ///- The distance of each node from the root(s).
629 while ( !_heap->empty() ) processNextNode();
632 ///Executes the algorithm until \c dest is reached.
634 ///Executes the algorithm until \c dest is reached.
636 ///\pre init() must be called and at least one node should be added
637 ///with addSource() before using this function.
639 ///This method runs the %Dijkstra algorithm from the root node(s)
642 ///shortest path to \c dest. The algorithm computes
643 ///- The shortest path to \c dest.
644 ///- The distance of \c dest from the root(s).
646 void start(Node dest)
648 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
649 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
652 ///Executes the algorithm until a condition is met.
654 ///Executes the algorithm until a condition is met.
656 ///\pre init() must be called and at least one node should be added
657 ///with addSource() before using this function.
659 ///\param nm must be a bool (or convertible) node map. The algorithm
660 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
661 template<class NodeBoolMap>
662 void start(const NodeBoolMap &nm)
664 while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
665 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
668 ///Runs %Dijkstra algorithm from node \c s.
670 ///This method runs the %Dijkstra algorithm from a root node \c s
673 ///shortest path to each node. The algorithm computes
674 ///- The shortest path tree.
675 ///- The distance of each node from the root.
677 ///\note d.run(s) is just a shortcut of the following code.
689 ///Finds the shortest path between \c s and \c t.
691 ///Finds the shortest path between \c s and \c t.
693 ///\return The length of the shortest s---t path if there exists one,
695 ///\note Apart from the return value, d.run(s) is
696 ///just a shortcut of the following code.
702 Value run(Node s,Node t) {
706 return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
711 ///\name Query Functions
712 ///The result of the %Dijkstra algorithm can be obtained using these
714 ///Before the use of these functions,
715 ///either run() or start() must be called.
719 ///Copies the shortest path to \c t into \c p
721 ///This function copies the shortest path to \c t into \c p.
722 ///If it \c t is a source itself or unreachable, then it does not
724 ///\return Returns \c true if a path to \c t was actually copied to \c p,
725 ///\c false otherwise.
728 bool getPath(P &p,Node t)
732 typename P::Builder b(p);
733 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
734 b.pushFront(predEdge(t));
741 ///The distance of a node from the root.
743 ///Returns the distance of a node from the root.
744 ///\pre \ref run() must be called before using this function.
745 ///\warning If node \c v in unreachable from the root the return value
746 ///of this funcion is undefined.
747 Value dist(Node v) const { return (*_dist)[v]; }
749 ///Returns the 'previous edge' of the shortest path tree.
751 ///For a node \c v it returns the 'previous edge' of the shortest path tree,
752 ///i.e. it returns the last edge of a shortest path from the root to \c
753 ///v. It is \ref INVALID
754 ///if \c v is unreachable from the root or if \c v=s. The
755 ///shortest path tree used here is equal to the shortest path tree used in
756 ///\ref predNode(). \pre \ref run() must be called before using
758 Edge predEdge(Node v) const { return (*_pred)[v]; }
760 ///Returns the 'previous node' of the shortest path tree.
762 ///For a node \c v it returns the 'previous node' of the shortest path tree,
763 ///i.e. it returns the last but one node from a shortest path from the
764 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
765 ///\c v=s. The shortest path tree used here is equal to the shortest path
766 ///tree used in \ref predEdge(). \pre \ref run() must be called before
767 ///using this function.
768 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
769 G->source((*_pred)[v]); }
771 ///Returns a reference to the NodeMap of distances.
773 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
774 ///be called before using this function.
775 const DistMap &distMap() const { return *_dist;}
777 ///Returns a reference to the shortest path tree map.
779 ///Returns a reference to the NodeMap of the edges of the
780 ///shortest path tree.
781 ///\pre \ref run() must be called before using this function.
782 const PredMap &predMap() const { return *_pred;}
784 ///Checks if a node is reachable from the root.
786 ///Returns \c true if \c v is reachable from the root.
787 ///\warning The source nodes are inditated as unreached.
788 ///\pre \ref run() must be called before using this function.
790 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
792 ///Checks if a node is processed.
794 ///Returns \c true if \c v is processed, i.e. the shortest
795 ///path to \c v has already found.
796 ///\pre \ref run() must be called before using this function.
798 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
807 ///Default traits class of Dijkstra function.
809 ///Default traits class of Dijkstra function.
810 ///\param GR Graph type.
811 ///\param LM Type of length map.
812 template<class GR, class LM>
813 struct DijkstraWizardDefaultTraits
815 ///The graph type the algorithm runs on.
817 ///The type of the map that stores the edge lengths.
819 ///The type of the map that stores the edge lengths.
820 ///It must meet the \ref concept::ReadMap "ReadMap" concept.
821 typedef LM LengthMap;
822 //The type of the length of the edges.
823 typedef typename LM::Value Value;
824 ///The heap type used by Dijkstra algorithm.
826 /// The cross reference type used by heap.
828 /// The cross reference type used by heap.
829 /// Usually it is \c Graph::NodeMap<int>.
830 typedef typename Graph::template NodeMap<int> HeapCrossRef;
831 ///Instantiates a HeapCrossRef.
833 ///This function instantiates a \ref HeapCrossRef.
834 /// \param G is the graph, to which we would like to define the
836 /// \todo The graph alone may be insufficient for the initialization
837 static HeapCrossRef *createHeapCrossRef(const GR &G)
839 return new HeapCrossRef(G);
842 ///The heap type used by Dijkstra algorithm.
844 ///The heap type used by Dijkstra algorithm.
848 typedef BinHeap<typename Graph::Node, typename LM::Value,
849 typename GR::template NodeMap<int>,
850 std::less<Value> > Heap;
852 static Heap *createHeap(HeapCrossRef& R)
857 ///\brief The type of the map that stores the last
858 ///edges of the shortest paths.
860 ///The type of the map that stores the last
861 ///edges of the shortest paths.
862 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
864 typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
865 ///Instantiates a PredMap.
867 ///This function instantiates a \ref PredMap.
868 ///\param g is the graph, to which we would like to define the PredMap.
869 ///\todo The graph alone may be insufficient for the initialization
871 static PredMap *createPredMap(const GR &g)
873 static PredMap *createPredMap(const GR &)
876 return new PredMap();
878 ///The type of the map that stores whether a nodes is processed.
880 ///The type of the map that stores whether a nodes is processed.
881 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
882 ///By default it is a NullMap.
883 ///\todo If it is set to a real map,
884 ///Dijkstra::processed() should read this.
885 ///\todo named parameter to set this type, function to read and write.
886 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
887 ///Instantiates a ProcessedMap.
889 ///This function instantiates a \ref ProcessedMap.
890 ///\param g is the graph, to which
891 ///we would like to define the \ref ProcessedMap
893 static ProcessedMap *createProcessedMap(const GR &g)
895 static ProcessedMap *createProcessedMap(const GR &)
898 return new ProcessedMap();
900 ///The type of the map that stores the dists of the nodes.
902 ///The type of the map that stores the dists of the nodes.
903 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
905 typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
906 ///Instantiates a DistMap.
908 ///This function instantiates a \ref DistMap.
909 ///\param g is the graph, to which we would like to define the \ref DistMap
911 static DistMap *createDistMap(const GR &g)
913 static DistMap *createDistMap(const GR &)
916 return new DistMap();
920 /// Default traits used by \ref DijkstraWizard
922 /// To make it easier to use Dijkstra algorithm
923 ///we have created a wizard class.
924 /// This \ref DijkstraWizard class needs default traits,
925 ///as well as the \ref Dijkstra class.
926 /// The \ref DijkstraWizardBase is a class to be the default traits of the
927 /// \ref DijkstraWizard class.
928 /// \todo More named parameters are required...
929 template<class GR,class LM>
930 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
933 typedef DijkstraWizardDefaultTraits<GR,LM> Base;
935 /// Type of the nodes in the graph.
936 typedef typename Base::Graph::Node Node;
938 /// Pointer to the underlying graph.
940 /// Pointer to the length map
942 ///Pointer to the map of predecessors edges.
944 ///Pointer to the map of distances.
946 ///Pointer to the source node.
952 /// This constructor does not require parameters, therefore it initiates
953 /// all of the attributes to default values (0, INVALID).
954 DijkstraWizardBase() : _g(0), _length(0), _pred(0),
955 _dist(0), _source(INVALID) {}
959 /// This constructor requires some parameters,
960 /// listed in the parameters list.
961 /// Others are initiated to 0.
962 /// \param g is the initial value of \ref _g
963 /// \param l is the initial value of \ref _length
964 /// \param s is the initial value of \ref _source
965 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
966 _g((void *)&g), _length((void *)&l), _pred(0),
967 _dist(0), _source(s) {}
971 /// A class to make the usage of Dijkstra algorithm easier
973 /// This class is created to make it easier to use Dijkstra algorithm.
974 /// It uses the functions and features of the plain \ref Dijkstra,
975 /// but it is much simpler to use it.
977 /// Simplicity means that the way to change the types defined
978 /// in the traits class is based on functions that returns the new class
979 /// and not on templatable built-in classes.
980 /// When using the plain \ref Dijkstra
981 /// the new class with the modified type comes from
982 /// the original class by using the ::
983 /// operator. In the case of \ref DijkstraWizard only
984 /// a function have to be called and it will
985 /// return the needed class.
987 /// It does not have own \ref run method. When its \ref run method is called
988 /// it initiates a plain \ref Dijkstra class, and calls the \ref
989 /// Dijkstra::run method of it.
991 class DijkstraWizard : public TR
995 ///The type of the underlying graph.
996 typedef typename TR::Graph Graph;
998 typedef typename Graph::Node Node;
1000 typedef typename Graph::NodeIt NodeIt;
1002 typedef typename Graph::Edge Edge;
1004 typedef typename Graph::OutEdgeIt OutEdgeIt;
1006 ///The type of the map that stores the edge lengths.
1007 typedef typename TR::LengthMap LengthMap;
1008 ///The type of the length of the edges.
1009 typedef typename LengthMap::Value Value;
1010 ///\brief The type of the map that stores the last
1011 ///edges of the shortest paths.
1012 typedef typename TR::PredMap PredMap;
1013 ///The type of the map that stores the dists of the nodes.
1014 typedef typename TR::DistMap DistMap;
1015 ///The heap type used by the dijkstra algorithm.
1016 typedef typename TR::Heap Heap;
1019 DijkstraWizard() : TR() {}
1021 /// Constructor that requires parameters.
1023 /// Constructor that requires parameters.
1024 /// These parameters will be the default values for the traits class.
1025 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
1029 DijkstraWizard(const TR &b) : TR(b) {}
1031 ~DijkstraWizard() {}
1033 ///Runs Dijkstra algorithm from a given node.
1035 ///Runs Dijkstra algorithm from a given node.
1036 ///The node can be given by the \ref source function.
1039 if(Base::_source==INVALID) throw UninitializedParameter();
1040 Dijkstra<Graph,LengthMap,TR>
1041 dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
1042 if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred);
1043 if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist);
1044 dij.run(Base::_source);
1047 ///Runs Dijkstra algorithm from the given node.
1049 ///Runs Dijkstra algorithm from the given node.
1050 ///\param s is the given source.
1058 struct DefPredMapBase : public Base {
1060 static PredMap *createPredMap(const Graph &) { return 0; };
1061 DefPredMapBase(const TR &b) : TR(b) {}
1064 ///\brief \ref named-templ-param "Named parameter"
1065 ///function for setting PredMap type
1067 /// \ref named-templ-param "Named parameter"
1068 ///function for setting PredMap type
1071 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1073 Base::_pred=(void *)&t;
1074 return DijkstraWizard<DefPredMapBase<T> >(*this);
1078 struct DefDistMapBase : public Base {
1080 static DistMap *createDistMap(const Graph &) { return 0; };
1081 DefDistMapBase(const TR &b) : TR(b) {}
1084 ///\brief \ref named-templ-param "Named parameter"
1085 ///function for setting DistMap type
1087 /// \ref named-templ-param "Named parameter"
1088 ///function for setting DistMap type
1091 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1093 Base::_dist=(void *)&t;
1094 return DijkstraWizard<DefDistMapBase<T> >(*this);
1097 /// Sets the source node, from which the Dijkstra algorithm runs.
1099 /// Sets the source node, from which the Dijkstra algorithm runs.
1100 /// \param s is the source node.
1101 DijkstraWizard<TR> &source(Node s)
1109 ///Function type interface for Dijkstra algorithm.
1111 /// \ingroup flowalgs
1112 ///Function type interface for Dijkstra algorithm.
1114 ///This function also has several
1115 ///\ref named-templ-func-param "named parameters",
1116 ///they are declared as the members of class \ref DijkstraWizard.
1118 ///example shows how to use these parameters.
1120 /// dijkstra(g,length,source).predMap(preds).run();
1122 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1123 ///to the end of the parameter list.
1124 ///\sa DijkstraWizard
1126 template<class GR, class LM>
1127 DijkstraWizard<DijkstraWizardBase<GR,LM> >
1128 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1130 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1133 } //END OF NAMESPACE LEMON