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