COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 280:e7f8647ce760

Last change on this file since 280:e7f8647ce760 was 280:e7f8647ce760, checked in by Alpar Juttner <alpar@…>, 16 years ago

Remove todo-s and convert them to trac tickets

File size: 41.7 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_DIJKSTRA_H
20#define LEMON_DIJKSTRA_H
21
22///\ingroup shortest_path
23///\file
24///\brief Dijkstra algorithm.
25
26#include <limits>
27#include <lemon/list_graph.h>
28#include <lemon/bin_heap.h>
29#include <lemon/bits/path_dump.h>
30#include <lemon/core.h>
31#include <lemon/error.h>
32#include <lemon/maps.h>
33
34namespace lemon {
35
36  /// \brief Default operation traits for the Dijkstra algorithm class.
37  ///
38  /// This operation traits class defines all computational operations and
39  /// constants which are used in the Dijkstra algorithm.
40  template <typename Value>
41  struct DijkstraDefaultOperationTraits {
42    /// \brief Gives back the zero value of the type.
43    static Value zero() {
44      return static_cast<Value>(0);
45    }
46    /// \brief Gives back the sum of the given two elements.
47    static Value plus(const Value& left, const Value& right) {
48      return left + right;
49    }
50    /// \brief Gives back true only if the first value is less than the second.
51    static bool less(const Value& left, const Value& right) {
52      return left < right;
53    }
54  };
55
56  /// \brief Widest path operation traits for the Dijkstra algorithm class.
57  ///
58  /// This operation traits class defines all computational operations and
59  /// constants which are used in the Dijkstra algorithm for widest path
60  /// computation.
61  ///
62  /// \see DijkstraDefaultOperationTraits
63  template <typename Value>
64  struct DijkstraWidestPathOperationTraits {
65    /// \brief Gives back the maximum value of the type.
66    static Value zero() {
67      return std::numeric_limits<Value>::max();
68    }
69    /// \brief Gives back the minimum of the given two elements.
70    static Value plus(const Value& left, const Value& right) {
71      return std::min(left, right);
72    }
73    /// \brief Gives back true only if the first value is less than the second.
74    static bool less(const Value& left, const Value& right) {
75      return left < right;
76    }
77  };
78
79  ///Default traits class of Dijkstra class.
80
81  ///Default traits class of Dijkstra class.
82  ///\tparam GR The type of the digraph.
83  ///\tparam LM The type of the length map.
84  template<class GR, class LM>
85  struct DijkstraDefaultTraits
86  {
87    ///The type of the digraph the algorithm runs on.
88    typedef GR Digraph;
89
90    ///The type of the map that stores the arc lengths.
91
92    ///The type of the map that stores the arc lengths.
93    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
94    typedef LM LengthMap;
95    ///The type of the length of the arcs.
96    typedef typename LM::Value Value;
97
98    /// Operation traits for Dijkstra algorithm.
99
100    /// This class defines the operations that are used in the algorithm.
101    /// \see DijkstraDefaultOperationTraits
102    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
103
104    /// The cross reference type used by the heap.
105
106    /// The cross reference type used by the heap.
107    /// Usually it is \c Digraph::NodeMap<int>.
108    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
109    ///Instantiates a \ref HeapCrossRef.
110
111    ///This function instantiates a \ref HeapCrossRef.
112    /// \param g is the digraph, to which we would like to define the
113    /// \ref HeapCrossRef.
114    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
115    {
116      return new HeapCrossRef(g);
117    }
118
119    ///The heap type used by the Dijkstra algorithm.
120
121    ///The heap type used by the Dijkstra algorithm.
122    ///
123    ///\sa BinHeap
124    ///\sa Dijkstra
125    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
126    ///Instantiates a \ref Heap.
127
128    ///This function instantiates a \ref Heap.
129    static Heap *createHeap(HeapCrossRef& r)
130    {
131      return new Heap(r);
132    }
133
134    ///\brief The type of the map that stores the predecessor
135    ///arcs of the shortest paths.
136    ///
137    ///The type of the map that stores the predecessor
138    ///arcs of the shortest paths.
139    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
140    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
141    ///Instantiates a \ref PredMap.
142
143    ///This function instantiates a \ref PredMap.
144    ///\param g is the digraph, to which we would like to define the
145    ///\ref PredMap.
146    static PredMap *createPredMap(const Digraph &g)
147    {
148      return new PredMap(g);
149    }
150
151    ///The type of the map that indicates which nodes are processed.
152
153    ///The type of the map that indicates which nodes are processed.
154    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
155    ///By default it is a NullMap.
156    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
157    ///Instantiates a \ref ProcessedMap.
158
159    ///This function instantiates a \ref ProcessedMap.
160    ///\param g is the digraph, to which
161    ///we would like to define the \ref ProcessedMap
162#ifdef DOXYGEN
163    static ProcessedMap *createProcessedMap(const Digraph &g)
164#else
165    static ProcessedMap *createProcessedMap(const Digraph &)
166#endif
167    {
168      return new ProcessedMap();
169    }
170
171    ///The type of the map that stores the distances of the nodes.
172
173    ///The type of the map that stores the distances of the nodes.
174    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
175    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
176    ///Instantiates a \ref DistMap.
177
178    ///This function instantiates a \ref DistMap.
179    ///\param g is the digraph, to which we would like to define
180    ///the \ref DistMap
181    static DistMap *createDistMap(const Digraph &g)
182    {
183      return new DistMap(g);
184    }
185  };
186
187  ///%Dijkstra algorithm class.
188
189  /// \ingroup shortest_path
190  ///This class provides an efficient implementation of the %Dijkstra algorithm.
191  ///
192  ///The arc lengths are passed to the algorithm using a
193  ///\ref concepts::ReadMap "ReadMap",
194  ///so it is easy to change it to any kind of length.
195  ///The type of the length is determined by the
196  ///\ref concepts::ReadMap::Value "Value" of the length map.
197  ///It is also possible to change the underlying priority heap.
198  ///
199  ///There is also a \ref dijkstra() "function type interface" for the
200  ///%Dijkstra algorithm, which is convenient in the simplier cases and
201  ///it can be used easier.
202  ///
203  ///\tparam GR The type of the digraph the algorithm runs on.
204  ///The default value is \ref ListDigraph.
205  ///The value of GR is not used directly by \ref Dijkstra, it is only
206  ///passed to \ref DijkstraDefaultTraits.
207  ///\tparam LM A readable arc map that determines the lengths of the
208  ///arcs. It is read once for each arc, so the map may involve in
209  ///relatively time consuming process to compute the arc lengths if
210  ///it is necessary. The default map type is \ref
211  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
212  ///The value of LM is not used directly by \ref Dijkstra, it is only
213  ///passed to \ref DijkstraDefaultTraits.
214  ///\tparam TR Traits class to set various data types used by the algorithm.
215  ///The default traits class is \ref DijkstraDefaultTraits
216  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
217  ///for the documentation of a Dijkstra traits class.
218#ifdef DOXYGEN
219  template <typename GR, typename LM, typename TR>
220#else
221  template <typename GR=ListDigraph,
222            typename LM=typename GR::template ArcMap<int>,
223            typename TR=DijkstraDefaultTraits<GR,LM> >
224#endif
225  class Dijkstra {
226  public:
227    ///\ref Exception for uninitialized parameters.
228
229    ///This error represents problems in the initialization of the
230    ///parameters of the algorithm.
231    class UninitializedParameter : public lemon::UninitializedParameter {
232    public:
233      virtual const char* what() const throw() {
234        return "lemon::Dijkstra::UninitializedParameter";
235      }
236    };
237
238    ///The type of the digraph the algorithm runs on.
239    typedef typename TR::Digraph Digraph;
240
241    ///The type of the length of the arcs.
242    typedef typename TR::LengthMap::Value Value;
243    ///The type of the map that stores the arc lengths.
244    typedef typename TR::LengthMap LengthMap;
245    ///\brief The type of the map that stores the predecessor arcs of the
246    ///shortest paths.
247    typedef typename TR::PredMap PredMap;
248    ///The type of the map that stores the distances of the nodes.
249    typedef typename TR::DistMap DistMap;
250    ///The type of the map that indicates which nodes are processed.
251    typedef typename TR::ProcessedMap ProcessedMap;
252    ///The type of the paths.
253    typedef PredMapPath<Digraph, PredMap> Path;
254    ///The cross reference type used for the current heap.
255    typedef typename TR::HeapCrossRef HeapCrossRef;
256    ///The heap type used by the algorithm.
257    typedef typename TR::Heap Heap;
258    ///The operation traits class.
259    typedef typename TR::OperationTraits OperationTraits;
260
261    ///The traits class.
262    typedef TR Traits;
263
264  private:
265
266    typedef typename Digraph::Node Node;
267    typedef typename Digraph::NodeIt NodeIt;
268    typedef typename Digraph::Arc Arc;
269    typedef typename Digraph::OutArcIt OutArcIt;
270
271    //Pointer to the underlying digraph.
272    const Digraph *G;
273    //Pointer to the length map.
274    const LengthMap *length;
275    //Pointer to the map of predecessors arcs.
276    PredMap *_pred;
277    //Indicates if _pred is locally allocated (true) or not.
278    bool local_pred;
279    //Pointer to the map of distances.
280    DistMap *_dist;
281    //Indicates if _dist is locally allocated (true) or not.
282    bool local_dist;
283    //Pointer to the map of processed status of the nodes.
284    ProcessedMap *_processed;
285    //Indicates if _processed is locally allocated (true) or not.
286    bool local_processed;
287    //Pointer to the heap cross references.
288    HeapCrossRef *_heap_cross_ref;
289    //Indicates if _heap_cross_ref is locally allocated (true) or not.
290    bool local_heap_cross_ref;
291    //Pointer to the heap.
292    Heap *_heap;
293    //Indicates if _heap is locally allocated (true) or not.
294    bool local_heap;
295
296    //Creates the maps if necessary.
297    void create_maps()
298    {
299      if(!_pred) {
300        local_pred = true;
301        _pred = Traits::createPredMap(*G);
302      }
303      if(!_dist) {
304        local_dist = true;
305        _dist = Traits::createDistMap(*G);
306      }
307      if(!_processed) {
308        local_processed = true;
309        _processed = Traits::createProcessedMap(*G);
310      }
311      if (!_heap_cross_ref) {
312        local_heap_cross_ref = true;
313        _heap_cross_ref = Traits::createHeapCrossRef(*G);
314      }
315      if (!_heap) {
316        local_heap = true;
317        _heap = Traits::createHeap(*_heap_cross_ref);
318      }
319    }
320
321  public:
322
323    typedef Dijkstra Create;
324
325    ///\name Named template parameters
326
327    ///@{
328
329    template <class T>
330    struct SetPredMapTraits : public Traits {
331      typedef T PredMap;
332      static PredMap *createPredMap(const Digraph &)
333      {
334        throw UninitializedParameter();
335      }
336    };
337    ///\brief \ref named-templ-param "Named parameter" for setting
338    ///\ref PredMap type.
339    ///
340    ///\ref named-templ-param "Named parameter" for setting
341    ///\ref PredMap type.
342    template <class T>
343    struct SetPredMap
344      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
345      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
346    };
347
348    template <class T>
349    struct SetDistMapTraits : public Traits {
350      typedef T DistMap;
351      static DistMap *createDistMap(const Digraph &)
352      {
353        throw UninitializedParameter();
354      }
355    };
356    ///\brief \ref named-templ-param "Named parameter" for setting
357    ///\ref DistMap type.
358    ///
359    ///\ref named-templ-param "Named parameter" for setting
360    ///\ref DistMap type.
361    template <class T>
362    struct SetDistMap
363      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
364      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
365    };
366
367    template <class T>
368    struct SetProcessedMapTraits : public Traits {
369      typedef T ProcessedMap;
370      static ProcessedMap *createProcessedMap(const Digraph &)
371      {
372        throw UninitializedParameter();
373      }
374    };
375    ///\brief \ref named-templ-param "Named parameter" for setting
376    ///\ref ProcessedMap type.
377    ///
378    ///\ref named-templ-param "Named parameter" for setting
379    ///\ref ProcessedMap type.
380    template <class T>
381    struct SetProcessedMap
382      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
383      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
384    };
385
386    struct SetStandardProcessedMapTraits : public Traits {
387      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
388      static ProcessedMap *createProcessedMap(const Digraph &g)
389      {
390        return new ProcessedMap(g);
391      }
392    };
393    ///\brief \ref named-templ-param "Named parameter" for setting
394    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
395    ///
396    ///\ref named-templ-param "Named parameter" for setting
397    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
398    ///If you don't set it explicitly, it will be automatically allocated.
399    struct SetStandardProcessedMap
400      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
401      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
402      Create;
403    };
404
405    template <class H, class CR>
406    struct SetHeapTraits : public Traits {
407      typedef CR HeapCrossRef;
408      typedef H Heap;
409      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
410        throw UninitializedParameter();
411      }
412      static Heap *createHeap(HeapCrossRef &)
413      {
414        throw UninitializedParameter();
415      }
416    };
417    ///\brief \ref named-templ-param "Named parameter" for setting
418    ///heap and cross reference type
419    ///
420    ///\ref named-templ-param "Named parameter" for setting heap and cross
421    ///reference type.
422    template <class H, class CR = typename Digraph::template NodeMap<int> >
423    struct SetHeap
424      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
425      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
426    };
427
428    template <class H, class CR>
429    struct SetStandardHeapTraits : public Traits {
430      typedef CR HeapCrossRef;
431      typedef H Heap;
432      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
433        return new HeapCrossRef(G);
434      }
435      static Heap *createHeap(HeapCrossRef &R)
436      {
437        return new Heap(R);
438      }
439    };
440    ///\brief \ref named-templ-param "Named parameter" for setting
441    ///heap and cross reference type with automatic allocation
442    ///
443    ///\ref named-templ-param "Named parameter" for setting heap and cross
444    ///reference type. It can allocate the heap and the cross reference
445    ///object if the cross reference's constructor waits for the digraph as
446    ///parameter and the heap's constructor waits for the cross reference.
447    template <class H, class CR = typename Digraph::template NodeMap<int> >
448    struct SetStandardHeap
449      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
450      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
451      Create;
452    };
453
454    template <class T>
455    struct SetOperationTraitsTraits : public Traits {
456      typedef T OperationTraits;
457    };
458
459    /// \brief \ref named-templ-param "Named parameter" for setting
460    ///\ref OperationTraits type
461    ///
462    ///\ref named-templ-param "Named parameter" for setting
463    ///\ref OperationTraits type.
464    template <class T>
465    struct SetOperationTraits
466      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
467      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
468      Create;
469    };
470
471    ///@}
472
473  protected:
474
475    Dijkstra() {}
476
477  public:
478
479    ///Constructor.
480
481    ///Constructor.
482    ///\param _g The digraph the algorithm runs on.
483    ///\param _length The length map used by the algorithm.
484    Dijkstra(const Digraph& _g, const LengthMap& _length) :
485      G(&_g), length(&_length),
486      _pred(NULL), local_pred(false),
487      _dist(NULL), local_dist(false),
488      _processed(NULL), local_processed(false),
489      _heap_cross_ref(NULL), local_heap_cross_ref(false),
490      _heap(NULL), local_heap(false)
491    { }
492
493    ///Destructor.
494    ~Dijkstra()
495    {
496      if(local_pred) delete _pred;
497      if(local_dist) delete _dist;
498      if(local_processed) delete _processed;
499      if(local_heap_cross_ref) delete _heap_cross_ref;
500      if(local_heap) delete _heap;
501    }
502
503    ///Sets the length map.
504
505    ///Sets the length map.
506    ///\return <tt> (*this) </tt>
507    Dijkstra &lengthMap(const LengthMap &m)
508    {
509      length = &m;
510      return *this;
511    }
512
513    ///Sets the map that stores the predecessor arcs.
514
515    ///Sets the map that stores the predecessor arcs.
516    ///If you don't use this function before calling \ref run(),
517    ///it will allocate one. The destructor deallocates this
518    ///automatically allocated map, of course.
519    ///\return <tt> (*this) </tt>
520    Dijkstra &predMap(PredMap &m)
521    {
522      if(local_pred) {
523        delete _pred;
524        local_pred=false;
525      }
526      _pred = &m;
527      return *this;
528    }
529
530    ///Sets the map that indicates which nodes are processed.
531
532    ///Sets the map that indicates which nodes are processed.
533    ///If you don't use this function before calling \ref run(),
534    ///it will allocate one. The destructor deallocates this
535    ///automatically allocated map, of course.
536    ///\return <tt> (*this) </tt>
537    Dijkstra &processedMap(ProcessedMap &m)
538    {
539      if(local_processed) {
540        delete _processed;
541        local_processed=false;
542      }
543      _processed = &m;
544      return *this;
545    }
546
547    ///Sets the map that stores the distances of the nodes.
548
549    ///Sets the map that stores the distances of the nodes calculated by the
550    ///algorithm.
551    ///If you don't use this function before calling \ref run(),
552    ///it will allocate one. The destructor deallocates this
553    ///automatically allocated map, of course.
554    ///\return <tt> (*this) </tt>
555    Dijkstra &distMap(DistMap &m)
556    {
557      if(local_dist) {
558        delete _dist;
559        local_dist=false;
560      }
561      _dist = &m;
562      return *this;
563    }
564
565    ///Sets the heap and the cross reference used by algorithm.
566
567    ///Sets the heap and the cross reference used by algorithm.
568    ///If you don't use this function before calling \ref run(),
569    ///it will allocate one. The destructor deallocates this
570    ///automatically allocated heap and cross reference, of course.
571    ///\return <tt> (*this) </tt>
572    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
573    {
574      if(local_heap_cross_ref) {
575        delete _heap_cross_ref;
576        local_heap_cross_ref=false;
577      }
578      _heap_cross_ref = &cr;
579      if(local_heap) {
580        delete _heap;
581        local_heap=false;
582      }
583      _heap = &hp;
584      return *this;
585    }
586
587  private:
588
589    void finalizeNodeData(Node v,Value dst)
590    {
591      _processed->set(v,true);
592      _dist->set(v, dst);
593    }
594
595  public:
596
597    ///\name Execution control
598    ///The simplest way to execute the algorithm is to use one of the
599    ///member functions called \ref lemon::Dijkstra::run() "run()".
600    ///\n
601    ///If you need more control on the execution, first you must call
602    ///\ref lemon::Dijkstra::init() "init()", then you can add several
603    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
604    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
605    ///actual path computation.
606
607    ///@{
608
609    ///Initializes the internal data structures.
610
611    ///Initializes the internal data structures.
612    ///
613    void init()
614    {
615      create_maps();
616      _heap->clear();
617      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
618        _pred->set(u,INVALID);
619        _processed->set(u,false);
620        _heap_cross_ref->set(u,Heap::PRE_HEAP);
621      }
622    }
623
624    ///Adds a new source node.
625
626    ///Adds a new source node to the priority heap.
627    ///The optional second parameter is the initial distance of the node.
628    ///
629    ///The function checks if the node has already been added to the heap and
630    ///it is pushed to the heap only if either it was not in the heap
631    ///or the shortest path found till then is shorter than \c dst.
632    void addSource(Node s,Value dst=OperationTraits::zero())
633    {
634      if(_heap->state(s) != Heap::IN_HEAP) {
635        _heap->push(s,dst);
636      } else if(OperationTraits::less((*_heap)[s], dst)) {
637        _heap->set(s,dst);
638        _pred->set(s,INVALID);
639      }
640    }
641
642    ///Processes the next node in the priority heap
643
644    ///Processes the next node in the priority heap.
645    ///
646    ///\return The processed node.
647    ///
648    ///\warning The priority heap must not be empty.
649    Node processNextNode()
650    {
651      Node v=_heap->top();
652      Value oldvalue=_heap->prio();
653      _heap->pop();
654      finalizeNodeData(v,oldvalue);
655
656      for(OutArcIt e(*G,v); e!=INVALID; ++e) {
657        Node w=G->target(e);
658        switch(_heap->state(w)) {
659        case Heap::PRE_HEAP:
660          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
661          _pred->set(w,e);
662          break;
663        case Heap::IN_HEAP:
664          {
665            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
666            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
667              _heap->decrease(w, newvalue);
668              _pred->set(w,e);
669            }
670          }
671          break;
672        case Heap::POST_HEAP:
673          break;
674        }
675      }
676      return v;
677    }
678
679    ///The next node to be processed.
680
681    ///Returns the next node to be processed or \c INVALID if the
682    ///priority heap is empty.
683    Node nextNode() const
684    {
685      return !_heap->empty()?_heap->top():INVALID;
686    }
687
688    ///\brief Returns \c false if there are nodes
689    ///to be processed.
690    ///
691    ///Returns \c false if there are nodes
692    ///to be processed in the priority heap.
693    bool emptyQueue() const { return _heap->empty(); }
694
695    ///Returns the number of the nodes to be processed in the priority heap
696
697    ///Returns the number of the nodes to be processed in the priority heap.
698    ///
699    int queueSize() const { return _heap->size(); }
700
701    ///Executes the algorithm.
702
703    ///Executes the algorithm.
704    ///
705    ///This method runs the %Dijkstra algorithm from the root node(s)
706    ///in order to compute the shortest path to each node.
707    ///
708    ///The algorithm computes
709    ///- the shortest path tree (forest),
710    ///- the distance of each node from the root(s).
711    ///
712    ///\pre init() must be called and at least one root node should be
713    ///added with addSource() before using this function.
714    ///
715    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
716    ///\code
717    ///  while ( !d.emptyQueue() ) {
718    ///    d.processNextNode();
719    ///  }
720    ///\endcode
721    void start()
722    {
723      while ( !emptyQueue() ) processNextNode();
724    }
725
726    ///Executes the algorithm until the given target node is reached.
727
728    ///Executes the algorithm until the given target node is reached.
729    ///
730    ///This method runs the %Dijkstra algorithm from the root node(s)
731    ///in order to compute the shortest path to \c dest.
732    ///
733    ///The algorithm computes
734    ///- the shortest path to \c dest,
735    ///- the distance of \c dest from the root(s).
736    ///
737    ///\pre init() must be called and at least one root node should be
738    ///added with addSource() before using this function.
739    void start(Node dest)
740    {
741      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
742      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
743    }
744
745    ///Executes the algorithm until a condition is met.
746
747    ///Executes the algorithm until a condition is met.
748    ///
749    ///This method runs the %Dijkstra algorithm from the root node(s) in
750    ///order to compute the shortest path to a node \c v with
751    /// <tt>nm[v]</tt> true, if such a node can be found.
752    ///
753    ///\param nm A \c bool (or convertible) node map. The algorithm
754    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
755    ///
756    ///\return The reached node \c v with <tt>nm[v]</tt> true or
757    ///\c INVALID if no such node was found.
758    ///
759    ///\pre init() must be called and at least one root node should be
760    ///added with addSource() before using this function.
761    template<class NodeBoolMap>
762    Node start(const NodeBoolMap &nm)
763    {
764      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
765      if ( _heap->empty() ) return INVALID;
766      finalizeNodeData(_heap->top(),_heap->prio());
767      return _heap->top();
768    }
769
770    ///Runs the algorithm from the given node.
771
772    ///This method runs the %Dijkstra algorithm from node \c s
773    ///in order to compute the shortest path to each node.
774    ///
775    ///The algorithm computes
776    ///- the shortest path tree,
777    ///- the distance of each node from the root.
778    ///
779    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
780    ///\code
781    ///  d.init();
782    ///  d.addSource(s);
783    ///  d.start();
784    ///\endcode
785    void run(Node s) {
786      init();
787      addSource(s);
788      start();
789    }
790
791    ///Finds the shortest path between \c s and \c t.
792
793    ///This method runs the %Dijkstra algorithm from node \c s
794    ///in order to compute the shortest path to \c t.
795    ///
796    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
797    ///if \c t is reachable form \c s, \c 0 otherwise.
798    ///
799    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
800    ///shortcut of the following code.
801    ///\code
802    ///  d.init();
803    ///  d.addSource(s);
804    ///  d.start(t);
805    ///\endcode
806    Value run(Node s,Node t) {
807      init();
808      addSource(s);
809      start(t);
810      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
811    }
812
813    ///@}
814
815    ///\name Query Functions
816    ///The result of the %Dijkstra algorithm can be obtained using these
817    ///functions.\n
818    ///Either \ref lemon::Dijkstra::run() "run()" or
819    ///\ref lemon::Dijkstra::start() "start()" must be called before
820    ///using them.
821
822    ///@{
823
824    ///The shortest path to a node.
825
826    ///Returns the shortest path to a node.
827    ///
828    ///\warning \c t should be reachable from the root(s).
829    ///
830    ///\pre Either \ref run() or \ref start() must be called before
831    ///using this function.
832    Path path(Node t) const { return Path(*G, *_pred, t); }
833
834    ///The distance of a node from the root(s).
835
836    ///Returns the distance of a node from the root(s).
837    ///
838    ///\warning If node \c v is not reachable from the root(s), then
839    ///the return value of this function is undefined.
840    ///
841    ///\pre Either \ref run() or \ref start() must be called before
842    ///using this function.
843    Value dist(Node v) const { return (*_dist)[v]; }
844
845    ///Returns the 'previous arc' of the shortest path tree for a node.
846
847    ///This function returns the 'previous arc' of the shortest path
848    ///tree for the node \c v, i.e. it returns the last arc of a
849    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
850    ///is not reachable from the root(s) or if \c v is a root.
851    ///
852    ///The shortest path tree used here is equal to the shortest path
853    ///tree used in \ref predNode().
854    ///
855    ///\pre Either \ref run() or \ref start() must be called before
856    ///using this function.
857    Arc predArc(Node v) const { return (*_pred)[v]; }
858
859    ///Returns the 'previous node' of the shortest path tree for a node.
860
861    ///This function returns the 'previous node' of the shortest path
862    ///tree for the node \c v, i.e. it returns the last but one node
863    ///from a shortest path from the root(s) to \c v. It is \c INVALID
864    ///if \c v is not reachable from the root(s) or if \c v is a root.
865    ///
866    ///The shortest path tree used here is equal to the shortest path
867    ///tree used in \ref predArc().
868    ///
869    ///\pre Either \ref run() or \ref start() must be called before
870    ///using this function.
871    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
872                                  G->source((*_pred)[v]); }
873
874    ///\brief Returns a const reference to the node map that stores the
875    ///distances of the nodes.
876    ///
877    ///Returns a const reference to the node map that stores the distances
878    ///of the nodes calculated by the algorithm.
879    ///
880    ///\pre Either \ref run() or \ref init()
881    ///must be called before using this function.
882    const DistMap &distMap() const { return *_dist;}
883
884    ///\brief Returns a const reference to the node map that stores the
885    ///predecessor arcs.
886    ///
887    ///Returns a const reference to the node map that stores the predecessor
888    ///arcs, which form the shortest path tree.
889    ///
890    ///\pre Either \ref run() or \ref init()
891    ///must be called before using this function.
892    const PredMap &predMap() const { return *_pred;}
893
894    ///Checks if a node is reachable from the root(s).
895
896    ///Returns \c true if \c v is reachable from the root(s).
897    ///\pre Either \ref run() or \ref start()
898    ///must be called before using this function.
899    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
900                                        Heap::PRE_HEAP; }
901
902    ///Checks if a node is processed.
903
904    ///Returns \c true if \c v is processed, i.e. the shortest
905    ///path to \c v has already found.
906    ///\pre Either \ref run() or \ref start()
907    ///must be called before using this function.
908    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
909                                          Heap::POST_HEAP; }
910
911    ///The current distance of a node from the root(s).
912
913    ///Returns the current distance of a node from the root(s).
914    ///It may be decreased in the following processes.
915    ///\pre \c v should be reached but not processed.
916    Value currentDist(Node v) const { return (*_heap)[v]; }
917
918    ///@}
919  };
920
921
922  ///Default traits class of dijkstra() function.
923
924  ///Default traits class of dijkstra() function.
925  ///\tparam GR The type of the digraph.
926  ///\tparam LM The type of the length map.
927  template<class GR, class LM>
928  struct DijkstraWizardDefaultTraits
929  {
930    ///The type of the digraph the algorithm runs on.
931    typedef GR Digraph;
932    ///The type of the map that stores the arc lengths.
933
934    ///The type of the map that stores the arc lengths.
935    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
936    typedef LM LengthMap;
937    ///The type of the length of the arcs.
938    typedef typename LM::Value Value;
939
940    /// Operation traits for Dijkstra algorithm.
941
942    /// This class defines the operations that are used in the algorithm.
943    /// \see DijkstraDefaultOperationTraits
944    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
945
946    /// The cross reference type used by the heap.
947
948    /// The cross reference type used by the heap.
949    /// Usually it is \c Digraph::NodeMap<int>.
950    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
951    ///Instantiates a \ref HeapCrossRef.
952
953    ///This function instantiates a \ref HeapCrossRef.
954    /// \param g is the digraph, to which we would like to define the
955    /// HeapCrossRef.
956    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
957    {
958      return new HeapCrossRef(g);
959    }
960
961    ///The heap type used by the Dijkstra algorithm.
962
963    ///The heap type used by the Dijkstra algorithm.
964    ///
965    ///\sa BinHeap
966    ///\sa Dijkstra
967    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
968                    std::less<Value> > Heap;
969
970    ///Instantiates a \ref Heap.
971
972    ///This function instantiates a \ref Heap.
973    /// \param r is the HeapCrossRef which is used.
974    static Heap *createHeap(HeapCrossRef& r)
975    {
976      return new Heap(r);
977    }
978
979    ///\brief The type of the map that stores the predecessor
980    ///arcs of the shortest paths.
981    ///
982    ///The type of the map that stores the predecessor
983    ///arcs of the shortest paths.
984    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
985    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
986    ///Instantiates a \ref PredMap.
987
988    ///This function instantiates a \ref PredMap.
989    ///\param g is the digraph, to which we would like to define the
990    ///\ref PredMap.
991#ifdef DOXYGEN
992    static PredMap *createPredMap(const Digraph &g)
993#else
994    static PredMap *createPredMap(const Digraph &)
995#endif
996    {
997      return new PredMap();
998    }
999
1000    ///The type of the map that indicates which nodes are processed.
1001
1002    ///The type of the map that indicates which nodes are processed.
1003    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1004    ///By default it is a NullMap.
1005    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1006    ///Instantiates a \ref ProcessedMap.
1007
1008    ///This function instantiates a \ref ProcessedMap.
1009    ///\param g is the digraph, to which
1010    ///we would like to define the \ref ProcessedMap.
1011#ifdef DOXYGEN
1012    static ProcessedMap *createProcessedMap(const Digraph &g)
1013#else
1014    static ProcessedMap *createProcessedMap(const Digraph &)
1015#endif
1016    {
1017      return new ProcessedMap();
1018    }
1019
1020    ///The type of the map that stores the distances of the nodes.
1021
1022    ///The type of the map that stores the distances of the nodes.
1023    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1024    typedef NullMap<typename Digraph::Node,Value> DistMap;
1025    ///Instantiates a \ref DistMap.
1026
1027    ///This function instantiates a \ref DistMap.
1028    ///\param g is the digraph, to which we would like to define
1029    ///the \ref DistMap
1030#ifdef DOXYGEN
1031    static DistMap *createDistMap(const Digraph &g)
1032#else
1033    static DistMap *createDistMap(const Digraph &)
1034#endif
1035    {
1036      return new DistMap();
1037    }
1038  };
1039
1040  /// Default traits class used by \ref DijkstraWizard
1041
1042  /// To make it easier to use Dijkstra algorithm
1043  /// we have created a wizard class.
1044  /// This \ref DijkstraWizard class needs default traits,
1045  /// as well as the \ref Dijkstra class.
1046  /// The \ref DijkstraWizardBase is a class to be the default traits of the
1047  /// \ref DijkstraWizard class.
1048  template<class GR,class LM>
1049  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1050  {
1051    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1052  protected:
1053    //The type of the nodes in the digraph.
1054    typedef typename Base::Digraph::Node Node;
1055
1056    //Pointer to the digraph the algorithm runs on.
1057    void *_g;
1058    //Pointer to the length map
1059    void *_length;
1060    //Pointer to the map of processed nodes.
1061    void *_processed;
1062    //Pointer to the map of predecessors arcs.
1063    void *_pred;
1064    //Pointer to the map of distances.
1065    void *_dist;
1066    //Pointer to the source node.
1067    Node _source;
1068
1069  public:
1070    /// Constructor.
1071
1072    /// This constructor does not require parameters, therefore it initiates
1073    /// all of the attributes to default values (0, INVALID).
1074    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
1075                           _dist(0), _source(INVALID) {}
1076
1077    /// Constructor.
1078
1079    /// This constructor requires some parameters,
1080    /// listed in the parameters list.
1081    /// Others are initiated to 0.
1082    /// \param g The digraph the algorithm runs on.
1083    /// \param l The length map.
1084    /// \param s The source node.
1085    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1086      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1087      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1088      _processed(0), _pred(0), _dist(0), _source(s) {}
1089
1090  };
1091
1092  /// Auxiliary class for the function type interface of Dijkstra algorithm.
1093
1094  /// This auxiliary class is created to implement the function type
1095  /// interface of \ref Dijkstra algorithm. It uses the functions and features
1096  /// of the plain \ref Dijkstra, but it is much simpler to use it.
1097  /// It should only be used through the \ref dijkstra() function, which makes
1098  /// it easier to use the algorithm.
1099  ///
1100  /// Simplicity means that the way to change the types defined
1101  /// in the traits class is based on functions that returns the new class
1102  /// and not on templatable built-in classes.
1103  /// When using the plain \ref Dijkstra
1104  /// the new class with the modified type comes from
1105  /// the original class by using the ::
1106  /// operator. In the case of \ref DijkstraWizard only
1107  /// a function have to be called, and it will
1108  /// return the needed class.
1109  ///
1110  /// It does not have own \ref run() method. When its \ref run() method
1111  /// is called, it initiates a plain \ref Dijkstra object, and calls the
1112  /// \ref Dijkstra::run() method of it.
1113  template<class TR>
1114  class DijkstraWizard : public TR
1115  {
1116    typedef TR Base;
1117
1118    ///The type of the digraph the algorithm runs on.
1119    typedef typename TR::Digraph Digraph;
1120
1121    typedef typename Digraph::Node Node;
1122    typedef typename Digraph::NodeIt NodeIt;
1123    typedef typename Digraph::Arc Arc;
1124    typedef typename Digraph::OutArcIt OutArcIt;
1125
1126    ///The type of the map that stores the arc lengths.
1127    typedef typename TR::LengthMap LengthMap;
1128    ///The type of the length of the arcs.
1129    typedef typename LengthMap::Value Value;
1130    ///\brief The type of the map that stores the predecessor
1131    ///arcs of the shortest paths.
1132    typedef typename TR::PredMap PredMap;
1133    ///The type of the map that stores the distances of the nodes.
1134    typedef typename TR::DistMap DistMap;
1135    ///The type of the map that indicates which nodes are processed.
1136    typedef typename TR::ProcessedMap ProcessedMap;
1137    ///The heap type used by the dijkstra algorithm.
1138    typedef typename TR::Heap Heap;
1139
1140  public:
1141
1142    /// Constructor.
1143    DijkstraWizard() : TR() {}
1144
1145    /// Constructor that requires parameters.
1146
1147    /// Constructor that requires parameters.
1148    /// These parameters will be the default values for the traits class.
1149    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
1150      TR(g,l,s) {}
1151
1152    ///Copy constructor
1153    DijkstraWizard(const TR &b) : TR(b) {}
1154
1155    ~DijkstraWizard() {}
1156
1157    ///Runs Dijkstra algorithm from a source node.
1158
1159    ///Runs Dijkstra algorithm from a source node.
1160    ///The node can be given with the \ref source() function.
1161    void run()
1162    {
1163      if(Base::_source==INVALID) throw UninitializedParameter();
1164      Dijkstra<Digraph,LengthMap,TR>
1165        dij(*reinterpret_cast<const Digraph*>(Base::_g),
1166            *reinterpret_cast<const LengthMap*>(Base::_length));
1167      if(Base::_processed)
1168        dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1169      if(Base::_pred)
1170        dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1171      if(Base::_dist)
1172        dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1173      dij.run(Base::_source);
1174    }
1175
1176    ///Runs Dijkstra algorithm from the given node.
1177
1178    ///Runs Dijkstra algorithm from the given node.
1179    ///\param s is the given source.
1180    void run(Node s)
1181    {
1182      Base::_source=s;
1183      run();
1184    }
1185
1186    /// Sets the source node, from which the Dijkstra algorithm runs.
1187
1188    /// Sets the source node, from which the Dijkstra algorithm runs.
1189    /// \param s is the source node.
1190    DijkstraWizard<TR> &source(Node s)
1191    {
1192      Base::_source=s;
1193      return *this;
1194    }
1195
1196    template<class T>
1197    struct SetPredMapBase : public Base {
1198      typedef T PredMap;
1199      static PredMap *createPredMap(const Digraph &) { return 0; };
1200      SetPredMapBase(const TR &b) : TR(b) {}
1201    };
1202    ///\brief \ref named-templ-param "Named parameter"
1203    ///for setting \ref PredMap object.
1204    ///
1205    ///\ref named-templ-param "Named parameter"
1206    ///for setting \ref PredMap object.
1207    template<class T>
1208    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1209    {
1210      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1211      return DijkstraWizard<SetPredMapBase<T> >(*this);
1212    }
1213
1214    template<class T>
1215    struct SetProcessedMapBase : public Base {
1216      typedef T ProcessedMap;
1217      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1218      SetProcessedMapBase(const TR &b) : TR(b) {}
1219    };
1220    ///\brief \ref named-templ-param "Named parameter"
1221    ///for setting \ref ProcessedMap object.
1222    ///
1223    /// \ref named-templ-param "Named parameter"
1224    ///for setting \ref ProcessedMap object.
1225    template<class T>
1226    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1227    {
1228      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1229      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
1230    }
1231
1232    template<class T>
1233    struct SetDistMapBase : public Base {
1234      typedef T DistMap;
1235      static DistMap *createDistMap(const Digraph &) { return 0; };
1236      SetDistMapBase(const TR &b) : TR(b) {}
1237    };
1238    ///\brief \ref named-templ-param "Named parameter"
1239    ///for setting \ref DistMap object.
1240    ///
1241    ///\ref named-templ-param "Named parameter"
1242    ///for setting \ref DistMap object.
1243    template<class T>
1244    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1245    {
1246      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1247      return DijkstraWizard<SetDistMapBase<T> >(*this);
1248    }
1249
1250  };
1251
1252  ///Function type interface for Dijkstra algorithm.
1253
1254  /// \ingroup shortest_path
1255  ///Function type interface for Dijkstra algorithm.
1256  ///
1257  ///This function also has several
1258  ///\ref named-templ-func-param "named parameters",
1259  ///they are declared as the members of class \ref DijkstraWizard.
1260  ///The following
1261  ///example shows how to use these parameters.
1262  ///\code
1263  ///  dijkstra(g,length,source).predMap(preds).run();
1264  ///\endcode
1265  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1266  ///to the end of the parameter list.
1267  ///\sa DijkstraWizard
1268  ///\sa Dijkstra
1269  template<class GR, class LM>
1270  DijkstraWizard<DijkstraWizardBase<GR,LM> >
1271  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1272  {
1273    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1274  }
1275
1276} //END OF NAMESPACE LEMON
1277
1278#endif
Note: See TracBrowser for help on using the repository browser.