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