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