COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 421:6b9057cdcd8b

Last change on this file since 421:6b9057cdcd8b was 421:6b9057cdcd8b, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Doc improvements for Bfs, Dfs, Dijkstra (#185)

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