2 * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 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>
30 /// \addtogroup flowalgs
33 template<class GR, class LM>
34 struct DijkstraDefaultTraits
39 typedef typename Graph::Node Node;
41 typedef typename Graph::Edge Edge;
42 ///The type of the map that stores the edge lengths.
44 ///It must meet the \ref ReadMap concept.
47 ///The type of the length of the edges.
48 typedef typename LM::ValueType ValueType;
49 ///The heap type used by the dijkstra algorithm.
50 typedef BinHeap<typename Graph::Node,
51 typename LM::ValueType,
52 typename GR::template NodeMap<int>,
53 std::less<ValueType> > Heap;
55 ///\brief The type of the map that stores the last
56 ///edges of the shortest paths.
58 ///It must meet the \ref WriteMap concept.
60 typedef typename Graph::template NodeMap<Edge> PredMap;
63 ///\todo Please document...
65 static PredMap *createPredMap(const Graph &G)
67 return new PredMap(G);
69 ///\brief The type of the map that stores the last but one
70 ///nodes of the shortest paths.
72 ///It must meet the \ref WriteMap concept.
74 typedef typename Graph::template NodeMap<Node> PredNodeMap;
77 ///\todo Please document...
79 static PredNodeMap *createPredNodeMap(const Graph &G)
81 return new PredNodeMap(G);
83 ///The type of the map that stores the dists of the nodes.
85 ///It must meet the \ref WriteMap concept.
87 typedef typename Graph::template NodeMap<ValueType> DistMap;
90 ///\todo Please document...
92 static DistMap *createDistMap(const Graph &G)
94 return new DistMap(G);
98 ///%Dijkstra algorithm class.
100 ///This class provides an efficient implementation of %Dijkstra algorithm.
101 ///The edge lengths are passed to the algorithm using a
102 ///\ref skeleton::ReadMap "ReadMap",
103 ///so it is easy to change it to any kind of length.
105 ///The type of the length is determined by the
106 ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map.
108 ///It is also possible to change the underlying priority heap.
110 ///\param GR The graph type the algorithm runs on. The default value is
112 ///\param LM This read-only
115 ///lengths of the edges. It is read once for each edge, so the map
116 ///may involve in relatively time consuming process to compute the edge
117 ///length if it is necessary. The default map type is
118 ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>"
119 ///\param Heap The heap type used by the %Dijkstra
120 ///algorithm. The default
121 ///is using \ref BinHeap "binary heap".
123 ///\author Jacint Szabo and Alpar Juttner
124 ///\todo We need a typedef-names should be standardized. (-:
125 ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
126 ///should not be fixed. (Problematic to solve).
129 template <typename GR,
133 template <typename GR=ListGraph,
134 typename LM=typename GR::template EdgeMap<int>,
135 typename TR=DijkstraDefaultTraits<GR,LM> >
140 ///The type of the underlying graph.
143 typedef typename Graph::Node Node;
145 typedef typename Graph::NodeIt NodeIt;
147 typedef typename Graph::Edge Edge;
149 typedef typename Graph::OutEdgeIt OutEdgeIt;
151 ///The type of the length of the edges.
152 typedef typename LM::ValueType ValueType;
153 ///The type of the map that stores the edge lengths.
154 typedef LM LengthMap;
155 ///\brief The type of the map that stores the last
156 ///edges of the shortest paths.
157 typedef typename TR::PredMap PredMap;
158 ///\brief The type of the map that stores the last but one
159 ///nodes of the shortest paths.
160 typedef typename TR::PredNodeMap PredNodeMap;
161 ///The type of the map that stores the dists of the nodes.
162 typedef typename TR::DistMap DistMap;
164 ///The heap type used by the dijkstra algorithm.
165 typedef typename TR::Heap Heap;
168 /// Pointer to the underlying graph.
170 /// Pointer to the length map
172 ///Pointer to the map of predecessors edges.
173 PredMap *predecessor;
174 ///Indicates if \ref predecessor is locally allocated (\c true) or not.
175 bool local_predecessor;
176 ///Pointer to the map of predecessors nodes.
177 PredNodeMap *pred_node;
178 ///Indicates if \ref pred_node is locally allocated (\c true) or not.
179 bool local_pred_node;
180 ///Pointer to the map of distances.
182 ///Indicates if \ref distance is locally allocated (\c true) or not.
185 ///The source node of the last execution.
188 ///Initializes the maps.
190 ///\todo Error if \c G or are \c NULL. What about \c length?
191 ///\todo Better memory allocation (instead of new).
195 local_predecessor = true;
196 predecessor = Traits::createPredMap(*G);
199 local_pred_node = true;
200 pred_node = Traits::createPredNodeMap(*G);
203 local_distance = true;
204 distance = Traits::createDistMap(*G);
211 struct SetPredMapTraits : public Traits {
213 ///\todo An exception should be thrown.
215 static PredMap *createPredMap(const Graph &G)
217 std::cerr << __FILE__ ":" << __LINE__ <<
218 ": error: Special maps should be manually created" << std::endl;
222 ///\ref named-templ-param "Named parameter" for setting PredMap's type
224 class SetPredMap : public Dijkstra< Graph,
226 SetPredMapTraits<T> > { };
229 struct SetPredNodeMapTraits : public Traits {
230 typedef T PredNodeMap;
231 ///\todo An exception should be thrown.
233 static PredNodeMap *createPredNodeMap(const Graph &G)
235 std::cerr << __FILE__ ":" << __LINE__ <<
236 ": error: Special maps should be manually created" << std::endl;
240 ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
242 class SetPredNodeMap : public Dijkstra< Graph,
244 SetPredNodeMapTraits<T> > { };
247 struct SetDistMapTraits : public Traits {
249 ///\todo An exception should be thrown.
251 static DistMap *createDistMap(const Graph &G)
253 std::cerr << __FILE__ ":" << __LINE__ <<
254 ": error: Special maps should be manually created" << std::endl;
258 ///\ref named-templ-param "Named parameter" for setting DistMap's type
260 class SetDistMap : public Dijkstra< Graph,
262 SetDistMapTraits<T> > { };
266 ///\param _G the graph the algorithm will run on.
267 ///\param _length the length map used by the algorithm.
268 Dijkstra(const Graph& _G, const LM& _length) :
269 G(&_G), length(&_length),
270 predecessor(NULL), local_predecessor(false),
271 pred_node(NULL), local_pred_node(false),
272 distance(NULL), local_distance(false)
278 if(local_predecessor) delete predecessor;
279 if(local_pred_node) delete pred_node;
280 if(local_distance) delete distance;
283 ///Sets the length map.
285 ///Sets the length map.
286 ///\return <tt> (*this) </tt>
287 Dijkstra &setLengthMap(const LM &m)
293 ///Sets the map storing the predecessor edges.
295 ///Sets the map storing the predecessor edges.
296 ///If you don't use this function before calling \ref run(),
297 ///it will allocate one. The destuctor deallocates this
298 ///automatically allocated map, of course.
299 ///\return <tt> (*this) </tt>
300 Dijkstra &setPredMap(PredMap &m)
302 if(local_predecessor) {
304 local_predecessor=false;
310 ///Sets the map storing the predecessor nodes.
312 ///Sets the map storing the predecessor nodes.
313 ///If you don't use this function before calling \ref run(),
314 ///it will allocate one. The destuctor deallocates this
315 ///automatically allocated map, of course.
316 ///\return <tt> (*this) </tt>
317 Dijkstra &setPredNodeMap(PredNodeMap &m)
319 if(local_pred_node) {
321 local_pred_node=false;
327 ///Sets the map storing the distances calculated by the algorithm.
329 ///Sets the map storing the distances calculated by the algorithm.
330 ///If you don't use this function before calling \ref run(),
331 ///it will allocate one. The destuctor deallocates this
332 ///automatically allocated map, of course.
333 ///\return <tt> (*this) </tt>
334 Dijkstra &setDistMap(DistMap &m)
338 local_distance=false;
344 ///Runs %Dijkstra algorithm from node \c s.
346 ///This method runs the %Dijkstra algorithm from a root node \c s
349 ///shortest path to each node. The algorithm computes
350 ///- The shortest path tree.
351 ///- The distance of each node from the root.
359 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
360 predecessor->set(u,INVALID);
361 pred_node->set(u,INVALID);
364 typename GR::template NodeMap<int> heap_map(*G,-1);
370 while ( !heap.empty() ) {
373 ValueType oldvalue=heap[v];
375 distance->set(v, oldvalue);
378 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
380 switch(heap.state(w)) {
382 heap.push(w,oldvalue+(*length)[e]);
383 predecessor->set(w,e);
387 if ( oldvalue+(*length)[e] < heap[w] ) {
388 heap.decrease(w, oldvalue+(*length)[e]);
389 predecessor->set(w,e);
393 case Heap::POST_HEAP:
400 ///The distance of a node from the root.
402 ///Returns the distance of a node from the root.
403 ///\pre \ref run() must be called before using this function.
404 ///\warning If node \c v in unreachable from the root the return value
405 ///of this funcion is undefined.
406 ValueType dist(Node v) const { return (*distance)[v]; }
408 ///Returns the 'previous edge' of the shortest path tree.
410 ///For a node \c v it returns the 'previous edge' of the shortest path tree,
411 ///i.e. it returns the last edge of a shortest path from the root to \c
412 ///v. It is \ref INVALID
413 ///if \c v is unreachable from the root or if \c v=s. The
414 ///shortest path tree used here is equal to the shortest path tree used in
415 ///\ref predNode(Node v). \pre \ref run() must be called before using
417 ///\todo predEdge could be a better name.
418 Edge pred(Node v) const { return (*predecessor)[v]; }
420 ///Returns the 'previous node' of the shortest path tree.
422 ///For a node \c v it returns the 'previous node' of the shortest path tree,
423 ///i.e. it returns the last but one node from a shortest path from the
424 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
425 ///\c v=s. The shortest path tree used here is equal to the shortest path
426 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
427 ///using this function.
428 Node predNode(Node v) const { return (*pred_node)[v]; }
430 ///Returns a reference to the NodeMap of distances.
432 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
433 ///be called before using this function.
434 const DistMap &distMap() const { return *distance;}
436 ///Returns a reference to the shortest path tree map.
438 ///Returns a reference to the NodeMap of the edges of the
439 ///shortest path tree.
440 ///\pre \ref run() must be called before using this function.
441 const PredMap &predMap() const { return *predecessor;}
443 ///Returns a reference to the map of nodes of shortest paths.
445 ///Returns a reference to the NodeMap of the last but one nodes of the
446 ///shortest path tree.
447 ///\pre \ref run() must be called before using this function.
448 const PredNodeMap &predNodeMap() const { return *pred_node;}
450 ///Checks if a node is reachable from the root.
452 ///Returns \c true if \c v is reachable from the root.
453 ///\note The root node is reported to be reached!
454 ///\pre \ref run() must be called before using this function.
456 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
469 ///The type of the underlying graph.
470 typedef typename TR::Graph Graph;
472 typedef typename Graph::Node Node;
474 typedef typename Graph::NodeIt NodeIt;
476 typedef typename Graph::Edge Edge;
478 typedef typename Graph::OutEdgeIt OutEdgeIt;
480 ///The type of the map that stores the edge lengths.
481 typedef typename TR::LengthMap LengthMap;
482 ///The type of the length of the edges.
483 typedef typename LengthMap::ValueType ValueType;
484 ///\brief The type of the map that stores the last
485 ///edges of the shortest paths.
486 typedef typename TR::PredMap PredMap;
487 ///\brief The type of the map that stores the last but one
488 ///nodes of the shortest paths.
489 typedef typename TR::PredNodeMap PredNodeMap;
490 ///The type of the map that stores the dists of the nodes.
491 typedef typename TR::DistMap DistMap;
493 ///The heap type used by the dijkstra algorithm.
494 typedef typename TR::Heap Heap;
496 /// Pointer to the underlying graph.
498 /// Pointer to the length map
499 const LengthMap *length;
500 ///Pointer to the map of predecessors edges.
501 PredMap *predecessor;
502 ///Pointer to the map of predecessors nodes.
503 PredNodeMap *pred_node;
504 ///Pointer to the map of distances.
510 _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0),
511 distance(0), source(INVALID) {}
513 _Dijkstra(const Graph &g,const LengthMap &l, Node s) :
514 G(&g), length(&l), predecessor(0), pred_node(0),
515 distance(0), source(s) {}
519 Dijkstra<Graph,LengthMap,TR> Dij(*G,*length);
520 if(predecessor) Dij.setPredMap(*predecessor);
521 if(pred_node) Dij.setPredNodeMap(*pred_node);
522 if(distance) Dij.setDistMap(*distance);
527 struct SetPredMapTraits : public Traits {typedef T PredMap;};
531 _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t)
533 _Dijkstra<SetPredMapTraits<T> > r;
537 r.pred_node=pred_node;
544 struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;};
547 _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t)
549 _Dijkstra<SetPredNodeMapTraits<T> > r;
552 r.predecessor=predecessor;
560 struct SetDistMapTraits : public Traits {typedef T DistMap;};
563 _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t)
565 _Dijkstra<SetPredMapTraits<T> > r;
568 r.predecessor=predecessor;
569 r.pred_node=pred_node;
576 _Dijkstra<TR> &setSource(Node s)
588 template<class GR, class LM>
589 _Dijkstra<DijkstraDefaultTraits<GR,LM> >
590 dijkstra(const GR &g,const LM &l,typename GR::Node s)
592 return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s);
597 } //END OF NAMESPACE LEMON