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