1.1 --- a/src/work/jacint/fib_heap.h Wed Mar 10 17:49:55 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,387 +0,0 @@
1.4 -// -*- C++ -*-
1.5 -/*
1.6 - *template <typename Item,
1.7 - * typename Prio,
1.8 - * typename ItemIntMap,
1.9 - * typename Compare = std::less<Prio> >
1.10 - *
1.11 - *constructors:
1.12 - *
1.13 - *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
1.14 - *
1.15 - *Member functions:
1.16 - *
1.17 - *int size() : returns the number of elements in the heap
1.18 - *
1.19 - *bool empty() : true iff size()=0
1.20 - *
1.21 - *void set(Item, Prio) : calls push(Item, Prio) if Item is not
1.22 - * in the heap, and calls decrease/increase(Item, Prio) otherwise
1.23 - *
1.24 - *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
1.25 - * mustn't be in the heap.
1.26 - *
1.27 - *Item top() : returns the Item with least Prio
1.28 - *
1.29 - *Prio prio() : returns the least Prio
1.30 - *
1.31 - *Prio get(Item) : returns Prio of Item
1.32 - *
1.33 - *void pop() : deletes the Item with least Prio
1.34 - *
1.35 - *void erase(Item) : deletes Item from the heap if it was already there
1.36 - *
1.37 - *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap
1.38 - * with prio at least P.
1.39 - *
1.40 - *void increase(Item, P) : sets prio of Item to P.
1.41 - *
1.42 - *
1.43 - *In Fibonacci heaps, increase and erase are not efficient, in case of
1.44 - *many calls to these operations, it is better to use bin_heap.
1.45 - */
1.46 -
1.47 -#ifndef FIB_HEAP_H
1.48 -#define FIB_HEAP_H
1.49 -
1.50 -#include <vector>
1.51 -#include <functional>
1.52 -#include <math.h>
1.53 -
1.54 -namespace hugo {
1.55 -
1.56 - template <typename Item, typename Prio, typename ItemIntMap,
1.57 - typename Compare = std::less<Prio> >
1.58 -
1.59 - class FibHeap {
1.60 -
1.61 - typedef Prio PrioType;
1.62 -
1.63 - class store;
1.64 -
1.65 - std::vector<store> container;
1.66 - int minimum;
1.67 - bool blank;
1.68 - ItemIntMap &iimap;
1.69 - Compare comp;
1.70 -
1.71 - public :
1.72 -
1.73 - FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {}
1.74 - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
1.75 - blank(true), iimap(_iimap), comp(_comp) {}
1.76 -
1.77 -
1.78 - int size() const {
1.79 - int s=0;
1.80 - for ( unsigned int i=0; i!=container.size(); ++i )
1.81 - if ( container[i].in ) ++s;
1.82 - return s;
1.83 - }
1.84 -
1.85 -
1.86 - bool empty() const { return blank; }
1.87 -
1.88 -
1.89 - void set (Item const it, PrioType const value) {
1.90 - int i=iimap.get(it);
1.91 - if ( i >= 0 && container[i].in ) {
1.92 - if ( !comp(container[i].prio, value) ) decrease(it, value);
1.93 - if ( comp(container[i].prio, value) ) increase(it, value);
1.94 - } else push(it, value);
1.95 - }
1.96 -
1.97 -
1.98 - void push (Item const it, PrioType const value) {
1.99 - int i=iimap.get(it);
1.100 - if ( i < 0 ) {
1.101 - int s=container.size();
1.102 - iimap.set( it, s );
1.103 - store st;
1.104 - st.name=it;
1.105 - container.push_back(st);
1.106 - i=s;
1.107 - }
1.108 -
1.109 - if ( !blank ) {
1.110 - container[container[minimum].right_neighbor].left_neighbor=i;
1.111 - container[i].right_neighbor=container[minimum].right_neighbor;
1.112 - container[minimum].right_neighbor=i;
1.113 - container[i].left_neighbor=minimum;
1.114 - if ( !comp( container[minimum].prio, value) ) minimum=i;
1.115 -
1.116 - } else {
1.117 - container[i].right_neighbor=container[i].left_neighbor=i;
1.118 - minimum=i;
1.119 - blank=false;
1.120 - }
1.121 - container[i].prio=value;
1.122 - }
1.123 -
1.124 -
1.125 -
1.126 - Item top() const {
1.127 - if ( !blank ) {
1.128 - return container[minimum].name;
1.129 - } else {
1.130 - return Item();
1.131 - }
1.132 - }
1.133 -
1.134 -
1.135 - PrioType prio() const {
1.136 - if ( !blank ) {
1.137 - return container[minimum].prio;
1.138 - } else {
1.139 - return PrioType();
1.140 - }
1.141 - }
1.142 -
1.143 -
1.144 - const PrioType get(const Item& it) const
1.145 - {
1.146 - int i=iimap.get(it);
1.147 -
1.148 - if ( i >= 0 && container[i].in ) {
1.149 - return container[i].prio;
1.150 - } else {
1.151 - return PrioType();
1.152 - }
1.153 - }
1.154 -
1.155 -
1.156 - void pop() {
1.157 - if ( !blank ) {
1.158 -
1.159 - /*The first case is that there are only one root.*/
1.160 - if ( container[minimum].left_neighbor==minimum ) {
1.161 - container[minimum].in=false;
1.162 - if ( container[minimum].degree==0 ) blank=true;
1.163 - else {
1.164 - makeroot(container[minimum].child);
1.165 - minimum=container[minimum].child;
1.166 - balance();
1.167 - }
1.168 - } else {
1.169 - int right=container[minimum].right_neighbor;
1.170 - unlace(minimum);
1.171 - container[minimum].in=false;
1.172 - if ( container[minimum].degree > 0 ) {
1.173 - int left=container[minimum].left_neighbor;
1.174 - int child=container[minimum].child;
1.175 - int last_child=container[child].left_neighbor;
1.176 -
1.177 - container[left].right_neighbor=child;
1.178 - container[child].left_neighbor=left;
1.179 - container[right].left_neighbor=last_child;
1.180 - container[last_child].right_neighbor=right;
1.181 -
1.182 - makeroot(child);
1.183 - }
1.184 - minimum=right;
1.185 - balance();
1.186 - } // the case where there are more roots
1.187 - }
1.188 - }
1.189 -
1.190 -
1.191 - void erase (const Item& it) {
1.192 - int i=iimap.get(it);
1.193 -
1.194 - if ( i >= 0 && container[i].in ) {
1.195 -
1.196 - if ( container[i].parent!=-1 ) {
1.197 - int p=container[i].parent;
1.198 - cut(i,p);
1.199 - cascade(p);
1.200 - minimum=i; //As if its prio would be -infinity
1.201 - }
1.202 - pop();
1.203 - }
1.204 - }
1.205 -
1.206 -
1.207 - void decrease (Item it, PrioType const value) {
1.208 - int i=iimap.get(it);
1.209 - container[i].prio=value;
1.210 - int p=container[i].parent;
1.211 -
1.212 - if ( p!=-1 && comp(value, container[p].prio) ) {
1.213 - cut(i,p);
1.214 - cascade(p);
1.215 - if ( comp(value, container[minimum].prio) ) minimum=i;
1.216 - }
1.217 - }
1.218 -
1.219 -
1.220 - void increase (Item it, PrioType const value) {
1.221 - erase(it);
1.222 - push(it, value);
1.223 - }
1.224 -
1.225 -
1.226 - private:
1.227 -
1.228 - void balance() {
1.229 - int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
1.230 -
1.231 - std::vector<int> A(maxdeg,-1);
1.232 -
1.233 - /*
1.234 - *Recall that now minimum does not point to the minimum prio element.
1.235 - *We set minimum to this during balance().
1.236 - */
1.237 - int anchor=container[minimum].left_neighbor;
1.238 - int next=minimum;
1.239 - bool end=false;
1.240 -
1.241 - do {
1.242 - int active=next;
1.243 - int d=container[active].degree;
1.244 - if ( anchor==active ) end=true;
1.245 - next = container[active].right_neighbor;
1.246 - if ( !comp(container[minimum].prio, container[active].prio) )
1.247 - minimum=active;
1.248 -
1.249 - while (A[d]!=-1) {
1.250 -
1.251 - if( comp(container[active].prio, container[A[d]].prio) ) {
1.252 - fuse(active,A[d]);
1.253 - } else {
1.254 - fuse(A[d],active);
1.255 - active=A[d];
1.256 - }
1.257 - A[d]=-1;
1.258 - ++d;
1.259 - }
1.260 -
1.261 - A[d]=active;
1.262 - } while ( !end );
1.263 - }
1.264 -
1.265 -
1.266 -
1.267 -
1.268 - /*
1.269 - *All the siblings of a are made roots.
1.270 - */
1.271 - void makeroot (int c)
1.272 - {
1.273 - int s=c;
1.274 - do {
1.275 - container[s].parent=-1;
1.276 - s=container[s].right_neighbor;
1.277 - } while ( s != c );
1.278 - }
1.279 -
1.280 -
1.281 - void cut (int a, int b)
1.282 - {
1.283 -
1.284 - /*
1.285 - *Replacing a from the children of b.
1.286 - */
1.287 - --container[b].degree;
1.288 -
1.289 - if ( container[b].degree !=0 ) {
1.290 - int child=container[b].child;
1.291 - if ( child==a )
1.292 - container[b].child=container[child].right_neighbor;
1.293 -
1.294 - unlace(a);
1.295 -
1.296 - }
1.297 -
1.298 -
1.299 - /*Lacing i to the roots.*/
1.300 - int right=container[minimum].right_neighbor;
1.301 - container[minimum].right_neighbor=a;
1.302 - container[a].left_neighbor=minimum;
1.303 - container[a].right_neighbor=right;
1.304 - container[right].left_neighbor=a;
1.305 -
1.306 - container[a].parent=-1;
1.307 - container[a].marked=false;
1.308 - }
1.309 -
1.310 -
1.311 - void cascade (int a)
1.312 - {
1.313 - if ( container[a].parent!=-1 ) {
1.314 - int p=container[a].parent;
1.315 -
1.316 - if ( container[a].marked==false ) container[a].marked=true;
1.317 - else {
1.318 - cut(a,p);
1.319 - cascade(p);
1.320 - }
1.321 - }
1.322 - }
1.323 -
1.324 -
1.325 - void fuse (int a, int b)
1.326 - {
1.327 -
1.328 - unlace(b);
1.329 -
1.330 -
1.331 - /*Lacing b under a.*/
1.332 - container[b].parent=a;
1.333 -
1.334 - if (container[a].degree==0) {
1.335 - container[b].left_neighbor=b;
1.336 - container[b].right_neighbor=b;
1.337 - container[a].child=b;
1.338 - } else {
1.339 - int child=container[a].child;
1.340 - int last_child=container[child].left_neighbor;
1.341 - container[child].left_neighbor=b;
1.342 - container[b].right_neighbor=child;
1.343 - container[last_child].right_neighbor=b;
1.344 - container[b].left_neighbor=last_child;
1.345 - }
1.346 -
1.347 - ++container[a].degree;
1.348 -
1.349 - container[b].marked=false;
1.350 - }
1.351 -
1.352 -
1.353 - /*
1.354 - *It is invoked only if a has siblings.
1.355 - */
1.356 -
1.357 - void unlace (int a) {
1.358 - int leftn=container[a].left_neighbor;
1.359 - int rightn=container[a].right_neighbor;
1.360 - container[leftn].right_neighbor=rightn;
1.361 - container[rightn].left_neighbor=leftn;
1.362 - }
1.363 -
1.364 -
1.365 - class store {
1.366 - friend class FibHeap;
1.367 -
1.368 - Item name;
1.369 - int parent;
1.370 - int left_neighbor;
1.371 - int right_neighbor;
1.372 - int child;
1.373 - int degree;
1.374 - bool marked;
1.375 - bool in;
1.376 - PrioType prio;
1.377 -
1.378 - store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
1.379 - };
1.380 -
1.381 - };
1.382 -
1.383 -} //namespace hugo
1.384 -#endif
1.385 -
1.386 -
1.387 -
1.388 -
1.389 -
1.390 -
2.1 --- a/src/work/jacint/makefile Wed Mar 10 17:49:55 2004 +0000
2.2 +++ b/src/work/jacint/makefile Thu Mar 11 11:03:22 2004 +0000
2.3 @@ -3,7 +3,7 @@
2.4 CXXFLAGS = -W -Wall -ansi -pedantic
2.5 LEDAROOT = /ledasrc/LEDA-4.1
2.6
2.7 -BINARIES = preflow dijkstra
2.8 +BINARIES = dijkstra
2.9
2.10 all: $(BINARIES)
2.11