COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 295:7c796c1cf1b0

Last change on this file since 295:7c796c1cf1b0 was 290:f6899946c1ac, checked in by Balazs Dezso <deba@…>, 16 years ago

Simplifying exceptions

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