COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 287:bb40b6db0a58

Last change on this file since 287:bb40b6db0a58 was 287:bb40b6db0a58, checked in by Alpar Juttner <alpar@…>, 15 years ago

Merge

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