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