1.1 --- a/src/work/jacint/dijkstra.cc Thu Mar 11 11:03:22 2004 +0000
1.2 +++ b/src/work/jacint/dijkstra.cc Thu Mar 11 12:55:50 2004 +0000
1.3 @@ -21,17 +21,23 @@
1.4
1.5 double pre_time=currTime();
1.6 Dijkstra<ListGraph, int> dijkstra_test(G, s, cap);
1.7 + dijkstra_test.run();
1.8 double post_time=currTime();
1.9
1.10 std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
1.11
1.12 + int hiba=0;
1.13 EachEdgeIt e;
1.14 -
1.15 for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
1.16 NodeIt u=G.tail(e);
1.17 NodeIt v=G.head(e);
1.18 - assert ( dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap.get(e) );
1.19 + if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
1.20 + std::cout<<"Hiba: "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
1.21 + ++hiba;
1.22 + }
1.23 }
1.24
1.25 + std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.26 +
1.27 return 0;
1.28 }
2.1 --- a/src/work/jacint/dijkstra.h Thu Mar 11 11:03:22 2004 +0000
2.2 +++ b/src/work/jacint/dijkstra.h Thu Mar 11 12:55:50 2004 +0000
2.3 @@ -2,29 +2,24 @@
2.4 /*
2.5 *template <Graph, T, Heap=FibHeap>
2.6 *
2.7 - *
2.8 *Constructor:
2.9 *
2.10 *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
2.11 *
2.12 *
2.13 - *
2.14 *Member functions:
2.15 *
2.16 *void run()
2.17 *
2.18 * The following function should be used after run() was already run.
2.19 *
2.20 - *
2.21 *T dist(NodeIt v) : returns the distance from s to v.
2.22 * It is 0 if v is not reachable from s.
2.23 *
2.24 - *
2.25 *EdgeIt pred(NodeIt v) : returns the last edge
2.26 * of a shortest s-v path. Returns an invalid iterator
2.27 * if v=s or v is not reachable from s.
2.28 *
2.29 - *
2.30 *bool reach(NodeIt v) : true iff v is reachable from s
2.31 *
2.32 */
2.33 @@ -76,9 +71,9 @@
2.34
2.35 NodeIt v=heap.top();
2.36 T oldvalue=heap.get(v);
2.37 + heap.pop();
2.38 distance.set(v, oldvalue);
2.39 - heap.pop();
2.40 -
2.41 +
2.42 OutEdgeIt e;
2.43 for( G.getFirst(e,v); G.valid(e); G.next(e)) {
2.44 NodeIt w=G.bNode(e);
2.45 @@ -88,7 +83,6 @@
2.46 reached.set(w,true);
2.47 heap.push(w,oldvalue+length.get(e));
2.48 predecessor.set(w,e);
2.49 -
2.50 } else if ( oldvalue+length.get(e) < heap.get(w) ) {
2.51 predecessor.set(w,e);
2.52 heap.decrease(w, oldvalue+length.get(e));
2.53 @@ -114,9 +108,9 @@
2.54 bool reach(NodeIt v) {
2.55 return reached.get(v);
2.56 }
2.57 -
2.58 +
2.59 };
2.60 -
2.61 +
2.62 }
2.63
2.64 #endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/jacint/fib_heap.h Thu Mar 11 12:55:50 2004 +0000
3.3 @@ -0,0 +1,400 @@
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 + *
3.29 + *Prio prio() : returns the least Prio
3.30 + *
3.31 + *Prio get(Item) : returns Prio of Item
3.32 + *
3.33 + *void pop() : deletes the Item with least Prio
3.34 + *
3.35 + *void erase(Item) : deletes Item from the heap if it was already there
3.36 + *
3.37 + *void decrease(Item, P) : decreases prio of Item to P.
3.38 + * Item must be in the heap with prio at least P.
3.39 + *
3.40 + *void increase(Item, P) : sets prio of Item to P.
3.41 + *
3.42 + *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
3.43 + * heap until now, IN_HEAP if it is in the heap at the moment, and
3.44 + * POST_HEAP otherwise. In the latter case it is possible that Item
3.45 + * will get back to the heap again.
3.46 + *
3.47 + *In Fibonacci heaps, increase and erase are not efficient, in case of
3.48 + *many calls to these operations, it is better to use bin_heap.
3.49 + */
3.50 +
3.51 +#ifndef FIB_HEAP_H
3.52 +#define FIB_HEAP_H
3.53 +
3.54 +#include <vector>
3.55 +#include <functional>
3.56 +#include <math.h>
3.57 +
3.58 +namespace hugo {
3.59 +
3.60 + template <typename Item, typename Prio, typename ItemIntMap,
3.61 + typename Compare = std::less<Prio> >
3.62 +
3.63 + class FibHeap {
3.64 +
3.65 + typedef Prio PrioType;
3.66 +
3.67 + class store;
3.68 +
3.69 + std::vector<store> container;
3.70 + int minimum;
3.71 + bool blank;
3.72 + ItemIntMap &iimap;
3.73 + Compare comp;
3.74 +
3.75 + enum state_enum {
3.76 + IN_HEAP = 0,
3.77 + PRE_HEAP = -1,
3.78 + POST_HEAP = -2
3.79 + };
3.80 +
3.81 + public :
3.82 +
3.83 + FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {}
3.84 + FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
3.85 + blank(true), iimap(_iimap), comp(_comp) {}
3.86 +
3.87 +
3.88 + int size() const {
3.89 + int s=0;
3.90 + for ( unsigned int i=0; i!=container.size(); ++i )
3.91 + if ( container[i].in ) ++s;
3.92 + return s;
3.93 + }
3.94 +
3.95 +
3.96 + bool empty() const { return blank; }
3.97 +
3.98 +
3.99 + void set (Item const it, PrioType const value) {
3.100 + int i=iimap.get(it);
3.101 + if ( i >= 0 && container[i].in ) {
3.102 + if ( !comp(container[i].prio, value) ) decrease(it, value);
3.103 + if ( comp(container[i].prio, value) ) increase(it, value);
3.104 + } else push(it, value);
3.105 + }
3.106 +
3.107 +
3.108 + void push (Item const it, PrioType const value) {
3.109 + int i=iimap.get(it);
3.110 + if ( i < 0 ) {
3.111 + int s=container.size();
3.112 + iimap.set( it, s );
3.113 + store st;
3.114 + st.name=it;
3.115 + container.push_back(st);
3.116 + i=s;
3.117 + } else {
3.118 + container[i].parent=container[i].child=-1;
3.119 + container[i].degree=0;
3.120 + container[i].in=true;
3.121 + container[i].marked=false;
3.122 + }
3.123 +
3.124 + if ( !blank ) {
3.125 + container[container[minimum].right_neighbor].left_neighbor=i;
3.126 + container[i].right_neighbor=container[minimum].right_neighbor;
3.127 + container[minimum].right_neighbor=i;
3.128 + container[i].left_neighbor=minimum;
3.129 + if ( !comp( container[minimum].prio, value) ) minimum=i;
3.130 + } else {
3.131 + container[i].right_neighbor=container[i].left_neighbor=i;
3.132 + minimum=i;
3.133 + blank=false;
3.134 + }
3.135 + container[i].prio=value;
3.136 + }
3.137 +
3.138 +
3.139 + Item top() const {
3.140 + if ( !blank ) {
3.141 + return container[minimum].name;
3.142 + } else {
3.143 + return Item();
3.144 + }
3.145 + }
3.146 +
3.147 +
3.148 + PrioType prio() const {
3.149 + if ( !blank ) {
3.150 + return container[minimum].prio;
3.151 + } else {
3.152 + return PrioType();
3.153 + }
3.154 + }
3.155 +
3.156 +
3.157 + const PrioType get(const Item& it) const {
3.158 + int i=iimap.get(it);
3.159 +
3.160 + if ( i >= 0 && container[i].in ) {
3.161 + return container[i].prio;
3.162 + } else {
3.163 + return PrioType();
3.164 + }
3.165 + }
3.166 +
3.167 +
3.168 +
3.169 +
3.170 + void pop() {
3.171 + /*The first case is that there are only one root.*/
3.172 + if ( container[minimum].left_neighbor==minimum ) {
3.173 + container[minimum].in=false;
3.174 + if ( container[minimum].degree==0 ) blank=true;
3.175 + else {
3.176 + makeroot(container[minimum].child);
3.177 + minimum=container[minimum].child;
3.178 + balance();
3.179 + }
3.180 + } else {
3.181 + int right=container[minimum].right_neighbor;
3.182 + unlace(minimum);
3.183 + container[minimum].in=false;
3.184 + if ( container[minimum].degree > 0 ) {
3.185 + int left=container[minimum].left_neighbor;
3.186 + int child=container[minimum].child;
3.187 + int last_child=container[child].left_neighbor;
3.188 +
3.189 + makeroot(child);
3.190 +
3.191 + container[left].right_neighbor=child;
3.192 + container[child].left_neighbor=left;
3.193 + container[right].left_neighbor=last_child;
3.194 + container[last_child].right_neighbor=right;
3.195 + }
3.196 + minimum=right;
3.197 + balance();
3.198 + } // the case where there are more roots
3.199 + }
3.200 +
3.201 +
3.202 + void erase (const Item& it) {
3.203 + int i=iimap.get(it);
3.204 +
3.205 + if ( i >= 0 && container[i].in ) {
3.206 +
3.207 + if ( container[i].parent!=-1 ) {
3.208 + int p=container[i].parent;
3.209 + cut(i,p);
3.210 + cascade(p);
3.211 + minimum=i; //As if its prio would be -infinity
3.212 + }
3.213 + pop();
3.214 + }
3.215 + }
3.216 +
3.217 +
3.218 + void decrease (Item it, PrioType const value) {
3.219 + int i=iimap.get(it);
3.220 + container[i].prio=value;
3.221 + int p=container[i].parent;
3.222 +
3.223 + if ( p!=-1 && comp(value, container[p].prio) ) {
3.224 + cut(i,p);
3.225 + cascade(p);
3.226 + if ( comp(value, container[minimum].prio) ) minimum=i;
3.227 + }
3.228 + }
3.229 +
3.230 +
3.231 + void increase (Item it, PrioType const value) {
3.232 + erase(it);
3.233 + push(it, value);
3.234 + }
3.235 +
3.236 +
3.237 + state_enum state(const Item &it) const {
3.238 + int i=iimap.get(it);
3.239 + if( i>=0 ) {
3.240 + if ( container[i].in ) i=0;
3.241 + else i=-2;
3.242 + }
3.243 + return state_enum(i);
3.244 + }
3.245 +
3.246 +
3.247 + private:
3.248 +
3.249 + void balance() {
3.250 +
3.251 + int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
3.252 +
3.253 + std::vector<int> A(maxdeg,-1);
3.254 +
3.255 + /*
3.256 + *Recall that now minimum does not point to the minimum prio element.
3.257 + *We set minimum to this during balance().
3.258 + */
3.259 + int anchor=container[minimum].left_neighbor;
3.260 + int next=minimum;
3.261 + bool end=false;
3.262 +
3.263 + do {
3.264 + int active=next;
3.265 + if ( anchor==active ) end=true;
3.266 + int d=container[active].degree;
3.267 + next=container[active].right_neighbor;
3.268 +
3.269 + while (A[d]!=-1) {
3.270 + if( comp(container[active].prio, container[A[d]].prio) ) {
3.271 + fuse(active,A[d]);
3.272 + } else {
3.273 + fuse(A[d],active);
3.274 + active=A[d];
3.275 + }
3.276 + A[d]=-1;
3.277 + ++d;
3.278 + }
3.279 + A[d]=active;
3.280 + } while ( !end );
3.281 +
3.282 +
3.283 + while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
3.284 + int s=minimum;
3.285 + int m=minimum;
3.286 + do {
3.287 + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
3.288 + s=container[s].right_neighbor;
3.289 + } while ( s != m );
3.290 + }
3.291 +
3.292 +
3.293 + void makeroot (int c) {
3.294 + int s=c;
3.295 + do {
3.296 + container[s].parent=-1;
3.297 + s=container[s].right_neighbor;
3.298 + } while ( s != c );
3.299 + }
3.300 +
3.301 +
3.302 + void cut (int a, int b) {
3.303 + /*
3.304 + *Replacing a from the children of b.
3.305 + */
3.306 + --container[b].degree;
3.307 +
3.308 + if ( container[b].degree !=0 ) {
3.309 + int child=container[b].child;
3.310 + if ( child==a )
3.311 + container[b].child=container[child].right_neighbor;
3.312 + unlace(a);
3.313 + }
3.314 +
3.315 +
3.316 + /*Lacing i to the roots.*/
3.317 + int right=container[minimum].right_neighbor;
3.318 + container[minimum].right_neighbor=a;
3.319 + container[a].left_neighbor=minimum;
3.320 + container[a].right_neighbor=right;
3.321 + container[right].left_neighbor=a;
3.322 +
3.323 + container[a].parent=-1;
3.324 + container[a].marked=false;
3.325 + }
3.326 +
3.327 +
3.328 + void cascade (int a)
3.329 + {
3.330 + if ( container[a].parent!=-1 ) {
3.331 + int p=container[a].parent;
3.332 +
3.333 + if ( container[a].marked==false ) container[a].marked=true;
3.334 + else {
3.335 + cut(a,p);
3.336 + cascade(p);
3.337 + }
3.338 + }
3.339 + }
3.340 +
3.341 +
3.342 + void fuse (int a, int b) {
3.343 + unlace(b);
3.344 +
3.345 + /*Lacing b under a.*/
3.346 + container[b].parent=a;
3.347 +
3.348 + if (container[a].degree==0) {
3.349 + container[b].left_neighbor=b;
3.350 + container[b].right_neighbor=b;
3.351 + container[a].child=b;
3.352 + } else {
3.353 + int child=container[a].child;
3.354 + int last_child=container[child].left_neighbor;
3.355 + container[child].left_neighbor=b;
3.356 + container[b].right_neighbor=child;
3.357 + container[last_child].right_neighbor=b;
3.358 + container[b].left_neighbor=last_child;
3.359 + }
3.360 +
3.361 + ++container[a].degree;
3.362 +
3.363 + container[b].marked=false;
3.364 + }
3.365 +
3.366 +
3.367 + /*
3.368 + *It is invoked only if a has siblings.
3.369 + */
3.370 + void unlace (int a) {
3.371 + int leftn=container[a].left_neighbor;
3.372 + int rightn=container[a].right_neighbor;
3.373 + container[leftn].right_neighbor=rightn;
3.374 + container[rightn].left_neighbor=leftn;
3.375 + }
3.376 +
3.377 +
3.378 + class store {
3.379 + friend class FibHeap;
3.380 +
3.381 + Item name;
3.382 + int parent;
3.383 + int left_neighbor;
3.384 + int right_neighbor;
3.385 + int child;
3.386 + int degree;
3.387 + bool marked;
3.388 + bool in;
3.389 + PrioType prio;
3.390 +
3.391 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
3.392 + };
3.393 +
3.394 + };
3.395 +
3.396 +} //namespace hugo
3.397 +#endif
3.398 +
3.399 +
3.400 +
3.401 +
3.402 +
3.403 +