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