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