COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/dijkstra.h @ 1119:d3504fc075dc

Last change on this file since 1119:d3504fc075dc was 1119:d3504fc075dc, checked in by Alpar Juttner, 15 years ago

Two incomplete additions:

  • Exceptions
  • bool map indication reached nodes (NullMap? by default)
File size: 19.6 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_DIJKSTRA_H
18#define LEMON_DIJKSTRA_H
19
20///\ingroup flowalgs
21///\file
22///\brief Dijkstra algorithm.
23
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>
29
30namespace lemon {
31
32
33  class UninitializedData : public LogicError {};
34
35
36/// \addtogroup flowalgs
37/// @{
38
39  ///Default traits class of Dijkstra class.
40
41  ///Default traits class of Dijkstra class.
42  ///\param GR Graph type.
43  ///\param LM Type of length map.
44  template<class GR, class LM>
45  struct DijkstraDefaultTraits
46  {
47    ///The graph type the algorithm runs on.
48    typedef GR Graph;
49    ///The type of the map that stores the edge lengths.
50
51    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
52    ///
53    typedef LM LengthMap;
54    //The type of the length of the edges.
55    typedef typename LM::Value Value;
56    ///The heap type used by Dijkstra algorithm.
57
58    ///The heap type used by Dijkstra algorithm.
59    ///
60    ///\sa BinHeap
61    ///\sa Dijkstra
62    typedef BinHeap<typename Graph::Node,
63                    typename LM::Value,
64                    typename GR::template NodeMap<int>,
65                    std::less<Value> > Heap;
66
67    ///\brief The type of the map that stores the last
68    ///edges of the shortest paths.
69    ///
70    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
71    ///
72    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
73    ///Instantiates a PredMap.
74 
75    ///\todo Please document...
76    ///\todo The graph alone may be insufficient for the initialization
77    static PredMap *createPredMap(const GR &G)
78    {
79      return new PredMap(G);
80    }
81    ///\brief The type of the map that stores the last but one
82    ///nodes of the shortest paths.
83    ///
84    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
85    ///
86    typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
87    ///Instantiates a PredNodeMap.
88 
89    ///\todo Please document...
90    ///
91    static PredNodeMap *createPredNodeMap(const GR &G)
92    {
93      return new PredNodeMap(G);
94    }
95
96    ///The type of the map that stores whether a nodes is reached.
97 
98    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
99    ///By default it is a NullMap.
100    ///\todo If it is set to a real map, Dijkstra::reached() should read this.
101    ///\todo named parameter to set this type, function to read and write.
102    typedef NullMap<typename Graph::Node,bool> ReachedMap;
103    ///Instantiates a ReachedMap.
104 
105    ///\todo Please document...
106    ///
107    static ReachedMap *createReachedMap(const GR &G)
108    {
109      return new ReachedMap();
110    }
111    ///The type of the map that stores the dists of the nodes.
112 
113    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
114    ///
115    typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
116    ///Instantiates a DistMap.
117 
118    ///\todo Please document...
119    ///
120    static DistMap *createDistMap(const GR &G)
121    {
122      return new DistMap(G);
123    }
124  };
125 
126  ///%Dijkstra algorithm class.
127
128  ///This class provides an efficient implementation of %Dijkstra algorithm.
129  ///The edge lengths are passed to the algorithm using a
130  ///\ref concept::ReadMap "ReadMap",
131  ///so it is easy to change it to any kind of length.
132  ///
133  ///The type of the length is determined by the
134  ///\ref concept::ReadMap::Value "Value" of the length map.
135  ///
136  ///It is also possible to change the underlying priority heap.
137  ///
138  ///\param GR The graph type the algorithm runs on. The default value is
139  ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
140  ///is only passed to \ref DijkstraDefaultTraits.
141  ///\param LM This read-only
142  ///EdgeMap
143  ///determines the
144  ///lengths of the edges. It is read once for each edge, so the map
145  ///may involve in relatively time consuming process to compute the edge
146  ///length if it is necessary. The default map type is
147  ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
148  ///The value of LM is not used directly by Dijkstra, it
149  ///is only passed to \ref DijkstraDefaultTraits.
150  ///\param TR Traits class to set various data types used by the algorithm.
151  ///The default traits class is
152  ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
153  ///See \ref DijkstraDefaultTraits for the documentation of
154  ///a Dijkstra traits class.
155  ///
156  ///\author Jacint Szabo and Alpar Juttner
157  ///\todo We need a typedef-names should be standardized. (-:
158
159#ifdef DOXYGEN
160  template <typename GR,
161            typename LM,
162            typename TR>
163#else
164  template <typename GR=ListGraph,
165            typename LM=typename GR::template EdgeMap<int>,
166            typename TR=DijkstraDefaultTraits<GR,LM> >
167#endif
168  class Dijkstra {
169  public:
170    ///Exception thrown by dijkstra.
171    class UninitializedData : public lemon::UninitializedData {};
172
173    typedef TR Traits;
174    ///The type of the underlying graph.
175    typedef typename TR::Graph Graph;
176    ///\e
177    typedef typename Graph::Node Node;
178    ///\e
179    typedef typename Graph::NodeIt NodeIt;
180    ///\e
181    typedef typename Graph::Edge Edge;
182    ///\e
183    typedef typename Graph::OutEdgeIt OutEdgeIt;
184   
185    ///The type of the length of the edges.
186    typedef typename TR::LengthMap::Value Value;
187    ///The type of the map that stores the edge lengths.
188    typedef typename TR::LengthMap LengthMap;
189    ///\brief The type of the map that stores the last
190    ///edges of the shortest paths.
191    typedef typename TR::PredMap PredMap;
192    ///\brief The type of the map that stores the last but one
193    ///nodes of the shortest paths.
194    typedef typename TR::PredNodeMap PredNodeMap;
195    ///The type of the map indicating if a node is reached.
196    typedef typename TR::ReachedMap ReachedMap;
197    ///The type of the map that stores the dists of the nodes.
198    typedef typename TR::DistMap DistMap;
199    ///The heap type used by the dijkstra algorithm.
200    typedef typename TR::Heap Heap;
201  private:
202    /// Pointer to the underlying graph.
203    const Graph *G;
204    /// Pointer to the length map
205    const LengthMap *length;
206    ///Pointer to the map of predecessors edges.
207    PredMap *_pred;
208    ///Indicates if \ref _pred is locally allocated (\c true) or not.
209    bool local_pred;
210    ///Pointer to the map of predecessors nodes.
211    PredNodeMap *pred_node;
212    ///Indicates if \ref pred_node is locally allocated (\c true) or not.
213    bool local_pred_node;
214    ///Pointer to the map of distances.
215    DistMap *distance;
216    ///Indicates if \ref distance is locally allocated (\c true) or not.
217    bool local_distance;
218    ///Pointer to the map of reached status of the nodes.
219    ReachedMap *_reached;
220    ///Indicates if \ref _reached is locally allocated (\c true) or not.
221    bool local_reached;
222
223    ///The source node of the last execution.
224    Node source;
225
226    ///Initializes the maps.
227   
228    ///\todo Error if \c G or are \c NULL. What about \c length?
229    ///\todo Better memory allocation (instead of new).
230    void init_maps()
231    {
232      if(!_pred) {
233        local_pred = true;
234        _pred = Traits::createPredMap(*G);
235      }
236      if(!pred_node) {
237        local_pred_node = true;
238        pred_node = Traits::createPredNodeMap(*G);
239      }
240      if(!distance) {
241        local_distance = true;
242        distance = Traits::createDistMap(*G);
243      }
244      if(!_reached) {
245        local_reached = true;
246        _reached = Traits::createReachedMap(*G);
247      }
248    }
249   
250  public :
251 
252    template <class T>
253    struct DefPredMapTraits : public Traits {
254      typedef T PredMap;
255      ///\todo An exception should be thrown.
256      ///
257      static PredMap *createPredMap(const Graph &G)
258      {
259        throw UninitializedData();
260      }
261    };
262    ///\ref named-templ-param "Named parameter" for setting PredMap type
263
264    ///\ref named-templ-param "Named parameter" for setting PredMap type
265    ///
266    template <class T>
267    class DefPredMap : public Dijkstra< Graph,
268                                        LengthMap,
269                                        DefPredMapTraits<T> > { };
270   
271    template <class T>
272    struct DefPredNodeMapTraits : public Traits {
273      typedef T PredNodeMap;
274      ///\todo An exception should be thrown.
275      ///
276      static PredNodeMap *createPredNodeMap(const Graph &G)
277      {
278        throw UninitializedData();
279      }
280    };
281    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
282
283    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
284    ///
285    template <class T>
286    class DefPredNodeMap : public Dijkstra< Graph,
287                                            LengthMap,
288                                            DefPredNodeMapTraits<T> > { };
289   
290    template <class T>
291    struct DefDistMapTraits : public Traits {
292      typedef T DistMap;
293      ///\todo An exception should be thrown.
294      ///
295      static DistMap *createDistMap(const Graph &G)
296      {
297        throw UninitializedData();
298      }
299    };
300    ///\ref named-templ-param "Named parameter" for setting DistMap type
301
302    ///\ref named-templ-param "Named parameter" for setting DistMap type
303    ///
304    template <class T>
305    class DefDistMap : public Dijkstra< Graph,
306                                        LengthMap,
307                                        DefDistMapTraits<T> > { };
308   
309    ///Constructor.
310   
311    ///\param _G the graph the algorithm will run on.
312    ///\param _length the length map used by the algorithm.
313    Dijkstra(const Graph& _G, const LengthMap& _length) :
314      G(&_G), length(&_length),
315      _pred(NULL), local_pred(false),
316      pred_node(NULL), local_pred_node(false),
317      distance(NULL), local_distance(false),
318      _reached(NULL), local_reached(false)
319    { }
320   
321    ///Destructor.
322    ~Dijkstra()
323    {
324      if(local_pred) delete _pred;
325      if(local_pred_node) delete pred_node;
326      if(local_distance) delete distance;
327      if(local_reached) delete _reached;
328    }
329
330    ///Sets the length map.
331
332    ///Sets the length map.
333    ///\return <tt> (*this) </tt>
334    Dijkstra &lengthMap(const LengthMap &m)
335    {
336      length = &m;
337      return *this;
338    }
339
340    ///Sets the map storing the predecessor edges.
341
342    ///Sets the map storing the predecessor edges.
343    ///If you don't use this function before calling \ref run(),
344    ///it will allocate one. The destuctor deallocates this
345    ///automatically allocated map, of course.
346    ///\return <tt> (*this) </tt>
347    Dijkstra &predMap(PredMap &m)
348    {
349      if(local_pred) {
350        delete _pred;
351        local_pred=false;
352      }
353      _pred = &m;
354      return *this;
355    }
356
357    ///Sets the map storing the predecessor nodes.
358
359    ///Sets the map storing the predecessor nodes.
360    ///If you don't use this function before calling \ref run(),
361    ///it will allocate one. The destuctor deallocates this
362    ///automatically allocated map, of course.
363    ///\return <tt> (*this) </tt>
364    Dijkstra &predNodeMap(PredNodeMap &m)
365    {
366      if(local_pred_node) {
367        delete pred_node;
368        local_pred_node=false;
369      }
370      pred_node = &m;
371      return *this;
372    }
373
374    ///Sets the map storing the distances calculated by the algorithm.
375
376    ///Sets the map storing the distances calculated by the algorithm.
377    ///If you don't use this function before calling \ref run(),
378    ///it will allocate one. The destuctor deallocates this
379    ///automatically allocated map, of course.
380    ///\return <tt> (*this) </tt>
381    Dijkstra &distMap(DistMap &m)
382    {
383      if(local_distance) {
384        delete distance;
385        local_distance=false;
386      }
387      distance = &m;
388      return *this;
389    }
390   
391  ///Runs %Dijkstra algorithm from node \c s.
392
393  ///This method runs the %Dijkstra algorithm from a root node \c s
394  ///in order to
395  ///compute the
396  ///shortest path to each node. The algorithm computes
397  ///- The shortest path tree.
398  ///- The distance of each node from the root.
399  ///\todo heap_map's type could also be in the traits class.
400    void run(Node s) {
401     
402      init_maps();
403     
404      source = s;
405     
406      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
407        _pred->set(u,INVALID);
408        pred_node->set(u,INVALID);
409        ///\todo *_reached is not set to false.
410      }
411     
412      typename Graph::template NodeMap<int> heap_map(*G,-1);
413     
414      Heap heap(heap_map);
415     
416      heap.push(s,0);
417     
418      while ( !heap.empty() ) {
419       
420        Node v=heap.top();
421        _reached->set(v,true);
422        Value oldvalue=heap[v];
423        heap.pop();
424        distance->set(v, oldvalue);
425       
426       
427        for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
428          Node w=G->target(e);
429          switch(heap.state(w)) {
430          case Heap::PRE_HEAP:
431            heap.push(w,oldvalue+(*length)[e]);
432            _pred->set(w,e);
433            pred_node->set(w,v);
434            break;
435          case Heap::IN_HEAP:
436            if ( oldvalue+(*length)[e] < heap[w] ) {
437              heap.decrease(w, oldvalue+(*length)[e]);
438              _pred->set(w,e);
439              pred_node->set(w,v);
440            }
441            break;
442          case Heap::POST_HEAP:
443            break;
444          }
445        }
446      }
447    }
448   
449    ///The distance of a node from the root.
450
451    ///Returns the distance of a node from the root.
452    ///\pre \ref run() must be called before using this function.
453    ///\warning If node \c v in unreachable from the root the return value
454    ///of this funcion is undefined.
455    Value dist(Node v) const { return (*distance)[v]; }
456
457    ///Returns the 'previous edge' of the shortest path tree.
458
459    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
460    ///i.e. it returns the last edge of a shortest path from the root to \c
461    ///v. It is \ref INVALID
462    ///if \c v is unreachable from the root or if \c v=s. The
463    ///shortest path tree used here is equal to the shortest path tree used in
464    ///\ref predNode(Node v).  \pre \ref run() must be called before using
465    ///this function.
466    ///\todo predEdge could be a better name.
467    Edge pred(Node v) const { return (*_pred)[v]; }
468
469    ///Returns the 'previous node' of the shortest path tree.
470
471    ///For a node \c v it returns the 'previous node' of the shortest path tree,
472    ///i.e. it returns the last but one node from a shortest path from the
473    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
474    ///\c v=s. The shortest path tree used here is equal to the shortest path
475    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
476    ///using this function.
477    Node predNode(Node v) const { return (*pred_node)[v]; }
478   
479    ///Returns a reference to the NodeMap of distances.
480
481    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
482    ///be called before using this function.
483    const DistMap &distMap() const { return *distance;}
484 
485    ///Returns a reference to the shortest path tree map.
486
487    ///Returns a reference to the NodeMap of the edges of the
488    ///shortest path tree.
489    ///\pre \ref run() must be called before using this function.
490    const PredMap &predMap() const { return *_pred;}
491 
492    ///Returns a reference to the map of nodes of shortest paths.
493
494    ///Returns a reference to the NodeMap of the last but one nodes of the
495    ///shortest path tree.
496    ///\pre \ref run() must be called before using this function.
497    const PredNodeMap &predNodeMap() const { return *pred_node;}
498
499    ///Checks if a node is reachable from the root.
500
501    ///Returns \c true if \c v is reachable from the root.
502    ///\note The root node is reported to be reached!
503    ///\pre \ref run() must be called before using this function.
504    ///
505    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
506   
507  };
508
509  template<class GR,class LM>
510  class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
511  {
512
513    typedef DijkstraDefaultTraits<GR,LM> Base;
514  protected:
515    /// Pointer to the underlying graph.
516    void *_g;
517    /// Pointer to the length map
518    void *_length;
519    ///Pointer to the map of predecessors edges.
520    void *_pred;
521    ///Pointer to the map of predecessors nodes.
522    void *_predNode;
523    ///Pointer to the map of distances.
524    void *_dist;
525    ///Pointer to the source node.
526    void *_source;
527
528    typedef typename Base::Graph::Node Node;
529
530    public:
531    DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
532                       _dist(0), _source(INVALID) {}
533
534    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
535      _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
536                  _dist(0), _source((void *)&s) {}
537
538  };
539 
540  ///\e
541
542  ///\e
543  ///
544  template<class TR>
545  class DijkstraWizard : public TR
546  {
547    typedef TR Base;
548
549    //The type of the underlying graph.
550    typedef typename TR::Graph Graph;
551    //\e
552    typedef typename Graph::Node Node;
553    //\e
554    typedef typename Graph::NodeIt NodeIt;
555    //\e
556    typedef typename Graph::Edge Edge;
557    //\e
558    typedef typename Graph::OutEdgeIt OutEdgeIt;
559   
560    //The type of the map that stores the edge lengths.
561    typedef typename TR::LengthMap LengthMap;
562    //The type of the length of the edges.
563    typedef typename LengthMap::Value Value;
564    //\brief The type of the map that stores the last
565    //edges of the shortest paths.
566    typedef typename TR::PredMap PredMap;
567    //\brief The type of the map that stores the last but one
568    //nodes of the shortest paths.
569    typedef typename TR::PredNodeMap PredNodeMap;
570    //The type of the map that stores the dists of the nodes.
571    typedef typename TR::DistMap DistMap;
572
573    //The heap type used by the dijkstra algorithm.
574    typedef typename TR::Heap Heap;
575public:
576    DijkstraWizard() : TR() {}
577
578    DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
579      TR(g,l,s) {}
580
581    DijkstraWizard(const TR &b) : TR(b) {}
582
583    ~DijkstraWizard() {}
584
585    ///\e
586    void run()
587    {
588      if(_source==0) throw UninitializedData();
589      Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
590      if(_pred) Dij.predMap(*(PredMap*)_pred);
591      if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
592      if(_dist) Dij.distMap(*(DistMap*)_dist);
593      Dij.run(*(Node*)_source);
594    }
595
596    ///\e
597    void run(Node s)
598    {
599      _source=(void *)&s;
600      run();
601    }
602
603    template<class T>
604    struct DefPredMapBase : public Base {
605      typedef T PredMap;
606      static PredMap *createPredMap(const Graph &G) { return 0; };
607      DefPredMapBase(const Base &b) : Base(b) {}
608    };
609   
610    ///\e
611    template<class T>
612    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
613    {
614      _pred=(void *)&t;
615      return DijkstraWizard<DefPredMapBase<T> >(*this);
616    }
617   
618
619    template<class T>
620    struct DefPredNodeMapBase : public Base {
621      typedef T PredNodeMap;
622      static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
623      DefPredNodeMapBase(const Base &b) : Base(b) {}
624    };
625   
626    ///\e
627    template<class T>
628    DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
629    {
630      _predNode=(void *)&t;
631      return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
632    }
633   
634    template<class T>
635    struct DefDistMapBase : public Base {
636      typedef T DistMap;
637      static DistMap *createDistMap(const Graph &G) { return 0; };
638      DefDistMapBase(const Base &b) : Base(b) {}
639    };
640   
641    ///\e
642    template<class T>
643    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
644    {
645      _dist=(void *)&t;
646      return DijkstraWizard<DefDistMapBase<T> >(*this);
647    }
648   
649    ///\e
650    DijkstraWizard<TR> &source(Node s)
651    {
652      source=(void *)&s;
653      return *this;
654    }
655   
656  };
657 
658  ///\e
659
660  ///\todo Please document...
661  ///
662  template<class GR, class LM>
663  DijkstraWizard<DijkstraWizardBase<GR,LM> >
664  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
665  {
666    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
667  }
668
669/// @}
670 
671} //END OF NAMESPACE LEMON
672
673#endif
674
Note: See TracBrowser for help on using the repository browser.