1.1 --- a/src/work/jacint/dijkstra.h Thu Apr 22 13:59:37 2004 +0000
1.2 +++ b/src/work/jacint/dijkstra.h Thu Apr 22 14:11:28 2004 +0000
1.3 @@ -1,4 +1,5 @@
1.4 // -*- C++ -*-
1.5 +
1.6 /*
1.7 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
1.8 *
1.9 @@ -26,98 +27,193 @@
1.10 #ifndef HUGO_DIJKSTRA_H
1.11 #define HUGO_DIJKSTRA_H
1.12
1.13 +///\file
1.14 +///\brief Dijkstra algorithm.
1.15 +
1.16 #include <fib_heap.h>
1.17 +#include <bin_heap.h>
1.18 #include <invalid.h>
1.19
1.20 namespace hugo {
1.21
1.22 - template <typename Graph, typename T,
1.23 - typename Heap=FibHeap<typename Graph::Node, T,
1.24 - typename Graph::NodeMap<int> >,
1.25 - typename LengthMap=typename Graph::EdgeMap<T> >
1.26 + //Alpar: Changed the order of the parameters
1.27 +
1.28 + ///%Dijkstra algorithm class.
1.29 +
1.30 + ///This class provides an efficient implementation of %Dijkstra algorithm.
1.31 + ///The edge lengths are passed to the algorithm using a
1.32 + ///\ref ReadMapSkeleton "readable map",
1.33 + ///so it is easy to change it to any kind of length.
1.34 + ///
1.35 + ///The type of the length is determined by the \c ValueType of the length map.
1.36 + ///
1.37 + ///It is also possible to change the underlying priority heap.
1.38 + ///
1.39 + ///\param Graph The graph type the algorithm runs on.
1.40 + ///\param LengthMap This read-only
1.41 + ///EdgeMap
1.42 + ///determines the
1.43 + ///lengths of the edges. It is read once for each edge, so the map
1.44 + ///may involve in relatively time consuming process to compute the edge
1.45 + ///length if it is necessary. The default map type is
1.46 + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.47 + ///\param Heap The heap type used by the %Dijkstra
1.48 + ///algorithm. The default
1.49 + ///is using \ref BinHeap "binary heap".
1.50 +
1.51 +#ifdef DOXYGEN
1.52 + template <typename Graph,
1.53 + typename LengthMap,
1.54 + typename Heap>
1.55 +#else
1.56 + template <typename Graph,
1.57 + typename LengthMap=typename Graph::EdgeMap<int>,
1.58 + template <class,class,class> class Heap = BinHeap >
1.59 +#endif
1.60 class Dijkstra{
1.61 + public:
1.62 typedef typename Graph::Node Node;
1.63 typedef typename Graph::NodeIt NodeIt;
1.64 typedef typename Graph::Edge Edge;
1.65 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.66
1.67 + typedef typename LengthMap::ValueType ValueType;
1.68 + typedef typename Graph::NodeMap<Edge> PredMap;
1.69 + typedef typename Graph::NodeMap<Node> PredNodeMap;
1.70 + typedef typename Graph::NodeMap<ValueType> DistMap;
1.71 +
1.72 + private:
1.73 const Graph& G;
1.74 const LengthMap& length;
1.75 - typename Graph::NodeMap<Edge> predecessor;
1.76 - typename Graph::NodeMap<T> distance;
1.77 - //FIXME:
1.78 - typename Graph::NodeMap<bool> reach;
1.79 - //typename Graph::NodeMap<int> reach;
1.80 + PredMap predecessor;
1.81 + PredNodeMap pred_node;
1.82 + DistMap distance;
1.83
1.84 public :
1.85
1.86 - /*
1.87 - The distance of the nodes is 0.
1.88 - */
1.89 - Dijkstra(Graph& _G, LengthMap& _length) : G(_G),
1.90 - length(_length), predecessor(_G), distance(_G), reach(_G) { }
1.91 + Dijkstra(Graph& _G, LengthMap& _length) :
1.92 + G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
1.93
1.94 + void run(Node s);
1.95 +
1.96 + ///The distance of a node from the source.
1.97
1.98 - void run(Node s) {
1.99 -
1.100 - NodeIt u;
1.101 - for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
1.102 - predecessor.set(u,INVALID);
1.103 - distance.set(u,0);
1.104 - reach.set(u,false);
1.105 - }
1.106 -
1.107 - //FIXME:
1.108 - typename Graph::NodeMap<bool> scanned(G,false);
1.109 - //typename Graph::NodeMap<int> scanned(G,false);
1.110 - typename Graph::NodeMap<int> heap_map(G,-1);
1.111 -
1.112 - Heap heap(heap_map);
1.113 + ///Returns the distance of a node from the source.
1.114 + ///\pre \ref run() must be called before using this function.
1.115 + ///\warning If node \c v in unreachable from the source the return value
1.116 + ///of this funcion is undefined.
1.117 + ValueType dist(Node v) const { return distance[v]; }
1.118 + ///Returns the edges of the shortest path tree.
1.119
1.120 - heap.push(s,0);
1.121 - reach.set(s, true);
1.122 + ///For a node \c v it returns the last edge of the shortest path
1.123 + ///from the source to \c v or INVALID if \c v is unreachable
1.124 + ///from the source.
1.125 + ///\pre \ref run() must be called before using this function.
1.126 + Edge pred(Node v) const { return predecessor[v]; }
1.127 + ///Returns the nodes of the shortest paths.
1.128
1.129 + ///For a node \c v it returns the last but one node of the shortest path
1.130 + ///from the source to \c v or INVALID if \c v is unreachable
1.131 + ///from the source.
1.132 + ///\pre \ref run() must be called before using this function.
1.133 + Node predNode(Node v) const { return pred_node[v]; }
1.134 +
1.135 + ///Returns a reference to the NodeMap of distances.
1.136 +
1.137 + ///\pre \ref run() must be called before using this function.
1.138 + ///
1.139 + const DistMap &distMap() const { return distance;}
1.140 + ///Returns a reference to the shortest path tree map.
1.141 +
1.142 + ///Returns a reference to the NodeMap of the edges of the
1.143 + ///shortest path tree.
1.144 + ///\pre \ref run() must be called before using this function.
1.145 + const PredMap &predMap() const { return predecessor;}
1.146 + ///Returns a reference to the map of nodes of shortest paths.
1.147 +
1.148 + ///Returns a reference to the NodeMap of the last but one nodes of the
1.149 + ///shortest paths.
1.150 + ///\pre \ref run() must be called before using this function.
1.151 + const PredNodeMap &predNodeMap() const { return pred_node;}
1.152 +
1.153 + ///Checks if a node is reachable from the source.
1.154 +
1.155 + ///Returns \c true if \c v is reachable from the source.
1.156 + ///\warning the source node is reported to be unreached!
1.157 + ///\todo Is this what we want?
1.158 + ///\pre \ref run() must be called before using this function.
1.159 + ///
1.160 + bool reached(Node v) { return G.valid(predecessor[v]); }
1.161 +
1.162 + };
1.163 +
1.164 +
1.165 + // **********************************************************************
1.166 + // IMPLEMENTATIONS
1.167 + // **********************************************************************
1.168 +
1.169 + ///Runs %Dijkstra algorithm from node the source.
1.170 +
1.171 + ///This method runs the %Dijkstra algorithm from a source node \c s
1.172 + ///in order to
1.173 + ///compute the
1.174 + ///shortest path to each node. The algorithm computes
1.175 + ///- The shortest path tree.
1.176 + ///- The distance of each node from the source.
1.177 + template <typename Graph, typename LengthMap,
1.178 + template<class,class,class> class Heap >
1.179 + void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
1.180 +
1.181 + NodeIt u;
1.182 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
1.183 + predecessor.set(u,INVALID);
1.184 + pred_node.set(u,INVALID);
1.185 + // If a node is unreacheable, then why should be the dist=0?
1.186 + // distance.set(u,0);
1.187 + // reach.set(u,false);
1.188 + }
1.189 +
1.190 + typename Graph::NodeMap<int> heap_map(G,-1);
1.191 +
1.192 + Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
1.193 +
1.194 + heap.push(s,0);
1.195 +
1.196 while ( !heap.empty() ) {
1.197
1.198 Node v=heap.top();
1.199 - T oldvalue=heap.get(v);
1.200 + ValueType oldvalue=heap[v];
1.201 heap.pop();
1.202 distance.set(v, oldvalue);
1.203 - scanned.set(v,true);
1.204 -
1.205 - OutEdgeIt e;
1.206 - for( G.first(e,v); G.valid(e); G.next(e)) {
1.207 +
1.208 + { //FIXME this bracket is for e to be local
1.209 + OutEdgeIt e;
1.210 + for(G.first(e, v);
1.211 + G.valid(e); G.next(e)) {
1.212 Node w=G.head(e);
1.213 -
1.214 - if ( !scanned[w] ) {
1.215 - if ( !reach[w] ) {
1.216 - reach.set(w,true);
1.217 - heap.push(w,oldvalue+length[e]);
1.218 +
1.219 + switch(heap.state(w)) {
1.220 + case heap.PRE_HEAP:
1.221 + heap.push(w,oldvalue+length[e]);
1.222 + predecessor.set(w,e);
1.223 + pred_node.set(w,v);
1.224 + break;
1.225 + case heap.IN_HEAP:
1.226 + if ( oldvalue+length[e] < heap[w] ) {
1.227 + heap.decrease(w, oldvalue+length[e]);
1.228 predecessor.set(w,e);
1.229 - } else if ( oldvalue+length[e] < heap.get(w) ) {
1.230 - predecessor.set(w,e);
1.231 - heap.decrease(w, oldvalue+length[e]);
1.232 + pred_node.set(w,v);
1.233 }
1.234 + break;
1.235 + case heap.POST_HEAP:
1.236 + break;
1.237 }
1.238 }
1.239 + } //FIXME tis bracket
1.240 }
1.241 - }
1.242 -
1.243 - T dist(Node v) {
1.244 - return distance[v];
1.245 - }
1.246 -
1.247 - Edge pred(Node v) {
1.248 - return predecessor[v];
1.249 - }
1.250 -
1.251 - bool reached(Node v) {
1.252 - return reach[v];
1.253 - }
1.254 -
1.255 - };
1.256 + }
1.257
1.258 -}
1.259 +} //END OF NAMESPACE HUGO
1.260
1.261 #endif
1.262