lemon/dijkstra.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 13 Mar 2010 22:01:38 +0100
changeset 864 d3ea191c3412
parent 788 c92296660262
child 877 141f9c0db4a3
permissions -rw-r--r--
Rename min mean cycle classes and their members (#179)
with respect to the possible introduction of min ratio
cycle algorithms in the future.

The renamed classes:
- Karp --> KarpMmc
- HartmannOrlin --> HartmannOrlinMmc
- Howard --> HowardMmc

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