Some changes in the documentation.
authorjacint
Fri, 23 Apr 2004 19:04:05 +0000
changeset 385d7ebbae96025
parent 384 f27d21767d38
child 386 0bdc7c279e79
Some changes in the documentation.
src/include/dijkstra.h
     1.1 --- a/src/include/dijkstra.h	Fri Apr 23 18:48:56 2004 +0000
     1.2 +++ b/src/include/dijkstra.h	Fri Apr 23 19:04:05 2004 +0000
     1.3 @@ -1,17 +1,15 @@
     1.4  // -*- C++ -*-
     1.5 -
     1.6  #ifndef HUGO_DIJKSTRA_H
     1.7  #define HUGO_DIJKSTRA_H
     1.8  
     1.9  ///\file
    1.10  ///\brief Dijkstra algorithm.
    1.11  
    1.12 -#include <fib_heap.h>
    1.13  #include <bin_heap.h>
    1.14  #include <invalid.h>
    1.15  
    1.16  namespace hugo {
    1.17 -  
    1.18 +
    1.19    ///%Dijkstra algorithm class.
    1.20  
    1.21    ///This class provides an efficient implementation of %Dijkstra algorithm.
    1.22 @@ -23,14 +21,17 @@
    1.23    ///
    1.24    ///It is also possible to change the underlying priority heap.
    1.25    ///
    1.26 -  ///\param Graph The graph type the algorithm runs on.  
    1.27 -  ///\param LengthMap This read-only EdgeMap determines the lengths of
    1.28 -  ///the edges. It is read once for each edge, so the map may involve
    1.29 -  ///in relatively time consuming process to compute the edge length
    1.30 -  ///if it is necessary. The default map type is \ref
    1.31 -  ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
    1.32 -  ///\param Heap The heap type used by the %Dijkstra algorithm. The
    1.33 -  ///default is using \ref BinHeap "binary heap".
    1.34 +  ///\param Graph The graph type the algorithm runs on.
    1.35 +  ///\param LengthMap This read-only
    1.36 +  ///EdgeMap
    1.37 +  ///determines the
    1.38 +  ///lengths of the edges. It is read once for each edge, so the map
    1.39 +  ///may involve in relatively time consuming process to compute the edge
    1.40 +  ///length if it is necessary. The default map type is
    1.41 +  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
    1.42 +  ///\param Heap The heap type used by the %Dijkstra
    1.43 +  ///algorithm. The default
    1.44 +  ///is using \ref BinHeap "binary heap".
    1.45    
    1.46  #ifdef DOXYGEN
    1.47    template <typename Graph,
    1.48 @@ -67,56 +68,61 @@
    1.49      
    1.50      void run(Node s);
    1.51      
    1.52 -    ///The distance of a node from the source.
    1.53 +    ///The distance of a node from the root.
    1.54  
    1.55 -    ///Returns the distance of a node from the source.
    1.56 +    ///Returns the distance of a node from the root.
    1.57      ///\pre \ref run() must be called before using this function.
    1.58 -    ///\warning If node \c v in unreachable from the source the return value
    1.59 +    ///\warning If node \c v in unreachable from the root the return value
    1.60      ///of this funcion is undefined.
    1.61      ValueType dist(Node v) const { return distance[v]; }
    1.62  
    1.63 -    ///Returns the edges of the shortest path tree.
    1.64 +    ///Returns the previous edge of the shortest path tree.
    1.65  
    1.66 -    ///For a node \c v it returns the last edge of the shortest path
    1.67 -    ///from the source to \c v or INVALID if \c v is unreachable
    1.68 -    ///from the source.
    1.69 -    ///\pre \ref run() must be called before using this function.
    1.70 +    ///For a node \c v it returns the previous edge of the shortest path tree,
    1.71 +    ///i.e. it returns the last edge from a shortest path from the root to \c
    1.72 +    ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
    1.73 +    ///shortest path tree used here is equal to the shortest path tree used in
    1.74 +    ///\ref predNode(Node v).  \pre \ref run() must be called before using
    1.75 +    ///this function.
    1.76      Edge pred(Node v) const { return predecessor[v]; }
    1.77  
    1.78 -    ///Returns the nodes of the shortest paths.
    1.79 +    ///Returns the previous node of the shortest path tree.
    1.80  
    1.81 -    ///For a node \c v it returns the last but one node of the shortest path
    1.82 -    ///from the source to \c v or INVALID if \c v is unreachable
    1.83 -    ///from the source.
    1.84 -    ///\pre \ref run() must be called before using this function.
    1.85 +    ///For a node \c v it returns the previous node of the shortest path tree,
    1.86 +    ///i.e. it returns the last but one node from a shortest path from the
    1.87 +    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    1.88 +    ///\c v=s. The shortest path tree used here is equal to the shortest path
    1.89 +    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
    1.90 +    ///using this function.
    1.91      Node predNode(Node v) const { return pred_node[v]; }
    1.92      
    1.93      ///Returns a reference to the NodeMap of distances.
    1.94  
    1.95 -    ///\pre \ref run() must be called before using this function.
    1.96 -    ///
    1.97 +    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
    1.98 +    ///be called before using this function.
    1.99      const DistMap &distMap() const { return distance;}
   1.100 -    
   1.101 + 
   1.102      ///Returns a reference to the shortest path tree map.
   1.103  
   1.104      ///Returns a reference to the NodeMap of the edges of the
   1.105      ///shortest path tree.
   1.106      ///\pre \ref run() must be called before using this function.
   1.107      const PredMap &predMap() const { return predecessor;}
   1.108 -    
   1.109 -    ///Returns a reference to the map of nodes of  shortest paths.
   1.110 + 
   1.111 +    ///Returns a reference to the map of nodes of shortest paths.
   1.112  
   1.113      ///Returns a reference to the NodeMap of the last but one nodes of the
   1.114 -    ///shortest paths.
   1.115 +    ///shortest path tree.
   1.116      ///\pre \ref run() must be called before using this function.
   1.117      const PredNodeMap &predNodeMap() const { return pred_node;}
   1.118  
   1.119 -    ///Checks if a node is reachable from the source.
   1.120 +    ///Checks if a node is reachable from the root.
   1.121  
   1.122 -    ///Returns \c true if \c v is reachable from the source.
   1.123 -    ///\warning the source node is reported to be unreached!
   1.124 +    ///Returns \c true if \c v is reachable from the root.
   1.125 +    ///\warning the root node is reported to be unreached!
   1.126      ///\todo Is this what we want?
   1.127      ///\pre \ref run() must be called before using this function.
   1.128 +    ///
   1.129      bool reached(Node v) { return G.valid(predecessor[v]); }
   1.130      
   1.131    };
   1.132 @@ -126,12 +132,14 @@
   1.133    //  IMPLEMENTATIONS
   1.134    // **********************************************************************
   1.135  
   1.136 -  ///Runs %Dijkstra algorithm from source node \c s.
   1.137 +  ///Runs %Dijkstra algorithm from node the root.
   1.138  
   1.139 -  ///This method runs the %Dijkstra algorithm from a source node \c s
   1.140 -  ///in order to compute the shortest path to each node. The algorithm
   1.141 -  ///computes - The shortest path tree.  - The distance of each node
   1.142 -  ///from the source.
   1.143 +  ///This method runs the %Dijkstra algorithm from a root node \c s
   1.144 +  ///in order to
   1.145 +  ///compute the
   1.146 +  ///shortest path to each node. The algorithm computes
   1.147 +  ///- The shortest path tree.
   1.148 +  ///- The distance of each node from the root.
   1.149    template <typename Graph, typename LengthMap,
   1.150  	    template<class,class,class> class Heap >
   1.151    void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
   1.152 @@ -145,18 +153,20 @@
   1.153      typename Graph::NodeMap<int> heap_map(G,-1);
   1.154      
   1.155      Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
   1.156 +    
   1.157      heap.push(s,0); 
   1.158      
   1.159 -    while ( !heap.empty() ) {
   1.160 -      
   1.161 -      Node v=heap.top(); 
   1.162 -      ValueType oldvalue=heap[v];
   1.163 -      heap.pop();
   1.164 -      distance.set(v, oldvalue);
   1.165 +      while ( !heap.empty() ) {
   1.166  	
   1.167 -      { //FIXME this bracket is for e to be local
   1.168 -	OutEdgeIt e;
   1.169 -	for(G.first(e, v); G.valid(e); G.next(e)) {
   1.170 +	Node v=heap.top(); 
   1.171 +	ValueType oldvalue=heap[v];
   1.172 +	heap.pop();
   1.173 +	distance.set(v, oldvalue);
   1.174 +	
   1.175 +	{ //FIXME this bracket is for e to be local
   1.176 +	  OutEdgeIt e;
   1.177 +	for(G.first(e, v);
   1.178 +	    G.valid(e); G.next(e)) {
   1.179  	  Node w=G.head(e); 
   1.180  	  
   1.181  	  switch(heap.state(w)) {
   1.182 @@ -176,8 +186,8 @@
   1.183  	    break;
   1.184  	  }
   1.185  	}
   1.186 -      } //FIXME this bracket
   1.187 -    }
   1.188 +      } //FIXME tis bracket
   1.189 +      }
   1.190    }
   1.191    
   1.192  } //END OF NAMESPACE HUGO