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