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