COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 525:9605e051942f

Last change on this file since 525:9605e051942f was 525:9605e051942f, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Various doc improvements

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