COIN-OR::LEMON - Graph Library

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

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

Merge

File size: 43.0 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
[286]727    ///Executes the algorithm until the given target node is processed.
[244]728
[286]729    ///Executes the algorithm until the given target node is processed.
[100]730    ///
731    ///This method runs the %Dijkstra algorithm from the root node(s)
[286]732    ///in order to compute the shortest path to \c t.
[100]733    ///
[244]734    ///The algorithm computes
[286]735    ///- the shortest path to \c t,
736    ///- the distance of \c t 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.
[286]740    void start(Node t)
[100]741    {
[286]742      while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
743      if ( !_heap->empty() ) {
744        finalizeNodeData(_heap->top(),_heap->prio());
745        _heap->pop();
746      }
[100]747    }
[209]748
[100]749    ///Executes the algorithm until a condition is met.
750
751    ///Executes the algorithm until a condition is met.
752    ///
[244]753    ///This method runs the %Dijkstra algorithm from the root node(s) in
754    ///order to compute the shortest path to a node \c v with
755    /// <tt>nm[v]</tt> true, if such a node can be found.
[100]756    ///
[244]757    ///\param nm A \c bool (or convertible) node map. The algorithm
[100]758    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
759    ///
760    ///\return The reached node \c v with <tt>nm[v]</tt> true or
761    ///\c INVALID if no such node was found.
[244]762    ///
763    ///\pre init() must be called and at least one root node should be
764    ///added with addSource() before using this function.
[100]765    template<class NodeBoolMap>
766    Node start(const NodeBoolMap &nm)
767    {
768      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
769      if ( _heap->empty() ) return INVALID;
770      finalizeNodeData(_heap->top(),_heap->prio());
771      return _heap->top();
772    }
[209]773
[286]774    ///Runs the algorithm from the given source node.
[209]775
[244]776    ///This method runs the %Dijkstra algorithm from node \c s
777    ///in order to compute the shortest path to each node.
[100]778    ///
[244]779    ///The algorithm computes
780    ///- the shortest path tree,
781    ///- the distance of each node from the root.
782    ///
783    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
[100]784    ///\code
785    ///  d.init();
786    ///  d.addSource(s);
787    ///  d.start();
788    ///\endcode
789    void run(Node s) {
790      init();
791      addSource(s);
792      start();
793    }
[209]794
[100]795    ///Finds the shortest path between \c s and \c t.
[209]796
[244]797    ///This method runs the %Dijkstra algorithm from node \c s
[286]798    ///in order to compute the shortest path to node \c t
799    ///(it stops searching when \c t is processed).
[100]800    ///
[286]801    ///\return \c true if \c t is reachable form \c s.
[244]802    ///
803    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
804    ///shortcut of the following code.
[100]805    ///\code
806    ///  d.init();
807    ///  d.addSource(s);
808    ///  d.start(t);
809    ///\endcode
[286]810    bool run(Node s,Node t) {
[100]811      init();
812      addSource(s);
813      start(t);
[286]814      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
[100]815    }
[209]816
[100]817    ///@}
818
819    ///\name Query Functions
820    ///The result of the %Dijkstra algorithm can be obtained using these
821    ///functions.\n
[244]822    ///Either \ref lemon::Dijkstra::run() "run()" or
823    ///\ref lemon::Dijkstra::start() "start()" must be called before
824    ///using them.
[209]825
[100]826    ///@{
827
[244]828    ///The shortest path to a node.
[209]829
[244]830    ///Returns the shortest path to a node.
831    ///
832    ///\warning \c t should be reachable from the root(s).
833    ///
834    ///\pre Either \ref run() or \ref start() must be called before
835    ///using this function.
836    Path path(Node t) const { return Path(*G, *_pred, t); }
[100]837
[244]838    ///The distance of a node from the root(s).
[100]839
[244]840    ///Returns the distance of a node from the root(s).
841    ///
842    ///\warning If node \c v is not reachable from the root(s), then
843    ///the return value of this function is undefined.
844    ///
845    ///\pre Either \ref run() or \ref start() must be called before
846    ///using this function.
[100]847    Value dist(Node v) const { return (*_dist)[v]; }
848
[244]849    ///Returns the 'previous arc' of the shortest path tree for a node.
[100]850
[244]851    ///This function returns the 'previous arc' of the shortest path
852    ///tree for the node \c v, i.e. it returns the last arc of a
853    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
854    ///is not reachable from the root(s) or if \c v is a root.
855    ///
856    ///The shortest path tree used here is equal to the shortest path
857    ///tree used in \ref predNode().
858    ///
859    ///\pre Either \ref run() or \ref start() must be called before
860    ///using this function.
[100]861    Arc predArc(Node v) const { return (*_pred)[v]; }
862
[244]863    ///Returns the 'previous node' of the shortest path tree for a node.
[100]864
[244]865    ///This function returns the 'previous node' of the shortest path
866    ///tree for the node \c v, i.e. it returns the last but one node
867    ///from a shortest path from the root(s) to \c v. It is \c INVALID
868    ///if \c v is not reachable from the root(s) or if \c v is a root.
869    ///
870    ///The shortest path tree used here is equal to the shortest path
871    ///tree used in \ref predArc().
872    ///
873    ///\pre Either \ref run() or \ref start() must be called before
[100]874    ///using this function.
875    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
[209]876                                  G->source((*_pred)[v]); }
877
[244]878    ///\brief Returns a const reference to the node map that stores the
879    ///distances of the nodes.
880    ///
881    ///Returns a const reference to the node map that stores the distances
882    ///of the nodes calculated by the algorithm.
883    ///
884    ///\pre Either \ref run() or \ref init()
885    ///must be called before using this function.
[100]886    const DistMap &distMap() const { return *_dist;}
[209]887
[244]888    ///\brief Returns a const reference to the node map that stores the
889    ///predecessor arcs.
890    ///
891    ///Returns a const reference to the node map that stores the predecessor
892    ///arcs, which form the shortest path tree.
893    ///
894    ///\pre Either \ref run() or \ref init()
895    ///must be called before using this function.
[100]896    const PredMap &predMap() const { return *_pred;}
[209]897
[244]898    ///Checks if a node is reachable from the root(s).
[100]899
[244]900    ///Returns \c true if \c v is reachable from the root(s).
901    ///\pre Either \ref run() or \ref start()
902    ///must be called before using this function.
903    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
904                                        Heap::PRE_HEAP; }
[100]905
906    ///Checks if a node is processed.
907
908    ///Returns \c true if \c v is processed, i.e. the shortest
909    ///path to \c v has already found.
[286]910    ///\pre Either \ref run() or \ref init()
[244]911    ///must be called before using this function.
912    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
913                                          Heap::POST_HEAP; }
914
915    ///The current distance of a node from the root(s).
916
917    ///Returns the current distance of a node from the root(s).
918    ///It may be decreased in the following processes.
[286]919    ///\pre Either \ref run() or \ref init()
920    ///must be called before using this function and
921    ///node \c v must be reached but not necessarily processed.
922    Value currentDist(Node v) const {
923      return processed(v) ? (*_dist)[v] : (*_heap)[v];
924    }
[209]925
[100]926    ///@}
927  };
928
929
[244]930  ///Default traits class of dijkstra() function.
[100]931
[244]932  ///Default traits class of dijkstra() function.
933  ///\tparam GR The type of the digraph.
934  ///\tparam LM The type of the length map.
[100]935  template<class GR, class LM>
936  struct DijkstraWizardDefaultTraits
937  {
[244]938    ///The type of the digraph the algorithm runs on.
[100]939    typedef GR Digraph;
940    ///The type of the map that stores the arc lengths.
941
942    ///The type of the map that stores the arc lengths.
943    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
944    typedef LM LengthMap;
[244]945    ///The type of the length of the arcs.
[100]946    typedef typename LM::Value Value;
[244]947
[100]948    /// Operation traits for Dijkstra algorithm.
949
[244]950    /// This class defines the operations that are used in the algorithm.
[100]951    /// \see DijkstraDefaultOperationTraits
952    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
953
[244]954    /// The cross reference type used by the heap.
[100]955
[244]956    /// The cross reference type used by the heap.
[100]957    /// Usually it is \c Digraph::NodeMap<int>.
958    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
[244]959    ///Instantiates a \ref HeapCrossRef.
[100]960
[209]961    ///This function instantiates a \ref HeapCrossRef.
[244]962    /// \param g is the digraph, to which we would like to define the
[100]963    /// HeapCrossRef.
[244]964    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
[100]965    {
[244]966      return new HeapCrossRef(g);
[100]967    }
[209]968
[244]969    ///The heap type used by the Dijkstra algorithm.
[100]970
[244]971    ///The heap type used by the Dijkstra algorithm.
[100]972    ///
973    ///\sa BinHeap
974    ///\sa Dijkstra
[244]975    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
[209]976                    std::less<Value> > Heap;
[100]977
[244]978    ///Instantiates a \ref Heap.
979
980    ///This function instantiates a \ref Heap.
981    /// \param r is the HeapCrossRef which is used.
982    static Heap *createHeap(HeapCrossRef& r)
[100]983    {
[244]984      return new Heap(r);
[100]985    }
986
[244]987    ///\brief The type of the map that stores the predecessor
[100]988    ///arcs of the shortest paths.
[209]989    ///
[244]990    ///The type of the map that stores the predecessor
[100]991    ///arcs of the shortest paths.
992    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[278]993    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
[244]994    ///Instantiates a \ref PredMap.
[209]995
996    ///This function instantiates a \ref PredMap.
[244]997    ///\param g is the digraph, to which we would like to define the
998    ///\ref PredMap.
999    static PredMap *createPredMap(const Digraph &g)
[100]1000    {
[278]1001      return new PredMap(g);
[100]1002    }
[209]1003
[244]1004    ///The type of the map that indicates which nodes are processed.
1005
1006    ///The type of the map that indicates which nodes are processed.
[100]1007    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1008    ///By default it is a NullMap.
1009    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
[244]1010    ///Instantiates a \ref ProcessedMap.
[209]1011
1012    ///This function instantiates a \ref ProcessedMap.
[100]1013    ///\param g is the digraph, to which
[244]1014    ///we would like to define the \ref ProcessedMap.
[100]1015#ifdef DOXYGEN
[244]1016    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]1017#else
[244]1018    static ProcessedMap *createProcessedMap(const Digraph &)
[100]1019#endif
1020    {
1021      return new ProcessedMap();
1022    }
[209]1023
[244]1024    ///The type of the map that stores the distances of the nodes.
1025
1026    ///The type of the map that stores the distances of the nodes.
[100]1027    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[278]1028    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
[244]1029    ///Instantiates a \ref DistMap.
[209]1030
1031    ///This function instantiates a \ref DistMap.
[210]1032    ///\param g is the digraph, to which we would like to define
1033    ///the \ref DistMap
[244]1034    static DistMap *createDistMap(const Digraph &g)
[100]1035    {
[278]1036      return new DistMap(g);
[100]1037    }
[278]1038
1039    ///The type of the shortest paths.
1040
1041    ///The type of the shortest paths.
1042    ///It must meet the \ref concepts::Path "Path" concept.
1043    typedef lemon::Path<Digraph> Path;
[100]1044  };
[209]1045
[244]1046  /// Default traits class used by \ref DijkstraWizard
[100]1047
1048  /// To make it easier to use Dijkstra algorithm
[244]1049  /// we have created a wizard class.
[100]1050  /// This \ref DijkstraWizard class needs default traits,
[244]1051  /// as well as the \ref Dijkstra class.
[100]1052  /// The \ref DijkstraWizardBase is a class to be the default traits of the
1053  /// \ref DijkstraWizard class.
1054  template<class GR,class LM>
1055  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1056  {
1057    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1058  protected:
[244]1059    //The type of the nodes in the digraph.
[100]1060    typedef typename Base::Digraph::Node Node;
1061
[244]1062    //Pointer to the digraph the algorithm runs on.
[100]1063    void *_g;
[278]1064    //Pointer to the length map.
[100]1065    void *_length;
[251]1066    //Pointer to the map of processed nodes.
1067    void *_processed;
[244]1068    //Pointer to the map of predecessors arcs.
[100]1069    void *_pred;
[244]1070    //Pointer to the map of distances.
[100]1071    void *_dist;
[278]1072    //Pointer to the shortest path to the target node.
1073    void *_path;
1074    //Pointer to the distance of the target node.
1075    void *_di;
[100]1076
[244]1077  public:
[100]1078    /// Constructor.
[209]1079
[100]1080    /// This constructor does not require parameters, therefore it initiates
[278]1081    /// all of the attributes to \c 0.
[251]1082    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
[278]1083                           _dist(0), _path(0), _di(0) {}
[100]1084
1085    /// Constructor.
[209]1086
[278]1087    /// This constructor requires two parameters,
1088    /// others are initiated to \c 0.
[244]1089    /// \param g The digraph the algorithm runs on.
1090    /// \param l The length map.
[278]1091    DijkstraWizardBase(const GR &g,const LM &l) :
[209]1092      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1093      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
[278]1094      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
[100]1095
1096  };
[209]1097
[278]1098  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
[100]1099
[278]1100  /// This auxiliary class is created to implement the
1101  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1102  /// It does not have own \ref run() method, it uses the functions
1103  /// and features of the plain \ref Dijkstra.
[100]1104  ///
[278]1105  /// This class should only be used through the \ref dijkstra() function,
1106  /// which makes it easier to use the algorithm.
[100]1107  template<class TR>
1108  class DijkstraWizard : public TR
1109  {
1110    typedef TR Base;
1111
[244]1112    ///The type of the digraph the algorithm runs on.
[100]1113    typedef typename TR::Digraph Digraph;
[244]1114
[100]1115    typedef typename Digraph::Node Node;
1116    typedef typename Digraph::NodeIt NodeIt;
1117    typedef typename Digraph::Arc Arc;
1118    typedef typename Digraph::OutArcIt OutArcIt;
[209]1119
[100]1120    ///The type of the map that stores the arc lengths.
1121    typedef typename TR::LengthMap LengthMap;
1122    ///The type of the length of the arcs.
1123    typedef typename LengthMap::Value Value;
[244]1124    ///\brief The type of the map that stores the predecessor
[100]1125    ///arcs of the shortest paths.
1126    typedef typename TR::PredMap PredMap;
[244]1127    ///The type of the map that stores the distances of the nodes.
[100]1128    typedef typename TR::DistMap DistMap;
[244]1129    ///The type of the map that indicates which nodes are processed.
1130    typedef typename TR::ProcessedMap ProcessedMap;
[278]1131    ///The type of the shortest paths
1132    typedef typename TR::Path Path;
[100]1133    ///The heap type used by the dijkstra algorithm.
1134    typedef typename TR::Heap Heap;
[244]1135
[100]1136  public:
[244]1137
[100]1138    /// Constructor.
1139    DijkstraWizard() : TR() {}
1140
1141    /// Constructor that requires parameters.
1142
1143    /// Constructor that requires parameters.
1144    /// These parameters will be the default values for the traits class.
[278]1145    /// \param g The digraph the algorithm runs on.
1146    /// \param l The length map.
1147    DijkstraWizard(const Digraph &g, const LengthMap &l) :
1148      TR(g,l) {}
[100]1149
1150    ///Copy constructor
1151    DijkstraWizard(const TR &b) : TR(b) {}
1152
1153    ~DijkstraWizard() {}
1154
[278]1155    ///Runs Dijkstra algorithm from the given source node.
[209]1156
[278]1157    ///This method runs %Dijkstra algorithm from the given source node
1158    ///in order to compute the shortest path to each node.
1159    void run(Node s)
[100]1160    {
[278]1161      if (s==INVALID) throw UninitializedParameter();
[209]1162      Dijkstra<Digraph,LengthMap,TR>
[278]1163        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1164             *reinterpret_cast<const LengthMap*>(Base::_length));
1165      if (Base::_pred)
1166        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1167      if (Base::_dist)
1168        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1169      if (Base::_processed)
1170        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1171      dijk.run(s);
[100]1172    }
1173
[278]1174    ///Finds the shortest path between \c s and \c t.
[100]1175
[278]1176    ///This method runs the %Dijkstra algorithm from node \c s
1177    ///in order to compute the shortest path to node \c t
1178    ///(it stops searching when \c t is processed).
1179    ///
1180    ///\return \c true if \c t is reachable form \c s.
1181    bool run(Node s, Node t)
[100]1182    {
[278]1183      if (s==INVALID || t==INVALID) throw UninitializedParameter();
1184      Dijkstra<Digraph,LengthMap,TR>
1185        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1186             *reinterpret_cast<const LengthMap*>(Base::_length));
1187      if (Base::_pred)
1188        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1189      if (Base::_dist)
1190        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1191      if (Base::_processed)
1192        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1193      dijk.run(s,t);
1194      if (Base::_path)
1195        *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
1196      if (Base::_di)
1197        *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
1198      return dijk.reached(t);
[244]1199    }
1200
[100]1201    template<class T>
[257]1202    struct SetPredMapBase : public Base {
[100]1203      typedef T PredMap;
1204      static PredMap *createPredMap(const Digraph &) { return 0; };
[257]1205      SetPredMapBase(const TR &b) : TR(b) {}
[100]1206    };
[278]1207    ///\brief \ref named-func-param "Named parameter"
[244]1208    ///for setting \ref PredMap object.
[100]1209    ///
[278]1210    ///\ref named-func-param "Named parameter"
[244]1211    ///for setting \ref PredMap object.
[100]1212    template<class T>
[257]1213    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
[100]1214    {
1215      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1216      return DijkstraWizard<SetPredMapBase<T> >(*this);
[100]1217    }
[209]1218
[100]1219    template<class T>
[278]1220    struct SetDistMapBase : public Base {
1221      typedef T DistMap;
1222      static DistMap *createDistMap(const Digraph &) { return 0; };
1223      SetDistMapBase(const TR &b) : TR(b) {}
1224    };
1225    ///\brief \ref named-func-param "Named parameter"
1226    ///for setting \ref DistMap object.
1227    ///
1228    ///\ref named-func-param "Named parameter"
1229    ///for setting \ref DistMap object.
1230    template<class T>
1231    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1232    {
1233      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1234      return DijkstraWizard<SetDistMapBase<T> >(*this);
1235    }
1236
1237    template<class T>
[257]1238    struct SetProcessedMapBase : public Base {
[244]1239      typedef T ProcessedMap;
1240      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
[257]1241      SetProcessedMapBase(const TR &b) : TR(b) {}
[244]1242    };
[278]1243    ///\brief \ref named-func-param "Named parameter"
[244]1244    ///for setting \ref ProcessedMap object.
1245    ///
[278]1246    /// \ref named-func-param "Named parameter"
[244]1247    ///for setting \ref ProcessedMap object.
1248    template<class T>
[257]1249    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
[244]1250    {
1251      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1252      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
[244]1253    }
1254
1255    template<class T>
[278]1256    struct SetPathBase : public Base {
1257      typedef T Path;
1258      SetPathBase(const TR &b) : TR(b) {}
[100]1259    };
[278]1260    ///\brief \ref named-func-param "Named parameter"
1261    ///for getting the shortest path to the target node.
[100]1262    ///
[278]1263    ///\ref named-func-param "Named parameter"
1264    ///for getting the shortest path to the target node.
[100]1265    template<class T>
[278]1266    DijkstraWizard<SetPathBase<T> > path(const T &t)
[100]1267    {
[278]1268      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1269      return DijkstraWizard<SetPathBase<T> >(*this);
1270    }
1271
1272    ///\brief \ref named-func-param "Named parameter"
1273    ///for getting the distance of the target node.
1274    ///
1275    ///\ref named-func-param "Named parameter"
1276    ///for getting the distance of the target node.
1277    DijkstraWizard dist(const Value &d)
1278    {
1279      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
1280      return *this;
[100]1281    }
[209]1282
[100]1283  };
[209]1284
[278]1285  ///Function-type interface for Dijkstra algorithm.
[100]1286
1287  /// \ingroup shortest_path
[278]1288  ///Function-type interface for Dijkstra algorithm.
[100]1289  ///
[278]1290  ///This function also has several \ref named-func-param "named parameters",
[100]1291  ///they are declared as the members of class \ref DijkstraWizard.
[278]1292  ///The following examples show how to use these parameters.
[100]1293  ///\code
[278]1294  ///  // Compute shortest path from node s to each node
1295  ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
1296  ///
1297  ///  // Compute shortest path from s to t
1298  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
[100]1299  ///\endcode
1300  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1301  ///to the end of the parameter list.
1302  ///\sa DijkstraWizard
1303  ///\sa Dijkstra
1304  template<class GR, class LM>
1305  DijkstraWizard<DijkstraWizardBase<GR,LM> >
[278]1306  dijkstra(const GR &digraph, const LM &length)
[100]1307  {
[278]1308    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
[100]1309  }
1310
1311} //END OF NAMESPACE LEMON
1312
1313#endif
Note: See TracBrowser for help on using the repository browser.