dijkstra.h and fib_heap.h has moved to include.
The versions of bin_heap.hh shuld be merged and renamed to bin_heap.h
1.1 --- a/doc/Doxyfile Mon Mar 29 08:22:39 2004 +0000
1.2 +++ b/doc/Doxyfile Mon Mar 29 08:31:01 2004 +0000
1.3 @@ -395,9 +395,9 @@
1.4 ../src/include/invalid.h \
1.5 ../src/include/smart_graph.h \
1.6 ../src/include/skeletons/maps.h \
1.7 - ../src/demo/alpar/dijkstra/dijkstra.h \
1.8 + ../src/include/dijkstra.h \
1.9 ../src/demo/alpar/dijkstra/bin_heap.hh \
1.10 - ../src/demo/alpar/dijkstra/fib_heap.h \
1.11 + ../src/include/fib_heap.h \
1.12 ../src/demo/athos/xy/xy.h \
1.13 maps.dox
1.14
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/include/dijkstra.h Mon Mar 29 08:31:01 2004 +0000
2.3 @@ -0,0 +1,236 @@
2.4 +// -*- C++ -*-
2.5 +
2.6 +/*
2.7 + *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
2.8 + *
2.9 + *Constructor:
2.10 + *
2.11 + *Dijkstra(Graph G, LengthMap length)
2.12 + *
2.13 + *
2.14 + *Methods:
2.15 + *
2.16 + *void run(Node s)
2.17 + *
2.18 + *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
2.19 + * Returns T() if v is not reachable from s.
2.20 + *
2.21 + *Edge pred(Node v) : After run(s) was run, it returns the last
2.22 + * edge of a shortest s-v path. It is INVALID for s and for
2.23 + * the nodes not reachable from s.
2.24 + *
2.25 + *bool reached(Node v) : After run(s) was run, it is true iff v is
2.26 + * reachable from s
2.27 + *
2.28 + */
2.29 +
2.30 +#ifndef HUGO_DIJKSTRA_H
2.31 +#define HUGO_DIJKSTRA_H
2.32 +
2.33 +///\file
2.34 +///\brief Dijkstra algorithm.
2.35 +
2.36 +#include "fib_heap.h"
2.37 +#include "bin_heap.hh"
2.38 +#include "invalid.h"
2.39 +
2.40 +namespace hugo {
2.41 +
2.42 + //Alpar: Changed the order of the parameters
2.43 +
2.44 + ///%Dijkstra algorithm class.
2.45 +
2.46 + ///This class provides an efficient implementation of %Dijkstra algorithm.
2.47 + ///The edge lengths are passed to the algorithm using a
2.48 + ///\ref ReadMapSkeleton "readable map",
2.49 + ///so it is easy to change it to any kind of length.
2.50 + ///
2.51 + ///The type of the length is determined by the \c ValueType of the length map.
2.52 + ///
2.53 + ///It is also possible to change the underlying priority heap.
2.54 + ///
2.55 + ///\param Graph The graph type the algorithm runs on.
2.56 + ///\param LengthMap This read-only
2.57 + ///EdgeMap
2.58 + ///determines the
2.59 + ///lengths of the edges. It is read once for each edge, so the map
2.60 + ///may involve in relatively time consuming process to compute the edge
2.61 + ///length if it is necessary. The default map type is
2.62 + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
2.63 + ///\param Heap The heap type used by the %Dijkstra
2.64 + ///algorithm. The default
2.65 + ///is using \ref BinHeap "binary heap".
2.66 +
2.67 +#ifdef DOXYGEN
2.68 + template <typename Graph,
2.69 + typename LengthMap,
2.70 + typename Heap>
2.71 +#else
2.72 + template <typename Graph,
2.73 + typename LengthMap=typename Graph::EdgeMap<int>,
2.74 + template <class,class,class> class Heap = BinHeap >
2.75 +// typename Heap=BinHeap <typename Graph::Node,
2.76 +// typename LengthMap::ValueType,
2.77 +// typename Graph::NodeMap<int> > >
2.78 +#endif
2.79 + class Dijkstra{
2.80 + public:
2.81 + typedef typename Graph::Node Node;
2.82 + typedef typename Graph::NodeIt NodeIt;
2.83 + typedef typename Graph::Edge Edge;
2.84 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.85 +
2.86 + typedef typename LengthMap::ValueType ValueType;
2.87 + typedef typename Graph::NodeMap<Edge> PredMap;
2.88 + typedef typename Graph::NodeMap<Node> PredNodeMap;
2.89 + typedef typename Graph::NodeMap<ValueType> DistMap;
2.90 +
2.91 + private:
2.92 + const Graph& G;
2.93 + const LengthMap& length;
2.94 + PredMap predecessor;
2.95 + //In place of reach:
2.96 + PredNodeMap pred_node;
2.97 + DistMap distance;
2.98 + //I don't like this:
2.99 + // //FIXME:
2.100 + // typename Graph::NodeMap<bool> reach;
2.101 + // //typename Graph::NodeMap<int> reach;
2.102 +
2.103 + public :
2.104 +
2.105 + /*
2.106 + The distance of the nodes is 0.
2.107 + */
2.108 + Dijkstra(Graph& _G, LengthMap& _length) :
2.109 + G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
2.110 +
2.111 + void run(Node s);
2.112 +
2.113 + ///The distance of a node from the source.
2.114 +
2.115 + ///Returns the distance of a node from the source.
2.116 + ///\pre \ref run() must be called before using this function.
2.117 + ///\warning If node \c v in unreachable from the source the return value
2.118 + ///of this funcion is undefined.
2.119 + ValueType dist(Node v) const { return distance[v]; }
2.120 + ///Returns the edges of the shortest path tree.
2.121 +
2.122 + ///For a node \c v it returns the last edge of the shortest path
2.123 + ///from the source to \c v or INVALID if \c v is unreachable
2.124 + ///from the source.
2.125 + ///\pre \ref run() must be called before using this function.
2.126 + Edge pred(Node v) const { return predecessor[v]; }
2.127 + ///Returns the nodes of the shortest paths.
2.128 +
2.129 + ///For a node \c v it returns the last but one node of the shortest path
2.130 + ///from the source to \c v or INVALID if \c v is unreachable
2.131 + ///from the source.
2.132 + ///\pre \ref run() must be called before using this function.
2.133 + Node predNode(Node v) const { return pred_node[v]; }
2.134 +
2.135 + ///Returns a reference to the NodeMap of distances.
2.136 +
2.137 + ///\pre \ref run() must be called before using this function.
2.138 + ///
2.139 + const DistMap &distMap() const { return distance;}
2.140 + ///Returns a reference to the shortest path tree map.
2.141 +
2.142 + ///Returns a reference to the NodeMap of the edges of the
2.143 + ///shortest path tree.
2.144 + ///\pre \ref run() must be called before using this function.
2.145 + const PredMap &predMap() const { return predecessor;}
2.146 + ///Returns a reference to the map of nodes of shortest paths.
2.147 +
2.148 + ///Returns a reference to the NodeMap of the last but one nodes of the
2.149 + ///shortest paths.
2.150 + ///\pre \ref run() must be called before using this function.
2.151 + const PredNodeMap &predNodeMap() const { return pred_node;}
2.152 +
2.153 + // bool reached(Node v) { return reach[v]; }
2.154 +
2.155 + ///Checks if a node is reachable from the source.
2.156 +
2.157 + ///Returns \c true if \c v is reachable from the source.
2.158 + ///\warning the source node is reported to be unreached!
2.159 + ///\todo Is this what we want?
2.160 + ///\pre \ref run() must be called before using this function.
2.161 + ///
2.162 + bool reached(Node v) { return G.valid(predecessor[v]); }
2.163 +
2.164 + };
2.165 +
2.166 +
2.167 + // **********************************************************************
2.168 + // IMPLEMENTATIONS
2.169 + // **********************************************************************
2.170 +
2.171 + ///Runs %Dijkstra algorithm from node the source.
2.172 +
2.173 + ///This method runs the %Dijkstra algorithm from a source node \c s
2.174 + ///in order to
2.175 + ///compute the
2.176 + ///shortest path to each node. The algorithm computes
2.177 + ///- The shortest path tree.
2.178 + ///- The distance of each node from the source.
2.179 + template <typename Graph, typename LengthMap,
2.180 + template<class,class,class> class Heap >
2.181 + void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
2.182 +
2.183 + NodeIt u;
2.184 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
2.185 + predecessor.set(u,INVALID);
2.186 + pred_node.set(u,INVALID);
2.187 + // If a node is unreacheable, then why should be the dist=0?
2.188 + // distance.set(u,0);
2.189 + // reach.set(u,false);
2.190 + }
2.191 +
2.192 + //We don't need it at all.
2.193 + // //FIXME:
2.194 + // typename Graph::NodeMap<bool> scanned(G,false);
2.195 + // //typename Graph::NodeMap<int> scanned(G,false);
2.196 + typename Graph::NodeMap<int> heap_map(G,-1);
2.197 +
2.198 + //Heap heap(heap_map);
2.199 + Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
2.200 +
2.201 + heap.push(s,0);
2.202 + // reach.set(s, true);
2.203 +
2.204 + while ( !heap.empty() ) {
2.205 +
2.206 + Node v=heap.top();
2.207 + ValueType oldvalue=heap[v];
2.208 + heap.pop();
2.209 + distance.set(v, oldvalue);
2.210 +
2.211 + for(OutEdgeIt e(G,v); G.valid(e); G.next(e)) {
2.212 + Node w=G.head(e);
2.213 +
2.214 + switch(heap.state(w)) {
2.215 + case heap.PRE_HEAP:
2.216 + // reach.set(w,true);
2.217 + heap.push(w,oldvalue+length[e]);
2.218 + predecessor.set(w,e);
2.219 + pred_node.set(w,v);
2.220 + break;
2.221 + case heap.IN_HEAP:
2.222 + if ( oldvalue+length[e] < heap[w] ) {
2.223 + heap.decrease(w, oldvalue+length[e]);
2.224 + predecessor.set(w,e);
2.225 + pred_node.set(w,v);
2.226 + }
2.227 + break;
2.228 + case heap.POST_HEAP:
2.229 + break;
2.230 + }
2.231 + }
2.232 + }
2.233 + }
2.234 +
2.235 +} //END OF NAMESPACE HUGO
2.236 +
2.237 +#endif
2.238 +
2.239 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/include/fib_heap.h Mon Mar 29 08:31:01 2004 +0000
3.3 @@ -0,0 +1,392 @@
3.4 +// -*- C++ -*-
3.5 +/*
3.6 + *template <typename Item,
3.7 + * typename Prio,
3.8 + * typename ItemIntMap,
3.9 + * typename Compare = std::less<Prio> >
3.10 + *
3.11 + *constructors:
3.12 + *
3.13 + *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
3.14 + *
3.15 + *Member functions:
3.16 + *
3.17 + *int size() : returns the number of elements in the heap
3.18 + *
3.19 + *bool empty() : true iff size()=0
3.20 + *
3.21 + *void set(Item, Prio) : calls push(Item, Prio) if Item is not
3.22 + * in the heap, and calls decrease/increase(Item, Prio) otherwise
3.23 + *
3.24 + *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
3.25 + * mustn't be in the heap.
3.26 + *
3.27 + *Item top() : returns the Item with least Prio.
3.28 + * Must be called only if heap is nonempty.
3.29 + *
3.30 + *Prio prio() : returns the least Prio
3.31 + * Must be called only if heap is nonempty.
3.32 + *
3.33 + *Prio get(Item) : returns Prio of Item
3.34 + * Must be called only if Item is in heap.
3.35 + *
3.36 + *void pop() : deletes the Item with least Prio
3.37 + *
3.38 + *void erase(Item) : deletes Item from the heap if it was already there
3.39 + *
3.40 + *void decrease(Item, P) : decreases prio of Item to P.
3.41 + * Item must be in the heap with prio at least P.
3.42 + *
3.43 + *void increase(Item, P) : sets prio of Item to P.
3.44 + *
3.45 + *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
3.46 + * heap until now, IN_HEAP if it is in the heap at the moment, and
3.47 + * POST_HEAP otherwise. In the latter case it is possible that Item
3.48 + * will get back to the heap again.
3.49 + *
3.50 + *In Fibonacci heaps, increase and erase are not efficient, in case of
3.51 + *many calls to these operations, it is better to use bin_heap.
3.52 + */
3.53 +
3.54 +#ifndef FIB_HEAP_H
3.55 +#define FIB_HEAP_H
3.56 +
3.57 +///\file
3.58 +///\brief Fibonacci Heap implementation.
3.59 +
3.60 +#include <vector>
3.61 +#include <functional>
3.62 +#include <math.h>
3.63 +
3.64 +namespace hugo {
3.65 +
3.66 + /// A Fibonacci Heap implementation.
3.67 + template <typename Item, typename Prio, typename ItemIntMap,
3.68 + typename Compare = std::less<Prio> >
3.69 + class FibHeap {
3.70 +
3.71 + typedef Prio PrioType;
3.72 +
3.73 + class store;
3.74 +
3.75 + std::vector<store> container;
3.76 + int minimum;
3.77 + ItemIntMap &iimap;
3.78 + Compare comp;
3.79 + int num_items;
3.80 +
3.81 + ///\todo It is use nowhere
3.82 + ///\todo It doesn't conform to the naming conventions.
3.83 + public:
3.84 + enum state_enum {
3.85 + IN_HEAP = 0,
3.86 + PRE_HEAP = -1,
3.87 + POST_HEAP = -2
3.88 + };
3.89 +
3.90 + public :
3.91 +
3.92 + FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
3.93 + FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
3.94 + iimap(_iimap), comp(_comp), num_items() {}
3.95 +
3.96 +
3.97 + int size() const {
3.98 + return num_items;
3.99 + }
3.100 +
3.101 +
3.102 + bool empty() const { return num_items==0; }
3.103 +
3.104 +
3.105 + void set (Item const it, PrioType const value) {
3.106 + int i=iimap[it];
3.107 + if ( i >= 0 && container[i].in ) {
3.108 + if ( comp(value, container[i].prio) ) decrease(it, value);
3.109 + if ( comp(container[i].prio, value) ) increase(it, value);
3.110 + } else push(it, value);
3.111 + }
3.112 +
3.113 +
3.114 + void push (Item const it, PrioType const value) {
3.115 + int i=iimap[it];
3.116 + if ( i < 0 ) {
3.117 + int s=container.size();
3.118 + iimap.set( it, s );
3.119 + store st;
3.120 + st.name=it;
3.121 + container.push_back(st);
3.122 + i=s;
3.123 + } else {
3.124 + container[i].parent=container[i].child=-1;
3.125 + container[i].degree=0;
3.126 + container[i].in=true;
3.127 + container[i].marked=false;
3.128 + }
3.129 +
3.130 + if ( num_items ) {
3.131 + container[container[minimum].right_neighbor].left_neighbor=i;
3.132 + container[i].right_neighbor=container[minimum].right_neighbor;
3.133 + container[minimum].right_neighbor=i;
3.134 + container[i].left_neighbor=minimum;
3.135 + if ( comp( value, container[minimum].prio) ) minimum=i;
3.136 + } else {
3.137 + container[i].right_neighbor=container[i].left_neighbor=i;
3.138 + minimum=i;
3.139 + }
3.140 + container[i].prio=value;
3.141 + ++num_items;
3.142 + }
3.143 +
3.144 +
3.145 + Item top() const {
3.146 + return container[minimum].name;
3.147 + }
3.148 +
3.149 +
3.150 + PrioType prio() const {
3.151 + return container[minimum].prio;
3.152 + }
3.153 +
3.154 +
3.155 +
3.156 +
3.157 + PrioType& operator[](const Item& it) {
3.158 + return container[iimap[it]].prio;
3.159 + }
3.160 +
3.161 + const PrioType& operator[](const Item& it) const {
3.162 + return container[iimap[it]].prio;
3.163 + }
3.164 +
3.165 +// const PrioType get(const Item& it) const {
3.166 +// return container[iimap[it]].prio;
3.167 +// }
3.168 +
3.169 + void pop() {
3.170 + /*The first case is that there are only one root.*/
3.171 + if ( container[minimum].left_neighbor==minimum ) {
3.172 + container[minimum].in=false;
3.173 + if ( container[minimum].degree!=0 ) {
3.174 + makeroot(container[minimum].child);
3.175 + minimum=container[minimum].child;
3.176 + balance();
3.177 + }
3.178 + } else {
3.179 + int right=container[minimum].right_neighbor;
3.180 + unlace(minimum);
3.181 + container[minimum].in=false;
3.182 + if ( container[minimum].degree > 0 ) {
3.183 + int left=container[minimum].left_neighbor;
3.184 + int child=container[minimum].child;
3.185 + int last_child=container[child].left_neighbor;
3.186 +
3.187 + makeroot(child);
3.188 +
3.189 + container[left].right_neighbor=child;
3.190 + container[child].left_neighbor=left;
3.191 + container[right].left_neighbor=last_child;
3.192 + container[last_child].right_neighbor=right;
3.193 + }
3.194 + minimum=right;
3.195 + balance();
3.196 + } // the case where there are more roots
3.197 + --num_items;
3.198 + }
3.199 +
3.200 +
3.201 + void erase (const Item& it) {
3.202 + int i=iimap[it];
3.203 +
3.204 + if ( i >= 0 && container[i].in ) {
3.205 + if ( container[i].parent!=-1 ) {
3.206 + int p=container[i].parent;
3.207 + cut(i,p);
3.208 + cascade(p);
3.209 + }
3.210 + minimum=i; //As if its prio would be -infinity
3.211 + pop();
3.212 + }
3.213 + }
3.214 +
3.215 +
3.216 + void decrease (Item it, PrioType const value) {
3.217 + int i=iimap[it];
3.218 + container[i].prio=value;
3.219 + int p=container[i].parent;
3.220 +
3.221 + if ( p!=-1 && comp(value, container[p].prio) ) {
3.222 + cut(i,p);
3.223 + cascade(p);
3.224 + }
3.225 + if ( comp(value, container[minimum].prio) ) minimum=i;
3.226 + }
3.227 +
3.228 +
3.229 + void increase (Item it, PrioType const value) {
3.230 + erase(it);
3.231 + push(it, value);
3.232 + }
3.233 +
3.234 +
3.235 + state_enum state(const Item &it) const {
3.236 + int i=iimap[it];
3.237 + if( i>=0 ) {
3.238 + if ( container[i].in ) i=0;
3.239 + else i=-2;
3.240 + }
3.241 + return state_enum(i);
3.242 + }
3.243 +
3.244 +
3.245 + private:
3.246 +
3.247 + void balance() {
3.248 +
3.249 + int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
3.250 +
3.251 + std::vector<int> A(maxdeg,-1);
3.252 +
3.253 + /*
3.254 + *Recall that now minimum does not point to the minimum prio element.
3.255 + *We set minimum to this during balance().
3.256 + */
3.257 + int anchor=container[minimum].left_neighbor;
3.258 + int next=minimum;
3.259 + bool end=false;
3.260 +
3.261 + do {
3.262 + int active=next;
3.263 + if ( anchor==active ) end=true;
3.264 + int d=container[active].degree;
3.265 + next=container[active].right_neighbor;
3.266 +
3.267 + while (A[d]!=-1) {
3.268 + if( comp(container[active].prio, container[A[d]].prio) ) {
3.269 + fuse(active,A[d]);
3.270 + } else {
3.271 + fuse(A[d],active);
3.272 + active=A[d];
3.273 + }
3.274 + A[d]=-1;
3.275 + ++d;
3.276 + }
3.277 + A[d]=active;
3.278 + } while ( !end );
3.279 +
3.280 +
3.281 + while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
3.282 + int s=minimum;
3.283 + int m=minimum;
3.284 + do {
3.285 + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
3.286 + s=container[s].right_neighbor;
3.287 + } while ( s != m );
3.288 + }
3.289 +
3.290 +
3.291 + void makeroot (int c) {
3.292 + int s=c;
3.293 + do {
3.294 + container[s].parent=-1;
3.295 + s=container[s].right_neighbor;
3.296 + } while ( s != c );
3.297 + }
3.298 +
3.299 +
3.300 + void cut (int a, int b) {
3.301 + /*
3.302 + *Replacing a from the children of b.
3.303 + */
3.304 + --container[b].degree;
3.305 +
3.306 + if ( container[b].degree !=0 ) {
3.307 + int child=container[b].child;
3.308 + if ( child==a )
3.309 + container[b].child=container[child].right_neighbor;
3.310 + unlace(a);
3.311 + }
3.312 +
3.313 +
3.314 + /*Lacing a to the roots.*/
3.315 + int right=container[minimum].right_neighbor;
3.316 + container[minimum].right_neighbor=a;
3.317 + container[a].left_neighbor=minimum;
3.318 + container[a].right_neighbor=right;
3.319 + container[right].left_neighbor=a;
3.320 +
3.321 + container[a].parent=-1;
3.322 + container[a].marked=false;
3.323 + }
3.324 +
3.325 +
3.326 + void cascade (int a)
3.327 + {
3.328 + if ( container[a].parent!=-1 ) {
3.329 + int p=container[a].parent;
3.330 +
3.331 + if ( container[a].marked==false ) container[a].marked=true;
3.332 + else {
3.333 + cut(a,p);
3.334 + cascade(p);
3.335 + }
3.336 + }
3.337 + }
3.338 +
3.339 +
3.340 + void fuse (int a, int b) {
3.341 + unlace(b);
3.342 +
3.343 + /*Lacing b under a.*/
3.344 + container[b].parent=a;
3.345 +
3.346 + if (container[a].degree==0) {
3.347 + container[b].left_neighbor=b;
3.348 + container[b].right_neighbor=b;
3.349 + container[a].child=b;
3.350 + } else {
3.351 + int child=container[a].child;
3.352 + int last_child=container[child].left_neighbor;
3.353 + container[child].left_neighbor=b;
3.354 + container[b].right_neighbor=child;
3.355 + container[last_child].right_neighbor=b;
3.356 + container[b].left_neighbor=last_child;
3.357 + }
3.358 +
3.359 + ++container[a].degree;
3.360 +
3.361 + container[b].marked=false;
3.362 + }
3.363 +
3.364 +
3.365 + /*
3.366 + *It is invoked only if a has siblings.
3.367 + */
3.368 + void unlace (int a) {
3.369 + int leftn=container[a].left_neighbor;
3.370 + int rightn=container[a].right_neighbor;
3.371 + container[leftn].right_neighbor=rightn;
3.372 + container[rightn].left_neighbor=leftn;
3.373 + }
3.374 +
3.375 +
3.376 + class store {
3.377 + friend class FibHeap;
3.378 +
3.379 + Item name;
3.380 + int parent;
3.381 + int left_neighbor;
3.382 + int right_neighbor;
3.383 + int child;
3.384 + int degree;
3.385 + bool marked;
3.386 + bool in;
3.387 + PrioType prio;
3.388 +
3.389 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
3.390 + };
3.391 +
3.392 + };
3.393 +
3.394 +} //namespace hugo
3.395 +#endif
4.1 --- a/src/work/alpar/dijkstra/dijkstra.h Mon Mar 29 08:22:39 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,236 +0,0 @@
4.4 -// -*- C++ -*-
4.5 -
4.6 -/*
4.7 - *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
4.8 - *
4.9 - *Constructor:
4.10 - *
4.11 - *Dijkstra(Graph G, LengthMap length)
4.12 - *
4.13 - *
4.14 - *Methods:
4.15 - *
4.16 - *void run(Node s)
4.17 - *
4.18 - *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
4.19 - * Returns T() if v is not reachable from s.
4.20 - *
4.21 - *Edge pred(Node v) : After run(s) was run, it returns the last
4.22 - * edge of a shortest s-v path. It is INVALID for s and for
4.23 - * the nodes not reachable from s.
4.24 - *
4.25 - *bool reached(Node v) : After run(s) was run, it is true iff v is
4.26 - * reachable from s
4.27 - *
4.28 - */
4.29 -
4.30 -#ifndef HUGO_DIJKSTRA_H
4.31 -#define HUGO_DIJKSTRA_H
4.32 -
4.33 -///\file
4.34 -///\brief Dijkstra algorithm.
4.35 -
4.36 -#include <fib_heap.h>
4.37 -#include <bin_heap.hh>
4.38 -#include <invalid.h>
4.39 -
4.40 -namespace hugo {
4.41 -
4.42 - //Alpar: Changed the order of the parameters
4.43 -
4.44 - ///%Dijkstra algorithm class.
4.45 -
4.46 - ///This class provides an efficient implementation of %Dijkstra algorithm.
4.47 - ///The edge lengths are passed to the algorithm using a
4.48 - ///\ref ReadMapSkeleton "readable map",
4.49 - ///so it is easy to change it to any kind of length.
4.50 - ///
4.51 - ///The type of the length is determined by the \c ValueType of the length map.
4.52 - ///
4.53 - ///It is also possible to change the underlying priority heap.
4.54 - ///
4.55 - ///\param Graph The graph type the algorithm runs on.
4.56 - ///\param LengthMap This read-only
4.57 - ///EdgeMap
4.58 - ///determines the
4.59 - ///lengths of the edges. It is read once for each edge, so the map
4.60 - ///may involve in relatively time consuming process to compute the edge
4.61 - ///length if it is necessary. The default map type is
4.62 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
4.63 - ///\param Heap The heap type used by the %Dijkstra
4.64 - ///algorithm. The default
4.65 - ///is using \ref BinHeap "binary heap".
4.66 -
4.67 -#ifdef DOXYGEN
4.68 - template <typename Graph,
4.69 - typename LengthMap,
4.70 - typename Heap>
4.71 -#else
4.72 - template <typename Graph,
4.73 - typename LengthMap=typename Graph::EdgeMap<int>,
4.74 - template <class,class,class> class Heap = BinHeap >
4.75 -// typename Heap=BinHeap <typename Graph::Node,
4.76 -// typename LengthMap::ValueType,
4.77 -// typename Graph::NodeMap<int> > >
4.78 -#endif
4.79 - class Dijkstra{
4.80 - public:
4.81 - typedef typename Graph::Node Node;
4.82 - typedef typename Graph::NodeIt NodeIt;
4.83 - typedef typename Graph::Edge Edge;
4.84 - typedef typename Graph::OutEdgeIt OutEdgeIt;
4.85 -
4.86 - typedef typename LengthMap::ValueType ValueType;
4.87 - typedef typename Graph::NodeMap<Edge> PredMap;
4.88 - typedef typename Graph::NodeMap<Node> PredNodeMap;
4.89 - typedef typename Graph::NodeMap<ValueType> DistMap;
4.90 -
4.91 - private:
4.92 - const Graph& G;
4.93 - const LengthMap& length;
4.94 - PredMap predecessor;
4.95 - //In place of reach:
4.96 - PredNodeMap pred_node;
4.97 - DistMap distance;
4.98 - //I don't like this:
4.99 - // //FIXME:
4.100 - // typename Graph::NodeMap<bool> reach;
4.101 - // //typename Graph::NodeMap<int> reach;
4.102 -
4.103 - public :
4.104 -
4.105 - /*
4.106 - The distance of the nodes is 0.
4.107 - */
4.108 - Dijkstra(Graph& _G, LengthMap& _length) :
4.109 - G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
4.110 -
4.111 - void run(Node s);
4.112 -
4.113 - ///The distance of a node from the source.
4.114 -
4.115 - ///Returns the distance of a node from the source.
4.116 - ///\pre \ref run() must be called before using this function.
4.117 - ///\warning If node \c v in unreachable from the source the return value
4.118 - ///of this funcion is undefined.
4.119 - ValueType dist(Node v) const { return distance[v]; }
4.120 - ///Returns the edges of the shortest path tree.
4.121 -
4.122 - ///For a node \c v it returns the last edge of the shortest path
4.123 - ///from the source to \c v or INVALID if \c v is unreachable
4.124 - ///from the source.
4.125 - ///\pre \ref run() must be called before using this function.
4.126 - Edge pred(Node v) const { return predecessor[v]; }
4.127 - ///Returns the nodes of the shortest paths.
4.128 -
4.129 - ///For a node \c v it returns the last but one node of the shortest path
4.130 - ///from the source to \c v or INVALID if \c v is unreachable
4.131 - ///from the source.
4.132 - ///\pre \ref run() must be called before using this function.
4.133 - Node predNode(Node v) const { return pred_node[v]; }
4.134 -
4.135 - ///Returns a reference to the NodeMap of distances.
4.136 -
4.137 - ///\pre \ref run() must be called before using this function.
4.138 - ///
4.139 - const DistMap &distMap() const { return distance;}
4.140 - ///Returns a reference to the shortest path tree map.
4.141 -
4.142 - ///Returns a reference to the NodeMap of the edges of the
4.143 - ///shortest path tree.
4.144 - ///\pre \ref run() must be called before using this function.
4.145 - const PredMap &predMap() const { return predecessor;}
4.146 - ///Returns a reference to the map of nodes of shortest paths.
4.147 -
4.148 - ///Returns a reference to the NodeMap of the last but one nodes of the
4.149 - ///shortest paths.
4.150 - ///\pre \ref run() must be called before using this function.
4.151 - const PredNodeMap &predNodeMap() const { return pred_node;}
4.152 -
4.153 - // bool reached(Node v) { return reach[v]; }
4.154 -
4.155 - ///Checks if a node is reachable from the source.
4.156 -
4.157 - ///Returns \c true if \c v is reachable from the source.
4.158 - ///\warning the source node is reported to be unreached!
4.159 - ///\todo Is this what we want?
4.160 - ///\pre \ref run() must be called before using this function.
4.161 - ///
4.162 - bool reached(Node v) { return G.valid(predecessor[v]); }
4.163 -
4.164 - };
4.165 -
4.166 -
4.167 - // **********************************************************************
4.168 - // IMPLEMENTATIONS
4.169 - // **********************************************************************
4.170 -
4.171 - ///Runs %Dijkstra algorithm from node the source.
4.172 -
4.173 - ///This method runs the %Dijkstra algorithm from a source node \c s
4.174 - ///in order to
4.175 - ///compute the
4.176 - ///shortest path to each node. The algorithm computes
4.177 - ///- The shortest path tree.
4.178 - ///- The distance of each node from the source.
4.179 - template <typename Graph, typename LengthMap,
4.180 - template<class,class,class> class Heap >
4.181 - void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
4.182 -
4.183 - NodeIt u;
4.184 - for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
4.185 - predecessor.set(u,INVALID);
4.186 - pred_node.set(u,INVALID);
4.187 - // If a node is unreacheable, then why should be the dist=0?
4.188 - // distance.set(u,0);
4.189 - // reach.set(u,false);
4.190 - }
4.191 -
4.192 - //We don't need it at all.
4.193 - // //FIXME:
4.194 - // typename Graph::NodeMap<bool> scanned(G,false);
4.195 - // //typename Graph::NodeMap<int> scanned(G,false);
4.196 - typename Graph::NodeMap<int> heap_map(G,-1);
4.197 -
4.198 - //Heap heap(heap_map);
4.199 - Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
4.200 -
4.201 - heap.push(s,0);
4.202 - // reach.set(s, true);
4.203 -
4.204 - while ( !heap.empty() ) {
4.205 -
4.206 - Node v=heap.top();
4.207 - ValueType oldvalue=heap[v];
4.208 - heap.pop();
4.209 - distance.set(v, oldvalue);
4.210 -
4.211 - for(OutEdgeIt e(G,v); G.valid(e); G.next(e)) {
4.212 - Node w=G.head(e);
4.213 -
4.214 - switch(heap.state(w)) {
4.215 - case heap.PRE_HEAP:
4.216 - // reach.set(w,true);
4.217 - heap.push(w,oldvalue+length[e]);
4.218 - predecessor.set(w,e);
4.219 - pred_node.set(w,v);
4.220 - break;
4.221 - case heap.IN_HEAP:
4.222 - if ( oldvalue+length[e] < heap[w] ) {
4.223 - heap.decrease(w, oldvalue+length[e]);
4.224 - predecessor.set(w,e);
4.225 - pred_node.set(w,v);
4.226 - }
4.227 - break;
4.228 - case heap.POST_HEAP:
4.229 - break;
4.230 - }
4.231 - }
4.232 - }
4.233 - }
4.234 -
4.235 -} //END OF NAMESPACE HUGO
4.236 -
4.237 -#endif
4.238 -
4.239 -
5.1 --- a/src/work/alpar/dijkstra/fib_heap.h Mon Mar 29 08:22:39 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,392 +0,0 @@
5.4 -// -*- C++ -*-
5.5 -/*
5.6 - *template <typename Item,
5.7 - * typename Prio,
5.8 - * typename ItemIntMap,
5.9 - * typename Compare = std::less<Prio> >
5.10 - *
5.11 - *constructors:
5.12 - *
5.13 - *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
5.14 - *
5.15 - *Member functions:
5.16 - *
5.17 - *int size() : returns the number of elements in the heap
5.18 - *
5.19 - *bool empty() : true iff size()=0
5.20 - *
5.21 - *void set(Item, Prio) : calls push(Item, Prio) if Item is not
5.22 - * in the heap, and calls decrease/increase(Item, Prio) otherwise
5.23 - *
5.24 - *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
5.25 - * mustn't be in the heap.
5.26 - *
5.27 - *Item top() : returns the Item with least Prio.
5.28 - * Must be called only if heap is nonempty.
5.29 - *
5.30 - *Prio prio() : returns the least Prio
5.31 - * Must be called only if heap is nonempty.
5.32 - *
5.33 - *Prio get(Item) : returns Prio of Item
5.34 - * Must be called only if Item is in heap.
5.35 - *
5.36 - *void pop() : deletes the Item with least Prio
5.37 - *
5.38 - *void erase(Item) : deletes Item from the heap if it was already there
5.39 - *
5.40 - *void decrease(Item, P) : decreases prio of Item to P.
5.41 - * Item must be in the heap with prio at least P.
5.42 - *
5.43 - *void increase(Item, P) : sets prio of Item to P.
5.44 - *
5.45 - *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
5.46 - * heap until now, IN_HEAP if it is in the heap at the moment, and
5.47 - * POST_HEAP otherwise. In the latter case it is possible that Item
5.48 - * will get back to the heap again.
5.49 - *
5.50 - *In Fibonacci heaps, increase and erase are not efficient, in case of
5.51 - *many calls to these operations, it is better to use bin_heap.
5.52 - */
5.53 -
5.54 -#ifndef FIB_HEAP_H
5.55 -#define FIB_HEAP_H
5.56 -
5.57 -///\file
5.58 -///\brief Fibonacci Heap implementation.
5.59 -
5.60 -#include <vector>
5.61 -#include <functional>
5.62 -#include <math.h>
5.63 -
5.64 -namespace hugo {
5.65 -
5.66 - /// A Fibonacci Heap implementation.
5.67 - template <typename Item, typename Prio, typename ItemIntMap,
5.68 - typename Compare = std::less<Prio> >
5.69 - class FibHeap {
5.70 -
5.71 - typedef Prio PrioType;
5.72 -
5.73 - class store;
5.74 -
5.75 - std::vector<store> container;
5.76 - int minimum;
5.77 - ItemIntMap &iimap;
5.78 - Compare comp;
5.79 - int num_items;
5.80 -
5.81 - ///\todo It is use nowhere
5.82 - ///\todo It doesn't conform to the naming conventions.
5.83 - public:
5.84 - enum state_enum {
5.85 - IN_HEAP = 0,
5.86 - PRE_HEAP = -1,
5.87 - POST_HEAP = -2
5.88 - };
5.89 -
5.90 - public :
5.91 -
5.92 - FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
5.93 - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
5.94 - iimap(_iimap), comp(_comp), num_items() {}
5.95 -
5.96 -
5.97 - int size() const {
5.98 - return num_items;
5.99 - }
5.100 -
5.101 -
5.102 - bool empty() const { return num_items==0; }
5.103 -
5.104 -
5.105 - void set (Item const it, PrioType const value) {
5.106 - int i=iimap[it];
5.107 - if ( i >= 0 && container[i].in ) {
5.108 - if ( comp(value, container[i].prio) ) decrease(it, value);
5.109 - if ( comp(container[i].prio, value) ) increase(it, value);
5.110 - } else push(it, value);
5.111 - }
5.112 -
5.113 -
5.114 - void push (Item const it, PrioType const value) {
5.115 - int i=iimap[it];
5.116 - if ( i < 0 ) {
5.117 - int s=container.size();
5.118 - iimap.set( it, s );
5.119 - store st;
5.120 - st.name=it;
5.121 - container.push_back(st);
5.122 - i=s;
5.123 - } else {
5.124 - container[i].parent=container[i].child=-1;
5.125 - container[i].degree=0;
5.126 - container[i].in=true;
5.127 - container[i].marked=false;
5.128 - }
5.129 -
5.130 - if ( num_items ) {
5.131 - container[container[minimum].right_neighbor].left_neighbor=i;
5.132 - container[i].right_neighbor=container[minimum].right_neighbor;
5.133 - container[minimum].right_neighbor=i;
5.134 - container[i].left_neighbor=minimum;
5.135 - if ( comp( value, container[minimum].prio) ) minimum=i;
5.136 - } else {
5.137 - container[i].right_neighbor=container[i].left_neighbor=i;
5.138 - minimum=i;
5.139 - }
5.140 - container[i].prio=value;
5.141 - ++num_items;
5.142 - }
5.143 -
5.144 -
5.145 - Item top() const {
5.146 - return container[minimum].name;
5.147 - }
5.148 -
5.149 -
5.150 - PrioType prio() const {
5.151 - return container[minimum].prio;
5.152 - }
5.153 -
5.154 -
5.155 -
5.156 -
5.157 - PrioType& operator[](const Item& it) {
5.158 - return container[iimap[it]].prio;
5.159 - }
5.160 -
5.161 - const PrioType& operator[](const Item& it) const {
5.162 - return container[iimap[it]].prio;
5.163 - }
5.164 -
5.165 -// const PrioType get(const Item& it) const {
5.166 -// return container[iimap[it]].prio;
5.167 -// }
5.168 -
5.169 - void pop() {
5.170 - /*The first case is that there are only one root.*/
5.171 - if ( container[minimum].left_neighbor==minimum ) {
5.172 - container[minimum].in=false;
5.173 - if ( container[minimum].degree!=0 ) {
5.174 - makeroot(container[minimum].child);
5.175 - minimum=container[minimum].child;
5.176 - balance();
5.177 - }
5.178 - } else {
5.179 - int right=container[minimum].right_neighbor;
5.180 - unlace(minimum);
5.181 - container[minimum].in=false;
5.182 - if ( container[minimum].degree > 0 ) {
5.183 - int left=container[minimum].left_neighbor;
5.184 - int child=container[minimum].child;
5.185 - int last_child=container[child].left_neighbor;
5.186 -
5.187 - makeroot(child);
5.188 -
5.189 - container[left].right_neighbor=child;
5.190 - container[child].left_neighbor=left;
5.191 - container[right].left_neighbor=last_child;
5.192 - container[last_child].right_neighbor=right;
5.193 - }
5.194 - minimum=right;
5.195 - balance();
5.196 - } // the case where there are more roots
5.197 - --num_items;
5.198 - }
5.199 -
5.200 -
5.201 - void erase (const Item& it) {
5.202 - int i=iimap[it];
5.203 -
5.204 - if ( i >= 0 && container[i].in ) {
5.205 - if ( container[i].parent!=-1 ) {
5.206 - int p=container[i].parent;
5.207 - cut(i,p);
5.208 - cascade(p);
5.209 - }
5.210 - minimum=i; //As if its prio would be -infinity
5.211 - pop();
5.212 - }
5.213 - }
5.214 -
5.215 -
5.216 - void decrease (Item it, PrioType const value) {
5.217 - int i=iimap[it];
5.218 - container[i].prio=value;
5.219 - int p=container[i].parent;
5.220 -
5.221 - if ( p!=-1 && comp(value, container[p].prio) ) {
5.222 - cut(i,p);
5.223 - cascade(p);
5.224 - }
5.225 - if ( comp(value, container[minimum].prio) ) minimum=i;
5.226 - }
5.227 -
5.228 -
5.229 - void increase (Item it, PrioType const value) {
5.230 - erase(it);
5.231 - push(it, value);
5.232 - }
5.233 -
5.234 -
5.235 - state_enum state(const Item &it) const {
5.236 - int i=iimap[it];
5.237 - if( i>=0 ) {
5.238 - if ( container[i].in ) i=0;
5.239 - else i=-2;
5.240 - }
5.241 - return state_enum(i);
5.242 - }
5.243 -
5.244 -
5.245 - private:
5.246 -
5.247 - void balance() {
5.248 -
5.249 - int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
5.250 -
5.251 - std::vector<int> A(maxdeg,-1);
5.252 -
5.253 - /*
5.254 - *Recall that now minimum does not point to the minimum prio element.
5.255 - *We set minimum to this during balance().
5.256 - */
5.257 - int anchor=container[minimum].left_neighbor;
5.258 - int next=minimum;
5.259 - bool end=false;
5.260 -
5.261 - do {
5.262 - int active=next;
5.263 - if ( anchor==active ) end=true;
5.264 - int d=container[active].degree;
5.265 - next=container[active].right_neighbor;
5.266 -
5.267 - while (A[d]!=-1) {
5.268 - if( comp(container[active].prio, container[A[d]].prio) ) {
5.269 - fuse(active,A[d]);
5.270 - } else {
5.271 - fuse(A[d],active);
5.272 - active=A[d];
5.273 - }
5.274 - A[d]=-1;
5.275 - ++d;
5.276 - }
5.277 - A[d]=active;
5.278 - } while ( !end );
5.279 -
5.280 -
5.281 - while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
5.282 - int s=minimum;
5.283 - int m=minimum;
5.284 - do {
5.285 - if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
5.286 - s=container[s].right_neighbor;
5.287 - } while ( s != m );
5.288 - }
5.289 -
5.290 -
5.291 - void makeroot (int c) {
5.292 - int s=c;
5.293 - do {
5.294 - container[s].parent=-1;
5.295 - s=container[s].right_neighbor;
5.296 - } while ( s != c );
5.297 - }
5.298 -
5.299 -
5.300 - void cut (int a, int b) {
5.301 - /*
5.302 - *Replacing a from the children of b.
5.303 - */
5.304 - --container[b].degree;
5.305 -
5.306 - if ( container[b].degree !=0 ) {
5.307 - int child=container[b].child;
5.308 - if ( child==a )
5.309 - container[b].child=container[child].right_neighbor;
5.310 - unlace(a);
5.311 - }
5.312 -
5.313 -
5.314 - /*Lacing a to the roots.*/
5.315 - int right=container[minimum].right_neighbor;
5.316 - container[minimum].right_neighbor=a;
5.317 - container[a].left_neighbor=minimum;
5.318 - container[a].right_neighbor=right;
5.319 - container[right].left_neighbor=a;
5.320 -
5.321 - container[a].parent=-1;
5.322 - container[a].marked=false;
5.323 - }
5.324 -
5.325 -
5.326 - void cascade (int a)
5.327 - {
5.328 - if ( container[a].parent!=-1 ) {
5.329 - int p=container[a].parent;
5.330 -
5.331 - if ( container[a].marked==false ) container[a].marked=true;
5.332 - else {
5.333 - cut(a,p);
5.334 - cascade(p);
5.335 - }
5.336 - }
5.337 - }
5.338 -
5.339 -
5.340 - void fuse (int a, int b) {
5.341 - unlace(b);
5.342 -
5.343 - /*Lacing b under a.*/
5.344 - container[b].parent=a;
5.345 -
5.346 - if (container[a].degree==0) {
5.347 - container[b].left_neighbor=b;
5.348 - container[b].right_neighbor=b;
5.349 - container[a].child=b;
5.350 - } else {
5.351 - int child=container[a].child;
5.352 - int last_child=container[child].left_neighbor;
5.353 - container[child].left_neighbor=b;
5.354 - container[b].right_neighbor=child;
5.355 - container[last_child].right_neighbor=b;
5.356 - container[b].left_neighbor=last_child;
5.357 - }
5.358 -
5.359 - ++container[a].degree;
5.360 -
5.361 - container[b].marked=false;
5.362 - }
5.363 -
5.364 -
5.365 - /*
5.366 - *It is invoked only if a has siblings.
5.367 - */
5.368 - void unlace (int a) {
5.369 - int leftn=container[a].left_neighbor;
5.370 - int rightn=container[a].right_neighbor;
5.371 - container[leftn].right_neighbor=rightn;
5.372 - container[rightn].left_neighbor=leftn;
5.373 - }
5.374 -
5.375 -
5.376 - class store {
5.377 - friend class FibHeap;
5.378 -
5.379 - Item name;
5.380 - int parent;
5.381 - int left_neighbor;
5.382 - int right_neighbor;
5.383 - int child;
5.384 - int degree;
5.385 - bool marked;
5.386 - bool in;
5.387 - PrioType prio;
5.388 -
5.389 - store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
5.390 - };
5.391 -
5.392 - };
5.393 -
5.394 -} //namespace hugo
5.395 -#endif