In algorithm window maps can be selected and reated through MapSelector widget.
2 * lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 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