COIN-OR::LEMON - Graph Library

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

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

Merge

File size: 42.9 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[100]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[100]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
[184]26#include <limits>
[169]27#include <lemon/list_graph.h>
[100]28#include <lemon/bin_heap.h>
29#include <lemon/bits/path_dump.h>
[220]30#include <lemon/core.h>
[100]31#include <lemon/error.h>
32#include <lemon/maps.h>
[278]33#include <lemon/path.h>
[100]34
35namespace lemon {
36
[244]37  /// \brief Default operation traits for the Dijkstra algorithm class.
[209]38  ///
[244]39  /// This operation traits class defines all computational operations and
40  /// constants which are used in the Dijkstra algorithm.
[100]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    }
[244]51    /// \brief Gives back true only if the first value is less than the second.
[100]52    static bool less(const Value& left, const Value& right) {
53      return left < right;
54    }
55  };
56
[244]57  /// \brief Widest path operation traits for the Dijkstra algorithm class.
[209]58  ///
[244]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
[100]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    }
[244]74    /// \brief Gives back true only if the first value is less than the second.
[100]75    static bool less(const Value& left, const Value& right) {
76      return left < right;
77    }
78  };
[209]79
[100]80  ///Default traits class of Dijkstra class.
81
82  ///Default traits class of Dijkstra class.
[244]83  ///\tparam GR The type of the digraph.
84  ///\tparam LM The type of the length map.
[100]85  template<class GR, class LM>
86  struct DijkstraDefaultTraits
87  {
[244]88    ///The type of the digraph the algorithm runs on.
[100]89    typedef GR Digraph;
[244]90
[100]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;
[244]96    ///The type of the length of the arcs.
[100]97    typedef typename LM::Value Value;
[244]98
[100]99    /// Operation traits for Dijkstra algorithm.
100
[244]101    /// This class defines the operations that are used in the algorithm.
[100]102    /// \see DijkstraDefaultOperationTraits
103    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
104
[244]105    /// The cross reference type used by the heap.
[100]106
[244]107    /// The cross reference type used by the heap.
[100]108    /// Usually it is \c Digraph::NodeMap<int>.
109    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
[244]110    ///Instantiates a \ref HeapCrossRef.
[100]111
[244]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)
[100]116    {
[244]117      return new HeapCrossRef(g);
[100]118    }
[209]119
[244]120    ///The heap type used by the Dijkstra algorithm.
[100]121
[244]122    ///The heap type used by the Dijkstra algorithm.
[100]123    ///
124    ///\sa BinHeap
125    ///\sa Dijkstra
126    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
[244]127    ///Instantiates a \ref Heap.
[100]128
[244]129    ///This function instantiates a \ref Heap.
130    static Heap *createHeap(HeapCrossRef& r)
[100]131    {
[244]132      return new Heap(r);
[100]133    }
134
[244]135    ///\brief The type of the map that stores the predecessor
[100]136    ///arcs of the shortest paths.
[209]137    ///
[244]138    ///The type of the map that stores the predecessor
[100]139    ///arcs of the shortest paths.
140    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[244]141    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
142    ///Instantiates a \ref PredMap.
[209]143
[244]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)
[100]148    {
[244]149      return new PredMap(g);
[100]150    }
151
[244]152    ///The type of the map that indicates which nodes are processed.
[209]153
[244]154    ///The type of the map that indicates which nodes are processed.
[100]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;
[244]158    ///Instantiates a \ref ProcessedMap.
[209]159
[244]160    ///This function instantiates a \ref ProcessedMap.
[100]161    ///\param g is the digraph, to which
[244]162    ///we would like to define the \ref ProcessedMap
[100]163#ifdef DOXYGEN
[244]164    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]165#else
[244]166    static ProcessedMap *createProcessedMap(const Digraph &)
[100]167#endif
168    {
169      return new ProcessedMap();
170    }
[209]171
[244]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.
[100]175    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
176    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
[244]177    ///Instantiates a \ref DistMap.
[209]178
179    ///This function instantiates a \ref DistMap.
[244]180    ///\param g is the digraph, to which we would like to define
[210]181    ///the \ref DistMap
[244]182    static DistMap *createDistMap(const Digraph &g)
[100]183    {
[244]184      return new DistMap(g);
[100]185    }
186  };
[209]187
[100]188  ///%Dijkstra algorithm class.
[209]189
[100]190  /// \ingroup shortest_path
[244]191  ///This class provides an efficient implementation of the %Dijkstra algorithm.
192  ///
[100]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  ///
[278]200  ///There is also a \ref dijkstra() "function-type interface" for the
[244]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
[100]209  ///arcs. It is read once for each arc, so the map may involve in
[244]210  ///relatively time consuming process to compute the arc lengths if
[100]211  ///it is necessary. The default map type is \ref
[244]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.
[100]219#ifdef DOXYGEN
220  template <typename GR, typename LM, typename TR>
221#else
222  template <typename GR=ListDigraph,
[209]223            typename LM=typename GR::template ArcMap<int>,
224            typename TR=DijkstraDefaultTraits<GR,LM> >
[100]225#endif
226  class Dijkstra {
227  public:
[244]228    ///\ref Exception for uninitialized parameters.
229
230    ///This error represents problems in the initialization of the
231    ///parameters of the algorithm.
[100]232    class UninitializedParameter : public lemon::UninitializedParameter {
233    public:
234      virtual const char* what() const throw() {
[209]235        return "lemon::Dijkstra::UninitializedParameter";
[100]236      }
237    };
238
[244]239    ///The type of the digraph the algorithm runs on.
[100]240    typedef typename TR::Digraph Digraph;
[209]241
[100]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;
[244]246    ///\brief The type of the map that stores the predecessor arcs of the
247    ///shortest paths.
[100]248    typedef typename TR::PredMap PredMap;
[244]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.
[100]252    typedef typename TR::ProcessedMap ProcessedMap;
[244]253    ///The type of the paths.
254    typedef PredMapPath<Digraph, PredMap> Path;
[100]255    ///The cross reference type used for the current heap.
256    typedef typename TR::HeapCrossRef HeapCrossRef;
[244]257    ///The heap type used by the algorithm.
[100]258    typedef typename TR::Heap Heap;
[244]259    ///The operation traits class.
[100]260    typedef typename TR::OperationTraits OperationTraits;
[244]261
262    ///The traits class.
263    typedef TR Traits;
264
[100]265  private:
[244]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.
[100]273    const Digraph *G;
[244]274    //Pointer to the length map.
[100]275    const LengthMap *length;
[244]276    //Pointer to the map of predecessors arcs.
[100]277    PredMap *_pred;
[244]278    //Indicates if _pred is locally allocated (true) or not.
[100]279    bool local_pred;
[244]280    //Pointer to the map of distances.
[100]281    DistMap *_dist;
[244]282    //Indicates if _dist is locally allocated (true) or not.
[100]283    bool local_dist;
[244]284    //Pointer to the map of processed status of the nodes.
[100]285    ProcessedMap *_processed;
[244]286    //Indicates if _processed is locally allocated (true) or not.
[100]287    bool local_processed;
[244]288    //Pointer to the heap cross references.
[100]289    HeapCrossRef *_heap_cross_ref;
[244]290    //Indicates if _heap_cross_ref is locally allocated (true) or not.
[100]291    bool local_heap_cross_ref;
[244]292    //Pointer to the heap.
[100]293    Heap *_heap;
[244]294    //Indicates if _heap is locally allocated (true) or not.
[100]295    bool local_heap;
296
[280]297    //Creates the maps if necessary.
[209]298    void create_maps()
[100]299    {
300      if(!_pred) {
[209]301        local_pred = true;
302        _pred = Traits::createPredMap(*G);
[100]303      }
304      if(!_dist) {
[209]305        local_dist = true;
306        _dist = Traits::createDistMap(*G);
[100]307      }
308      if(!_processed) {
[209]309        local_processed = true;
310        _processed = Traits::createProcessedMap(*G);
[100]311      }
312      if (!_heap_cross_ref) {
[209]313        local_heap_cross_ref = true;
314        _heap_cross_ref = Traits::createHeapCrossRef(*G);
[100]315      }
316      if (!_heap) {
[209]317        local_heap = true;
318        _heap = Traits::createHeap(*_heap_cross_ref);
[100]319      }
320    }
[209]321
[244]322  public:
[100]323
324    typedef Dijkstra Create;
[209]325
[100]326    ///\name Named template parameters
327
328    ///@{
329
330    template <class T>
[257]331    struct SetPredMapTraits : public Traits {
[100]332      typedef T PredMap;
333      static PredMap *createPredMap(const Digraph &)
334      {
[209]335        throw UninitializedParameter();
[100]336      }
337    };
[244]338    ///\brief \ref named-templ-param "Named parameter" for setting
339    ///\ref PredMap type.
[100]340    ///
[244]341    ///\ref named-templ-param "Named parameter" for setting
342    ///\ref PredMap type.
[100]343    template <class T>
[257]344    struct SetPredMap
345      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
346      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
[100]347    };
[209]348
[100]349    template <class T>
[257]350    struct SetDistMapTraits : public Traits {
[100]351      typedef T DistMap;
352      static DistMap *createDistMap(const Digraph &)
353      {
[209]354        throw UninitializedParameter();
[100]355      }
356    };
[244]357    ///\brief \ref named-templ-param "Named parameter" for setting
358    ///\ref DistMap type.
[100]359    ///
[244]360    ///\ref named-templ-param "Named parameter" for setting
361    ///\ref DistMap type.
[100]362    template <class T>
[257]363    struct SetDistMap
364      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
365      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
[100]366    };
[209]367
[100]368    template <class T>
[257]369    struct SetProcessedMapTraits : public Traits {
[100]370      typedef T ProcessedMap;
[244]371      static ProcessedMap *createProcessedMap(const Digraph &)
[100]372      {
[209]373        throw UninitializedParameter();
[100]374      }
375    };
[244]376    ///\brief \ref named-templ-param "Named parameter" for setting
377    ///\ref ProcessedMap type.
[100]378    ///
[244]379    ///\ref named-templ-param "Named parameter" for setting
380    ///\ref ProcessedMap type.
[100]381    template <class T>
[257]382    struct SetProcessedMap
383      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
384      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
[100]385    };
[209]386
[257]387    struct SetStandardProcessedMapTraits : public Traits {
[100]388      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
[244]389      static ProcessedMap *createProcessedMap(const Digraph &g)
[100]390      {
[244]391        return new ProcessedMap(g);
[100]392      }
393    };
[244]394    ///\brief \ref named-templ-param "Named parameter" for setting
395    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
[100]396    ///
[244]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.
[257]400    struct SetStandardProcessedMap
401      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
402      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
[210]403      Create;
[100]404    };
405
406    template <class H, class CR>
[257]407    struct SetHeapTraits : public Traits {
[100]408      typedef CR HeapCrossRef;
409      typedef H Heap;
410      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
[209]411        throw UninitializedParameter();
[100]412      }
[209]413      static Heap *createHeap(HeapCrossRef &)
[100]414      {
[209]415        throw UninitializedParameter();
[100]416      }
417    };
418    ///\brief \ref named-templ-param "Named parameter" for setting
419    ///heap and cross reference type
420    ///
[209]421    ///\ref named-templ-param "Named parameter" for setting heap and cross
[244]422    ///reference type.
[100]423    template <class H, class CR = typename Digraph::template NodeMap<int> >
[257]424    struct SetHeap
425      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
426      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
[100]427    };
428
429    template <class H, class CR>
[257]430    struct SetStandardHeapTraits : public Traits {
[100]431      typedef CR HeapCrossRef;
432      typedef H Heap;
433      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
[209]434        return new HeapCrossRef(G);
[100]435      }
[209]436      static Heap *createHeap(HeapCrossRef &R)
[100]437      {
[209]438        return new Heap(R);
[100]439      }
440    };
441    ///\brief \ref named-templ-param "Named parameter" for setting
442    ///heap and cross reference type with automatic allocation
443    ///
[209]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
[100]447    ///parameter and the heap's constructor waits for the cross reference.
448    template <class H, class CR = typename Digraph::template NodeMap<int> >
[257]449    struct SetStandardHeap
450      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
451      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
[100]452      Create;
453    };
454
455    template <class T>
[257]456    struct SetOperationTraitsTraits : public Traits {
[100]457      typedef T OperationTraits;
458    };
[209]459
460    /// \brief \ref named-templ-param "Named parameter" for setting
[244]461    ///\ref OperationTraits type
[100]462    ///
[244]463    ///\ref named-templ-param "Named parameter" for setting
464    ///\ref OperationTraits type.
[100]465    template <class T>
[257]466    struct SetOperationTraits
467      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
468      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
[100]469      Create;
470    };
[209]471
[100]472    ///@}
473
474  protected:
475
476    Dijkstra() {}
477
[209]478  public:
479
[100]480    ///Constructor.
[209]481
[244]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),
[100]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    { }
[209]493
[100]494    ///Destructor.
[209]495    ~Dijkstra()
[100]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>
[209]508    Dijkstra &lengthMap(const LengthMap &m)
[100]509    {
510      length = &m;
511      return *this;
512    }
513
[244]514    ///Sets the map that stores the predecessor arcs.
[100]515
[244]516    ///Sets the map that stores the predecessor arcs.
[100]517    ///If you don't use this function before calling \ref run(),
[244]518    ///it will allocate one. The destructor deallocates this
[100]519    ///automatically allocated map, of course.
520    ///\return <tt> (*this) </tt>
[209]521    Dijkstra &predMap(PredMap &m)
[100]522    {
523      if(local_pred) {
[209]524        delete _pred;
525        local_pred=false;
[100]526      }
527      _pred = &m;
528      return *this;
529    }
530
[244]531    ///Sets the map that indicates which nodes are processed.
[100]532
[244]533    ///Sets the map that indicates which nodes are processed.
[100]534    ///If you don't use this function before calling \ref run(),
[244]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
[100]554    ///automatically allocated map, of course.
555    ///\return <tt> (*this) </tt>
[209]556    Dijkstra &distMap(DistMap &m)
[100]557    {
558      if(local_dist) {
[209]559        delete _dist;
560        local_dist=false;
[100]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(),
[244]570    ///it will allocate one. The destructor deallocates this
[100]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) {
[209]576        delete _heap_cross_ref;
577        local_heap_cross_ref=false;
[100]578      }
579      _heap_cross_ref = &cr;
580      if(local_heap) {
[209]581        delete _heap;
582        local_heap=false;
[100]583      }
584      _heap = &hp;
585      return *this;
586    }
587
588  private:
[244]589
[100]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
[244]599    ///The simplest way to execute the algorithm is to use one of the
600    ///member functions called \ref lemon::Dijkstra::run() "run()".
[100]601    ///\n
[244]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.
[100]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 ) {
[209]619        _pred->set(u,INVALID);
620        _processed->set(u,false);
621        _heap_cross_ref->set(u,Heap::PRE_HEAP);
[100]622      }
623    }
[209]624
[100]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    ///
[244]630    ///The function checks if the node has already been added to the heap and
[100]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) {
[209]636        _heap->push(s,dst);
[100]637      } else if(OperationTraits::less((*_heap)[s], dst)) {
[209]638        _heap->set(s,dst);
639        _pred->set(s,INVALID);
[100]640      }
641    }
[209]642
[100]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    ///
[244]649    ///\warning The priority heap must not be empty.
[100]650    Node processNextNode()
651    {
[209]652      Node v=_heap->top();
[100]653      Value oldvalue=_heap->prio();
654      _heap->pop();
655      finalizeNodeData(v,oldvalue);
[209]656
[100]657      for(OutArcIt e(*G,v); e!=INVALID; ++e) {
[209]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        }
[100]676      }
677      return v;
678    }
679
[244]680    ///The next node to be processed.
[209]681
[244]682    ///Returns the next node to be processed or \c INVALID if the
683    ///priority heap is empty.
684    Node nextNode() const
[209]685    {
[100]686      return !_heap->empty()?_heap->top():INVALID;
687    }
[209]688
[100]689    ///\brief Returns \c false if there are nodes
[244]690    ///to be processed.
[100]691    ///
692    ///Returns \c false if there are nodes
[244]693    ///to be processed in the priority heap.
694    bool emptyQueue() const { return _heap->empty(); }
695
[100]696    ///Returns the number of the nodes to be processed in the priority heap
697
[244]698    ///Returns the number of the nodes to be processed in the priority heap.
[100]699    ///
[244]700    int queueSize() const { return _heap->size(); }
[209]701
[100]702    ///Executes the algorithm.
703
704    ///Executes the algorithm.
705    ///
[244]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.
[100]730    ///
731    ///This method runs the %Dijkstra algorithm from the root node(s)
[244]732    ///in order to compute the shortest path to \c dest.
[100]733    ///
[244]734    ///The algorithm computes
735    ///- the shortest path to \c dest,
736    ///- the distance of \c dest from the root(s).
[100]737    ///
[244]738    ///\pre init() must be called and at least one root node should be
739    ///added with addSource() before using this function.
[100]740    void start(Node dest)
741    {
742      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
743      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
744    }
[209]745
[100]746    ///Executes the algorithm until a condition is met.
747
748    ///Executes the algorithm until a condition is met.
749    ///
[244]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.
[100]753    ///
[244]754    ///\param nm A \c bool (or convertible) node map. The algorithm
[100]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.
[244]759    ///
760    ///\pre init() must be called and at least one root node should be
761    ///added with addSource() before using this function.
[100]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    }
[209]770
[244]771    ///Runs the algorithm from the given node.
[209]772
[244]773    ///This method runs the %Dijkstra algorithm from node \c s
774    ///in order to compute the shortest path to each node.
[100]775    ///
[244]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.
[100]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    }
[209]791
[100]792    ///Finds the shortest path between \c s and \c t.
[209]793
[244]794    ///This method runs the %Dijkstra algorithm from node \c s
795    ///in order to compute the shortest path to \c t.
[100]796    ///
[244]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.
[100]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    }
[209]813
[100]814    ///@}
815
816    ///\name Query Functions
817    ///The result of the %Dijkstra algorithm can be obtained using these
818    ///functions.\n
[244]819    ///Either \ref lemon::Dijkstra::run() "run()" or
820    ///\ref lemon::Dijkstra::start() "start()" must be called before
821    ///using them.
[209]822
[100]823    ///@{
824
[244]825    ///The shortest path to a node.
[209]826
[244]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); }
[100]834
[244]835    ///The distance of a node from the root(s).
[100]836
[244]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.
[100]844    Value dist(Node v) const { return (*_dist)[v]; }
845
[244]846    ///Returns the 'previous arc' of the shortest path tree for a node.
[100]847
[244]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.
[100]858    Arc predArc(Node v) const { return (*_pred)[v]; }
859
[244]860    ///Returns the 'previous node' of the shortest path tree for a node.
[100]861
[244]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
[100]871    ///using this function.
872    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
[209]873                                  G->source((*_pred)[v]); }
874
[244]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.
[100]883    const DistMap &distMap() const { return *_dist;}
[209]884
[244]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.
[100]893    const PredMap &predMap() const { return *_pred;}
[209]894
[244]895    ///Checks if a node is reachable from the root(s).
[100]896
[244]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; }
[100]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.
[244]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]; }
[209]918
[100]919    ///@}
920  };
921
922
[244]923  ///Default traits class of dijkstra() function.
[100]924
[244]925  ///Default traits class of dijkstra() function.
926  ///\tparam GR The type of the digraph.
927  ///\tparam LM The type of the length map.
[100]928  template<class GR, class LM>
929  struct DijkstraWizardDefaultTraits
930  {
[244]931    ///The type of the digraph the algorithm runs on.
[100]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;
[244]938    ///The type of the length of the arcs.
[100]939    typedef typename LM::Value Value;
[244]940
[100]941    /// Operation traits for Dijkstra algorithm.
942
[244]943    /// This class defines the operations that are used in the algorithm.
[100]944    /// \see DijkstraDefaultOperationTraits
945    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
946
[244]947    /// The cross reference type used by the heap.
[100]948
[244]949    /// The cross reference type used by the heap.
[100]950    /// Usually it is \c Digraph::NodeMap<int>.
951    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
[244]952    ///Instantiates a \ref HeapCrossRef.
[100]953
[209]954    ///This function instantiates a \ref HeapCrossRef.
[244]955    /// \param g is the digraph, to which we would like to define the
[100]956    /// HeapCrossRef.
[244]957    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
[100]958    {
[244]959      return new HeapCrossRef(g);
[100]960    }
[209]961
[244]962    ///The heap type used by the Dijkstra algorithm.
[100]963
[244]964    ///The heap type used by the Dijkstra algorithm.
[100]965    ///
966    ///\sa BinHeap
967    ///\sa Dijkstra
[244]968    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
[209]969                    std::less<Value> > Heap;
[100]970
[244]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)
[100]976    {
[244]977      return new Heap(r);
[100]978    }
979
[244]980    ///\brief The type of the map that stores the predecessor
[100]981    ///arcs of the shortest paths.
[209]982    ///
[244]983    ///The type of the map that stores the predecessor
[100]984    ///arcs of the shortest paths.
985    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[278]986    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
[244]987    ///Instantiates a \ref PredMap.
[209]988
989    ///This function instantiates a \ref PredMap.
[244]990    ///\param g is the digraph, to which we would like to define the
991    ///\ref PredMap.
992    static PredMap *createPredMap(const Digraph &g)
[100]993    {
[278]994      return new PredMap(g);
[100]995    }
[209]996
[244]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.
[100]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;
[244]1003    ///Instantiates a \ref ProcessedMap.
[209]1004
1005    ///This function instantiates a \ref ProcessedMap.
[100]1006    ///\param g is the digraph, to which
[244]1007    ///we would like to define the \ref ProcessedMap.
[100]1008#ifdef DOXYGEN
[244]1009    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]1010#else
[244]1011    static ProcessedMap *createProcessedMap(const Digraph &)
[100]1012#endif
1013    {
1014      return new ProcessedMap();
1015    }
[209]1016
[244]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.
[100]1020    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[278]1021    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
[244]1022    ///Instantiates a \ref DistMap.
[209]1023
1024    ///This function instantiates a \ref DistMap.
[210]1025    ///\param g is the digraph, to which we would like to define
1026    ///the \ref DistMap
[244]1027    static DistMap *createDistMap(const Digraph &g)
[100]1028    {
[278]1029      return new DistMap(g);
[100]1030    }
[278]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;
[100]1037  };
[209]1038
[244]1039  /// Default traits class used by \ref DijkstraWizard
[100]1040
1041  /// To make it easier to use Dijkstra algorithm
[244]1042  /// we have created a wizard class.
[100]1043  /// This \ref DijkstraWizard class needs default traits,
[244]1044  /// as well as the \ref Dijkstra class.
[100]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:
[244]1052    //The type of the nodes in the digraph.
[100]1053    typedef typename Base::Digraph::Node Node;
1054
[244]1055    //Pointer to the digraph the algorithm runs on.
[100]1056    void *_g;
[278]1057    //Pointer to the length map.
[100]1058    void *_length;
[251]1059    //Pointer to the map of processed nodes.
1060    void *_processed;
[244]1061    //Pointer to the map of predecessors arcs.
[100]1062    void *_pred;
[244]1063    //Pointer to the map of distances.
[100]1064    void *_dist;
[278]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;
[100]1069
[244]1070  public:
[100]1071    /// Constructor.
[209]1072
[100]1073    /// This constructor does not require parameters, therefore it initiates
[278]1074    /// all of the attributes to \c 0.
[251]1075    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
[278]1076                           _dist(0), _path(0), _di(0) {}
[100]1077
1078    /// Constructor.
[209]1079
[278]1080    /// This constructor requires two parameters,
1081    /// others are initiated to \c 0.
[244]1082    /// \param g The digraph the algorithm runs on.
1083    /// \param l The length map.
[278]1084    DijkstraWizardBase(const GR &g,const LM &l) :
[209]1085      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1086      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
[278]1087      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
[100]1088
1089  };
[209]1090
[278]1091  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
[100]1092
[278]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.
[100]1097  ///
[278]1098  /// This class should only be used through the \ref dijkstra() function,
1099  /// which makes it easier to use the algorithm.
[100]1100  template<class TR>
1101  class DijkstraWizard : public TR
1102  {
1103    typedef TR Base;
1104
[244]1105    ///The type of the digraph the algorithm runs on.
[100]1106    typedef typename TR::Digraph Digraph;
[244]1107
[100]1108    typedef typename Digraph::Node Node;
1109    typedef typename Digraph::NodeIt NodeIt;
1110    typedef typename Digraph::Arc Arc;
1111    typedef typename Digraph::OutArcIt OutArcIt;
[209]1112
[100]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;
[244]1117    ///\brief The type of the map that stores the predecessor
[100]1118    ///arcs of the shortest paths.
1119    typedef typename TR::PredMap PredMap;
[244]1120    ///The type of the map that stores the distances of the nodes.
[100]1121    typedef typename TR::DistMap DistMap;
[244]1122    ///The type of the map that indicates which nodes are processed.
1123    typedef typename TR::ProcessedMap ProcessedMap;
[278]1124    ///The type of the shortest paths
1125    typedef typename TR::Path Path;
[100]1126    ///The heap type used by the dijkstra algorithm.
1127    typedef typename TR::Heap Heap;
[244]1128
[100]1129  public:
[244]1130
[100]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.
[278]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) {}
[100]1142
1143    ///Copy constructor
1144    DijkstraWizard(const TR &b) : TR(b) {}
1145
1146    ~DijkstraWizard() {}
1147
[278]1148    ///Runs Dijkstra algorithm from the given source node.
[209]1149
[278]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)
[100]1153    {
[278]1154      if (s==INVALID) throw UninitializedParameter();
[209]1155      Dijkstra<Digraph,LengthMap,TR>
[278]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);
[100]1165    }
1166
[278]1167    ///Finds the shortest path between \c s and \c t.
[100]1168
[278]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)
[100]1175    {
[278]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);
[244]1192    }
1193
[100]1194    template<class T>
[257]1195    struct SetPredMapBase : public Base {
[100]1196      typedef T PredMap;
1197      static PredMap *createPredMap(const Digraph &) { return 0; };
[257]1198      SetPredMapBase(const TR &b) : TR(b) {}
[100]1199    };
[278]1200    ///\brief \ref named-func-param "Named parameter"
[244]1201    ///for setting \ref PredMap object.
[100]1202    ///
[278]1203    ///\ref named-func-param "Named parameter"
[244]1204    ///for setting \ref PredMap object.
[100]1205    template<class T>
[257]1206    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
[100]1207    {
1208      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1209      return DijkstraWizard<SetPredMapBase<T> >(*this);
[100]1210    }
[209]1211
[100]1212    template<class T>
[278]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>
[257]1231    struct SetProcessedMapBase : public Base {
[244]1232      typedef T ProcessedMap;
1233      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
[257]1234      SetProcessedMapBase(const TR &b) : TR(b) {}
[244]1235    };
[278]1236    ///\brief \ref named-func-param "Named parameter"
[244]1237    ///for setting \ref ProcessedMap object.
1238    ///
[278]1239    /// \ref named-func-param "Named parameter"
[244]1240    ///for setting \ref ProcessedMap object.
1241    template<class T>
[257]1242    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
[244]1243    {
1244      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1245      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
[244]1246    }
1247
1248    template<class T>
[278]1249    struct SetPathBase : public Base {
1250      typedef T Path;
1251      SetPathBase(const TR &b) : TR(b) {}
[100]1252    };
[278]1253    ///\brief \ref named-func-param "Named parameter"
1254    ///for getting the shortest path to the target node.
[100]1255    ///
[278]1256    ///\ref named-func-param "Named parameter"
1257    ///for getting the shortest path to the target node.
[100]1258    template<class T>
[278]1259    DijkstraWizard<SetPathBase<T> > path(const T &t)
[100]1260    {
[278]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;
[100]1274    }
[209]1275
[100]1276  };
[209]1277
[278]1278  ///Function-type interface for Dijkstra algorithm.
[100]1279
1280  /// \ingroup shortest_path
[278]1281  ///Function-type interface for Dijkstra algorithm.
[100]1282  ///
[278]1283  ///This function also has several \ref named-func-param "named parameters",
[100]1284  ///they are declared as the members of class \ref DijkstraWizard.
[278]1285  ///The following examples show how to use these parameters.
[100]1286  ///\code
[278]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);
[100]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> >
[278]1299  dijkstra(const GR &digraph, const LM &length)
[100]1300  {
[278]1301    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
[100]1302  }
1303
1304} //END OF NAMESPACE LEMON
1305
1306#endif
Note: See TracBrowser for help on using the repository browser.