COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 281:e9b4fbe163f5

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

Merge

File size: 42.9 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 reached.
728
729    ///Executes the algorithm until the given target node is reached.
730    ///
731    ///This method runs the %Dijkstra algorithm from the root node(s)
732    ///in order to compute the shortest path to \c dest.
733    ///
734    ///The algorithm computes
735    ///- the shortest path to \c dest,
736    ///- the distance of \c dest 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 dest)
741    {
742      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
743      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
744    }
745
746    ///Executes the algorithm until a condition is met.
747
748    ///Executes the algorithm until a condition is met.
749    ///
750    ///This method runs the %Dijkstra algorithm from the root node(s) in
751    ///order to compute the shortest path to a node \c v with
752    /// <tt>nm[v]</tt> true, if such a node can be found.
753    ///
754    ///\param nm A \c bool (or convertible) node map. The algorithm
755    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
756    ///
757    ///\return The reached node \c v with <tt>nm[v]</tt> true or
758    ///\c INVALID if no such node was found.
759    ///
760    ///\pre init() must be called and at least one root node should be
761    ///added with addSource() before using this function.
762    template<class NodeBoolMap>
763    Node start(const NodeBoolMap &nm)
764    {
765      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
766      if ( _heap->empty() ) return INVALID;
767      finalizeNodeData(_heap->top(),_heap->prio());
768      return _heap->top();
769    }
770
771    ///Runs the algorithm from the given node.
772
773    ///This method runs the %Dijkstra algorithm from node \c s
774    ///in order to compute the shortest path to each node.
775    ///
776    ///The algorithm computes
777    ///- the shortest path tree,
778    ///- the distance of each node from the root.
779    ///
780    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
781    ///\code
782    ///  d.init();
783    ///  d.addSource(s);
784    ///  d.start();
785    ///\endcode
786    void run(Node s) {
787      init();
788      addSource(s);
789      start();
790    }
791
792    ///Finds the shortest path between \c s and \c t.
793
794    ///This method runs the %Dijkstra algorithm from node \c s
795    ///in order to compute the shortest path to \c t.
796    ///
797    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
798    ///if \c t is reachable form \c s, \c 0 otherwise.
799    ///
800    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
801    ///shortcut of the following code.
802    ///\code
803    ///  d.init();
804    ///  d.addSource(s);
805    ///  d.start(t);
806    ///\endcode
807    Value run(Node s,Node t) {
808      init();
809      addSource(s);
810      start(t);
811      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
812    }
813
814    ///@}
815
816    ///\name Query Functions
817    ///The result of the %Dijkstra algorithm can be obtained using these
818    ///functions.\n
819    ///Either \ref lemon::Dijkstra::run() "run()" or
820    ///\ref lemon::Dijkstra::start() "start()" must be called before
821    ///using them.
822
823    ///@{
824
825    ///The shortest path to a node.
826
827    ///Returns the shortest path to a node.
828    ///
829    ///\warning \c t should be reachable from the root(s).
830    ///
831    ///\pre Either \ref run() or \ref start() must be called before
832    ///using this function.
833    Path path(Node t) const { return Path(*G, *_pred, t); }
834
835    ///The distance of a node from the root(s).
836
837    ///Returns the distance of a node from the root(s).
838    ///
839    ///\warning If node \c v is not reachable from the root(s), then
840    ///the return value of this function is undefined.
841    ///
842    ///\pre Either \ref run() or \ref start() must be called before
843    ///using this function.
844    Value dist(Node v) const { return (*_dist)[v]; }
845
846    ///Returns the 'previous arc' of the shortest path tree for a node.
847
848    ///This function returns the 'previous arc' of the shortest path
849    ///tree for the node \c v, i.e. it returns the last arc of a
850    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
851    ///is not reachable from the root(s) or if \c v is a root.
852    ///
853    ///The shortest path tree used here is equal to the shortest path
854    ///tree used in \ref predNode().
855    ///
856    ///\pre Either \ref run() or \ref start() must be called before
857    ///using this function.
858    Arc predArc(Node v) const { return (*_pred)[v]; }
859
860    ///Returns the 'previous node' of the shortest path tree for a node.
861
862    ///This function returns the 'previous node' of the shortest path
863    ///tree for the node \c v, i.e. it returns the last but one node
864    ///from a shortest path from the root(s) to \c v. It is \c INVALID
865    ///if \c v is not reachable from the root(s) or if \c v is a root.
866    ///
867    ///The shortest path tree used here is equal to the shortest path
868    ///tree used in \ref predArc().
869    ///
870    ///\pre Either \ref run() or \ref start() must be called before
871    ///using this function.
872    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
873                                  G->source((*_pred)[v]); }
874
875    ///\brief Returns a const reference to the node map that stores the
876    ///distances of the nodes.
877    ///
878    ///Returns a const reference to the node map that stores the distances
879    ///of the nodes calculated by the algorithm.
880    ///
881    ///\pre Either \ref run() or \ref init()
882    ///must be called before using this function.
883    const DistMap &distMap() const { return *_dist;}
884
885    ///\brief Returns a const reference to the node map that stores the
886    ///predecessor arcs.
887    ///
888    ///Returns a const reference to the node map that stores the predecessor
889    ///arcs, which form the shortest path tree.
890    ///
891    ///\pre Either \ref run() or \ref init()
892    ///must be called before using this function.
893    const PredMap &predMap() const { return *_pred;}
894
895    ///Checks if a node is reachable from the root(s).
896
897    ///Returns \c true if \c v is reachable from the root(s).
898    ///\pre Either \ref run() or \ref start()
899    ///must be called before using this function.
900    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
901                                        Heap::PRE_HEAP; }
902
903    ///Checks if a node is processed.
904
905    ///Returns \c true if \c v is processed, i.e. the shortest
906    ///path to \c v has already found.
907    ///\pre Either \ref run() or \ref start()
908    ///must be called before using this function.
909    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
910                                          Heap::POST_HEAP; }
911
912    ///The current distance of a node from the root(s).
913
914    ///Returns the current distance of a node from the root(s).
915    ///It may be decreased in the following processes.
916    ///\pre \c v should be reached but not processed.
917    Value currentDist(Node v) const { return (*_heap)[v]; }
918
919    ///@}
920  };
921
922
923  ///Default traits class of dijkstra() function.
924
925  ///Default traits class of dijkstra() function.
926  ///\tparam GR The type of the digraph.
927  ///\tparam LM The type of the length map.
928  template<class GR, class LM>
929  struct DijkstraWizardDefaultTraits
930  {
931    ///The type of the digraph the algorithm runs on.
932    typedef GR Digraph;
933    ///The type of the map that stores the arc lengths.
934
935    ///The type of the map that stores the arc lengths.
936    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
937    typedef LM LengthMap;
938    ///The type of the length of the arcs.
939    typedef typename LM::Value Value;
940
941    /// Operation traits for Dijkstra algorithm.
942
943    /// This class defines the operations that are used in the algorithm.
944    /// \see DijkstraDefaultOperationTraits
945    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
946
947    /// The cross reference type used by the heap.
948
949    /// The cross reference type used by the heap.
950    /// Usually it is \c Digraph::NodeMap<int>.
951    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
952    ///Instantiates a \ref HeapCrossRef.
953
954    ///This function instantiates a \ref HeapCrossRef.
955    /// \param g is the digraph, to which we would like to define the
956    /// HeapCrossRef.
957    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
958    {
959      return new HeapCrossRef(g);
960    }
961
962    ///The heap type used by the Dijkstra algorithm.
963
964    ///The heap type used by the Dijkstra algorithm.
965    ///
966    ///\sa BinHeap
967    ///\sa Dijkstra
968    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
969                    std::less<Value> > Heap;
970
971    ///Instantiates a \ref Heap.
972
973    ///This function instantiates a \ref Heap.
974    /// \param r is the HeapCrossRef which is used.
975    static Heap *createHeap(HeapCrossRef& r)
976    {
977      return new Heap(r);
978    }
979
980    ///\brief The type of the map that stores the predecessor
981    ///arcs of the shortest paths.
982    ///
983    ///The type of the map that stores the predecessor
984    ///arcs of the shortest paths.
985    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
986    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
987    ///Instantiates a \ref PredMap.
988
989    ///This function instantiates a \ref PredMap.
990    ///\param g is the digraph, to which we would like to define the
991    ///\ref PredMap.
992    static PredMap *createPredMap(const Digraph &g)
993    {
994      return new PredMap(g);
995    }
996
997    ///The type of the map that indicates which nodes are processed.
998
999    ///The type of the map that indicates which nodes are processed.
1000    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1001    ///By default it is a NullMap.
1002    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1003    ///Instantiates a \ref ProcessedMap.
1004
1005    ///This function instantiates a \ref ProcessedMap.
1006    ///\param g is the digraph, to which
1007    ///we would like to define the \ref ProcessedMap.
1008#ifdef DOXYGEN
1009    static ProcessedMap *createProcessedMap(const Digraph &g)
1010#else
1011    static ProcessedMap *createProcessedMap(const Digraph &)
1012#endif
1013    {
1014      return new ProcessedMap();
1015    }
1016
1017    ///The type of the map that stores the distances of the nodes.
1018
1019    ///The type of the map that stores the distances of the nodes.
1020    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1021    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1022    ///Instantiates a \ref DistMap.
1023
1024    ///This function instantiates a \ref DistMap.
1025    ///\param g is the digraph, to which we would like to define
1026    ///the \ref DistMap
1027    static DistMap *createDistMap(const Digraph &g)
1028    {
1029      return new DistMap(g);
1030    }
1031
1032    ///The type of the shortest paths.
1033
1034    ///The type of the shortest paths.
1035    ///It must meet the \ref concepts::Path "Path" concept.
1036    typedef lemon::Path<Digraph> Path;
1037  };
1038
1039  /// Default traits class used by \ref DijkstraWizard
1040
1041  /// To make it easier to use Dijkstra algorithm
1042  /// we have created a wizard class.
1043  /// This \ref DijkstraWizard class needs default traits,
1044  /// as well as the \ref Dijkstra class.
1045  /// The \ref DijkstraWizardBase is a class to be the default traits of the
1046  /// \ref DijkstraWizard class.
1047  template<class GR,class LM>
1048  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1049  {
1050    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1051  protected:
1052    //The type of the nodes in the digraph.
1053    typedef typename Base::Digraph::Node Node;
1054
1055    //Pointer to the digraph the algorithm runs on.
1056    void *_g;
1057    //Pointer to the length map.
1058    void *_length;
1059    //Pointer to the map of processed nodes.
1060    void *_processed;
1061    //Pointer to the map of predecessors arcs.
1062    void *_pred;
1063    //Pointer to the map of distances.
1064    void *_dist;
1065    //Pointer to the shortest path to the target node.
1066    void *_path;
1067    //Pointer to the distance of the target node.
1068    void *_di;
1069
1070  public:
1071    /// Constructor.
1072
1073    /// This constructor does not require parameters, therefore it initiates
1074    /// all of the attributes to \c 0.
1075    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
1076                           _dist(0), _path(0), _di(0) {}
1077
1078    /// Constructor.
1079
1080    /// This constructor requires two parameters,
1081    /// others are initiated to \c 0.
1082    /// \param g The digraph the algorithm runs on.
1083    /// \param l The length map.
1084    DijkstraWizardBase(const GR &g,const LM &l) :
1085      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1086      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1087      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1088
1089  };
1090
1091  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
1092
1093  /// This auxiliary class is created to implement the
1094  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1095  /// It does not have own \ref run() method, it uses the functions
1096  /// and features of the plain \ref Dijkstra.
1097  ///
1098  /// This class should only be used through the \ref dijkstra() function,
1099  /// which makes it easier to use the algorithm.
1100  template<class TR>
1101  class DijkstraWizard : public TR
1102  {
1103    typedef TR Base;
1104
1105    ///The type of the digraph the algorithm runs on.
1106    typedef typename TR::Digraph Digraph;
1107
1108    typedef typename Digraph::Node Node;
1109    typedef typename Digraph::NodeIt NodeIt;
1110    typedef typename Digraph::Arc Arc;
1111    typedef typename Digraph::OutArcIt OutArcIt;
1112
1113    ///The type of the map that stores the arc lengths.
1114    typedef typename TR::LengthMap LengthMap;
1115    ///The type of the length of the arcs.
1116    typedef typename LengthMap::Value Value;
1117    ///\brief The type of the map that stores the predecessor
1118    ///arcs of the shortest paths.
1119    typedef typename TR::PredMap PredMap;
1120    ///The type of the map that stores the distances of the nodes.
1121    typedef typename TR::DistMap DistMap;
1122    ///The type of the map that indicates which nodes are processed.
1123    typedef typename TR::ProcessedMap ProcessedMap;
1124    ///The type of the shortest paths
1125    typedef typename TR::Path Path;
1126    ///The heap type used by the dijkstra algorithm.
1127    typedef typename TR::Heap Heap;
1128
1129  public:
1130
1131    /// Constructor.
1132    DijkstraWizard() : TR() {}
1133
1134    /// Constructor that requires parameters.
1135
1136    /// Constructor that requires parameters.
1137    /// These parameters will be the default values for the traits class.
1138    /// \param g The digraph the algorithm runs on.
1139    /// \param l The length map.
1140    DijkstraWizard(const Digraph &g, const LengthMap &l) :
1141      TR(g,l) {}
1142
1143    ///Copy constructor
1144    DijkstraWizard(const TR &b) : TR(b) {}
1145
1146    ~DijkstraWizard() {}
1147
1148    ///Runs Dijkstra algorithm from the given source node.
1149
1150    ///This method runs %Dijkstra algorithm from the given source node
1151    ///in order to compute the shortest path to each node.
1152    void run(Node s)
1153    {
1154      if (s==INVALID) throw UninitializedParameter();
1155      Dijkstra<Digraph,LengthMap,TR>
1156        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1157             *reinterpret_cast<const LengthMap*>(Base::_length));
1158      if (Base::_pred)
1159        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1160      if (Base::_dist)
1161        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1162      if (Base::_processed)
1163        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1164      dijk.run(s);
1165    }
1166
1167    ///Finds the shortest path between \c s and \c t.
1168
1169    ///This method runs the %Dijkstra algorithm from node \c s
1170    ///in order to compute the shortest path to node \c t
1171    ///(it stops searching when \c t is processed).
1172    ///
1173    ///\return \c true if \c t is reachable form \c s.
1174    bool run(Node s, Node t)
1175    {
1176      if (s==INVALID || t==INVALID) throw UninitializedParameter();
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.