1.1 --- a/lemon/fib_heap.h Thu Dec 20 15:21:22 2007 +0000
1.2 +++ b/lemon/fib_heap.h Thu Dec 27 13:40:16 2007 +0000
1.3 @@ -41,31 +41,34 @@
1.4 ///
1.5 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
1.6 ///heap. In case of many calls to these operations, it is better to use a
1.7 - ///\e binary \e heap.
1.8 + ///\ref BinHeap "binary heap".
1.9 ///
1.10 - ///\param Prio Type of the priority of the items.
1.11 - ///\param ItemIntMap A read and writable Item int map, used internally
1.12 + ///\param _Prio Type of the priority of the items.
1.13 + ///\param _ItemIntMap A read and writable Item int map, used internally
1.14 ///to handle the cross references.
1.15 - ///\param Compare A class for the ordering of the priorities. The
1.16 - ///default is \c std::less<Prio>.
1.17 + ///\param _Compare A class for the ordering of the priorities. The
1.18 + ///default is \c std::less<_Prio>.
1.19 ///
1.20 ///\sa BinHeap
1.21 ///\sa Dijkstra
1.22 ///\author Jacint Szabo
1.23
1.24 #ifdef DOXYGEN
1.25 - template <typename Prio,
1.26 - typename ItemIntMap,
1.27 - typename Compare>
1.28 + template <typename _Prio,
1.29 + typename _ItemIntMap,
1.30 + typename _Compare>
1.31 #else
1.32 - template <typename Prio,
1.33 - typename ItemIntMap,
1.34 - typename Compare = std::less<Prio> >
1.35 + template <typename _Prio,
1.36 + typename _ItemIntMap,
1.37 + typename _Compare = std::less<_Prio> >
1.38 #endif
1.39 class FibHeap {
1.40 public:
1.41 + typedef _ItemIntMap ItemIntMap;
1.42 + typedef _Prio Prio;
1.43 typedef typename ItemIntMap::Key Item;
1.44 - typedef Prio PrioType;
1.45 + typedef std::pair<Item,Prio> Pair;
1.46 + typedef _Compare Compare;
1.47
1.48 private:
1.49 class store;
1.50 @@ -78,7 +81,7 @@
1.51
1.52 public:
1.53 ///Status of the nodes
1.54 - enum state_enum {
1.55 + enum State {
1.56 ///The node is in the heap
1.57 IN_HEAP = 0,
1.58 ///The node has never been in the heap
1.59 @@ -99,8 +102,8 @@
1.60 /// \c _iimap should be given to the constructor, since it is used
1.61 /// internally to handle the cross references. \c _comp is an
1.62 /// object for ordering of the priorities.
1.63 - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
1.64 - iimap(_iimap), comp(_comp), num_items() {}
1.65 + FibHeap(ItemIntMap &_iimap, const Compare &_comp)
1.66 + : minimum(0), iimap(_iimap), comp(_comp), num_items() {}
1.67
1.68 /// \brief The number of items stored in the heap.
1.69 ///
1.70 @@ -128,163 +131,19 @@
1.71 /// This method calls \ref push(\c item, \c value) if \c item is not
1.72 /// stored in the heap and it calls \ref decrease(\c item, \c value) or
1.73 /// \ref increase(\c item, \c value) otherwise.
1.74 - void set (Item const item, PrioType const value);
1.75 + void set (const Item& item, const Prio& value) {
1.76 + int i=iimap[item];
1.77 + if ( i >= 0 && container[i].in ) {
1.78 + if ( comp(value, container[i].prio) ) decrease(item, value);
1.79 + if ( comp(container[i].prio, value) ) increase(item, value);
1.80 + } else push(item, value);
1.81 + }
1.82
1.83 /// \brief Adds \c item to the heap with priority \c value.
1.84 ///
1.85 /// Adds \c item to the heap with priority \c value.
1.86 /// \pre \c item must not be stored in the heap.
1.87 - void push (Item const item, PrioType const value);
1.88 -
1.89 - /// \brief Returns the item with minimum priority relative to \c Compare.
1.90 - ///
1.91 - /// This method returns the item with minimum priority relative to \c
1.92 - /// Compare.
1.93 - /// \pre The heap must be nonempty.
1.94 - Item top() const { return container[minimum].name; }
1.95 -
1.96 - /// \brief Returns the minimum priority relative to \c Compare.
1.97 - ///
1.98 - /// It returns the minimum priority relative to \c Compare.
1.99 - /// \pre The heap must be nonempty.
1.100 - PrioType prio() const { return container[minimum].prio; }
1.101 -
1.102 - /// \brief Returns the priority of \c item.
1.103 - ///
1.104 - /// This function returns the priority of \c item.
1.105 - /// \pre \c item must be in the heap.
1.106 - PrioType& operator[](const Item& item) {
1.107 - return container[iimap[item]].prio;
1.108 - }
1.109 -
1.110 - /// \brief Returns the priority of \c item.
1.111 - ///
1.112 - /// It returns the priority of \c item.
1.113 - /// \pre \c item must be in the heap.
1.114 - const PrioType& operator[](const Item& item) const {
1.115 - return container[iimap[item]].prio;
1.116 - }
1.117 -
1.118 -
1.119 - /// \brief Deletes the item with minimum priority relative to \c Compare.
1.120 - ///
1.121 - /// This method deletes the item with minimum priority relative to \c
1.122 - /// Compare from the heap.
1.123 - /// \pre The heap must be non-empty.
1.124 - void pop();
1.125 -
1.126 - /// \brief Deletes \c item from the heap.
1.127 - ///
1.128 - /// This method deletes \c item from the heap, if \c item was already
1.129 - /// stored in the heap. It is quite inefficient in Fibonacci heaps.
1.130 - void erase (const Item& item);
1.131 -
1.132 - /// \brief Decreases the priority of \c item to \c value.
1.133 - ///
1.134 - /// This method decreases the priority of \c item to \c value.
1.135 - /// \pre \c item must be stored in the heap with priority at least \c
1.136 - /// value relative to \c Compare.
1.137 - void decrease (Item item, PrioType const value);
1.138 -
1.139 - /// \brief Increases the priority of \c item to \c value.
1.140 - ///
1.141 - /// This method sets the priority of \c item to \c value. Though
1.142 - /// there is no precondition on the priority of \c item, this
1.143 - /// method should be used only if it is indeed necessary to increase
1.144 - /// (relative to \c Compare) the priority of \c item, because this
1.145 - /// method is inefficient.
1.146 - void increase (Item item, PrioType const value) {
1.147 - erase(item);
1.148 - push(item, value);
1.149 - }
1.150 -
1.151 -
1.152 - /// \brief Returns if \c item is in, has already been in, or has never
1.153 - /// been in the heap.
1.154 - ///
1.155 - /// This method returns PRE_HEAP if \c item has never been in the
1.156 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.157 - /// otherwise. In the latter case it is possible that \c item will
1.158 - /// get back to the heap again.
1.159 - state_enum state(const Item &item) const {
1.160 - int i=iimap[item];
1.161 - if( i>=0 ) {
1.162 - if ( container[i].in ) i=0;
1.163 - else i=-2;
1.164 - }
1.165 - return state_enum(i);
1.166 - }
1.167 -
1.168 - /// \brief Sets the state of the \c item in the heap.
1.169 - ///
1.170 - /// Sets the state of the \c item in the heap. It can be used to
1.171 - /// manually clear the heap when it is important to achive the
1.172 - /// better time complexity.
1.173 - /// \param i The item.
1.174 - /// \param st The state. It should not be \c IN_HEAP.
1.175 - void state(const Item& i, state_enum st) {
1.176 - switch (st) {
1.177 - case POST_HEAP:
1.178 - case PRE_HEAP:
1.179 - if (state(i) == IN_HEAP) {
1.180 - erase(i);
1.181 - }
1.182 - iimap[i] = st;
1.183 - break;
1.184 - case IN_HEAP:
1.185 - break;
1.186 - }
1.187 - }
1.188 -
1.189 - private:
1.190 -
1.191 - void balance();
1.192 - void makeroot(int c);
1.193 - void cut(int a, int b);
1.194 - void cascade(int a);
1.195 - void fuse(int a, int b);
1.196 - void unlace(int a);
1.197 -
1.198 -
1.199 - class store {
1.200 - friend class FibHeap;
1.201 -
1.202 - Item name;
1.203 - int parent;
1.204 - int left_neighbor;
1.205 - int right_neighbor;
1.206 - int child;
1.207 - int degree;
1.208 - bool marked;
1.209 - bool in;
1.210 - PrioType prio;
1.211 -
1.212 - store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
1.213 - };
1.214 - };
1.215 -
1.216 -
1.217 -
1.218 - // **********************************************************************
1.219 - // IMPLEMENTATIONS
1.220 - // **********************************************************************
1.221 -
1.222 - template <typename Prio, typename ItemIntMap,
1.223 - typename Compare>
1.224 - void FibHeap<Prio, ItemIntMap, Compare>::set
1.225 - (Item const item, PrioType const value)
1.226 - {
1.227 - int i=iimap[item];
1.228 - if ( i >= 0 && container[i].in ) {
1.229 - if ( comp(value, container[i].prio) ) decrease(item, value);
1.230 - if ( comp(container[i].prio, value) ) increase(item, value);
1.231 - } else push(item, value);
1.232 - }
1.233 -
1.234 - template <typename Prio, typename ItemIntMap,
1.235 - typename Compare>
1.236 - void FibHeap<Prio, ItemIntMap, Compare>::push
1.237 - (Item const item, PrioType const value) {
1.238 + void push (const Item& item, const Prio& value) {
1.239 int i=iimap[item];
1.240 if ( i < 0 ) {
1.241 int s=container.size();
1.242 @@ -314,9 +173,33 @@
1.243 ++num_items;
1.244 }
1.245
1.246 - template <typename Prio, typename ItemIntMap,
1.247 - typename Compare>
1.248 - void FibHeap<Prio, ItemIntMap, Compare>::pop() {
1.249 + /// \brief Returns the item with minimum priority relative to \c Compare.
1.250 + ///
1.251 + /// This method returns the item with minimum priority relative to \c
1.252 + /// Compare.
1.253 + /// \pre The heap must be nonempty.
1.254 + Item top() const { return container[minimum].name; }
1.255 +
1.256 + /// \brief Returns the minimum priority relative to \c Compare.
1.257 + ///
1.258 + /// It returns the minimum priority relative to \c Compare.
1.259 + /// \pre The heap must be nonempty.
1.260 + const Prio& prio() const { return container[minimum].prio; }
1.261 +
1.262 + /// \brief Returns the priority of \c item.
1.263 + ///
1.264 + /// It returns the priority of \c item.
1.265 + /// \pre \c item must be in the heap.
1.266 + const Prio& operator[](const Item& item) const {
1.267 + return container[iimap[item]].prio;
1.268 + }
1.269 +
1.270 + /// \brief Deletes the item with minimum priority relative to \c Compare.
1.271 + ///
1.272 + /// This method deletes the item with minimum priority relative to \c
1.273 + /// Compare from the heap.
1.274 + /// \pre The heap must be non-empty.
1.275 + void pop() {
1.276 /*The first case is that there are only one root.*/
1.277 if ( container[minimum].left_neighbor==minimum ) {
1.278 container[minimum].in=false;
1.279 @@ -333,7 +216,7 @@
1.280 int left=container[minimum].left_neighbor;
1.281 int child=container[minimum].child;
1.282 int last_child=container[child].left_neighbor;
1.283 -
1.284 +
1.285 makeroot(child);
1.286
1.287 container[left].right_neighbor=child;
1.288 @@ -347,11 +230,11 @@
1.289 --num_items;
1.290 }
1.291
1.292 -
1.293 - template <typename Prio, typename ItemIntMap,
1.294 - typename Compare>
1.295 - void FibHeap<Prio, ItemIntMap, Compare>::erase
1.296 - (const Item& item) {
1.297 + /// \brief Deletes \c item from the heap.
1.298 + ///
1.299 + /// This method deletes \c item from the heap, if \c item was already
1.300 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
1.301 + void erase (const Item& item) {
1.302 int i=iimap[item];
1.303
1.304 if ( i >= 0 && container[i].in ) {
1.305 @@ -363,12 +246,14 @@
1.306 minimum=i; //As if its prio would be -infinity
1.307 pop();
1.308 }
1.309 - }
1.310 -
1.311 - template <typename Prio, typename ItemIntMap,
1.312 - typename Compare>
1.313 - void FibHeap<Prio, ItemIntMap, Compare>::decrease
1.314 - (Item item, PrioType const value) {
1.315 + }
1.316 +
1.317 + /// \brief Decreases the priority of \c item to \c value.
1.318 + ///
1.319 + /// This method decreases the priority of \c item to \c value.
1.320 + /// \pre \c item must be stored in the heap with priority at least \c
1.321 + /// value relative to \c Compare.
1.322 + void decrease (Item item, const Prio& value) {
1.323 int i=iimap[item];
1.324 container[i].prio=value;
1.325 int p=container[i].parent;
1.326 @@ -378,26 +263,75 @@
1.327 cascade(p);
1.328 }
1.329 if ( comp(value, container[minimum].prio) ) minimum=i;
1.330 - }
1.331 -
1.332 + }
1.333
1.334 - template <typename Prio, typename ItemIntMap,
1.335 - typename Compare>
1.336 - void FibHeap<Prio, ItemIntMap, Compare>::balance() {
1.337 + /// \brief Increases the priority of \c item to \c value.
1.338 + ///
1.339 + /// This method sets the priority of \c item to \c value. Though
1.340 + /// there is no precondition on the priority of \c item, this
1.341 + /// method should be used only if it is indeed necessary to increase
1.342 + /// (relative to \c Compare) the priority of \c item, because this
1.343 + /// method is inefficient.
1.344 + void increase (Item item, const Prio& value) {
1.345 + erase(item);
1.346 + push(item, value);
1.347 + }
1.348
1.349 - int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
1.350 +
1.351 + /// \brief Returns if \c item is in, has already been in, or has never
1.352 + /// been in the heap.
1.353 + ///
1.354 + /// This method returns PRE_HEAP if \c item has never been in the
1.355 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.356 + /// otherwise. In the latter case it is possible that \c item will
1.357 + /// get back to the heap again.
1.358 + State state(const Item &item) const {
1.359 + int i=iimap[item];
1.360 + if( i>=0 ) {
1.361 + if ( container[i].in ) i=0;
1.362 + else i=-2;
1.363 + }
1.364 + return State(i);
1.365 + }
1.366 +
1.367 + /// \brief Sets the state of the \c item in the heap.
1.368 + ///
1.369 + /// Sets the state of the \c item in the heap. It can be used to
1.370 + /// manually clear the heap when it is important to achive the
1.371 + /// better time complexity.
1.372 + /// \param i The item.
1.373 + /// \param st The state. It should not be \c IN_HEAP.
1.374 + void state(const Item& i, State st) {
1.375 + switch (st) {
1.376 + case POST_HEAP:
1.377 + case PRE_HEAP:
1.378 + if (state(i) == IN_HEAP) {
1.379 + erase(i);
1.380 + }
1.381 + iimap[i] = st;
1.382 + break;
1.383 + case IN_HEAP:
1.384 + break;
1.385 + }
1.386 + }
1.387 +
1.388 + private:
1.389 +
1.390 + void balance() {
1.391 +
1.392 + int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
1.393
1.394 - std::vector<int> A(maxdeg,-1);
1.395 + std::vector<int> A(maxdeg,-1);
1.396
1.397 - /*
1.398 - *Recall that now minimum does not point to the minimum prio element.
1.399 - *We set minimum to this during balance().
1.400 - */
1.401 - int anchor=container[minimum].left_neighbor;
1.402 - int next=minimum;
1.403 - bool end=false;
1.404 + /*
1.405 + *Recall that now minimum does not point to the minimum prio element.
1.406 + *We set minimum to this during balance().
1.407 + */
1.408 + int anchor=container[minimum].left_neighbor;
1.409 + int next=minimum;
1.410 + bool end=false;
1.411
1.412 - do {
1.413 + do {
1.414 int active=next;
1.415 if ( anchor==active ) end=true;
1.416 int d=container[active].degree;
1.417 @@ -414,64 +348,53 @@
1.418 ++d;
1.419 }
1.420 A[d]=active;
1.421 - } while ( !end );
1.422 + } while ( !end );
1.423
1.424
1.425 - while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
1.426 - int s=minimum;
1.427 - int m=minimum;
1.428 - do {
1.429 - if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
1.430 - s=container[s].right_neighbor;
1.431 - } while ( s != m );
1.432 + while ( container[minimum].parent >=0 )
1.433 + minimum=container[minimum].parent;
1.434 + int s=minimum;
1.435 + int m=minimum;
1.436 + do {
1.437 + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
1.438 + s=container[s].right_neighbor;
1.439 + } while ( s != m );
1.440 }
1.441
1.442 - template <typename Prio, typename ItemIntMap,
1.443 - typename Compare>
1.444 - void FibHeap<Prio, ItemIntMap, Compare>::makeroot
1.445 - (int c) {
1.446 + void makeroot(int c) {
1.447 int s=c;
1.448 do {
1.449 container[s].parent=-1;
1.450 s=container[s].right_neighbor;
1.451 } while ( s != c );
1.452 }
1.453 -
1.454 -
1.455 - template <typename Prio, typename ItemIntMap,
1.456 - typename Compare>
1.457 - void FibHeap<Prio, ItemIntMap, Compare>::cut
1.458 - (int a, int b) {
1.459 - /*
1.460 - *Replacing a from the children of b.
1.461 - */
1.462 - --container[b].degree;
1.463 +
1.464 + void cut(int a, int b) {
1.465 + /*
1.466 + *Replacing a from the children of b.
1.467 + */
1.468 + --container[b].degree;
1.469
1.470 - if ( container[b].degree !=0 ) {
1.471 - int child=container[b].child;
1.472 - if ( child==a )
1.473 - container[b].child=container[child].right_neighbor;
1.474 - unlace(a);
1.475 + if ( container[b].degree !=0 ) {
1.476 + int child=container[b].child;
1.477 + if ( child==a )
1.478 + container[b].child=container[child].right_neighbor;
1.479 + unlace(a);
1.480 + }
1.481 +
1.482 +
1.483 + /*Lacing a to the roots.*/
1.484 + int right=container[minimum].right_neighbor;
1.485 + container[minimum].right_neighbor=a;
1.486 + container[a].left_neighbor=minimum;
1.487 + container[a].right_neighbor=right;
1.488 + container[right].left_neighbor=a;
1.489 +
1.490 + container[a].parent=-1;
1.491 + container[a].marked=false;
1.492 }
1.493 -
1.494 -
1.495 - /*Lacing a to the roots.*/
1.496 - int right=container[minimum].right_neighbor;
1.497 - container[minimum].right_neighbor=a;
1.498 - container[a].left_neighbor=minimum;
1.499 - container[a].right_neighbor=right;
1.500 - container[right].left_neighbor=a;
1.501 -
1.502 - container[a].parent=-1;
1.503 - container[a].marked=false;
1.504 - }
1.505 -
1.506
1.507 - template <typename Prio, typename ItemIntMap,
1.508 - typename Compare>
1.509 - void FibHeap<Prio, ItemIntMap, Compare>::cascade
1.510 - (int a)
1.511 - {
1.512 + void cascade(int a) {
1.513 if ( container[a].parent!=-1 ) {
1.514 int p=container[a].parent;
1.515
1.516 @@ -483,11 +406,7 @@
1.517 }
1.518 }
1.519
1.520 -
1.521 - template <typename Prio, typename ItemIntMap,
1.522 - typename Compare>
1.523 - void FibHeap<Prio, ItemIntMap, Compare>::fuse
1.524 - (int a, int b) {
1.525 + void fuse(int a, int b) {
1.526 unlace(b);
1.527
1.528 /*Lacing b under a.*/
1.529 @@ -511,20 +430,33 @@
1.530 container[b].marked=false;
1.531 }
1.532
1.533 -
1.534 - /*
1.535 - *It is invoked only if a has siblings.
1.536 - */
1.537 - template <typename Prio, typename ItemIntMap,
1.538 - typename Compare>
1.539 - void FibHeap<Prio, ItemIntMap, Compare>::unlace
1.540 - (int a) {
1.541 + /*
1.542 + *It is invoked only if a has siblings.
1.543 + */
1.544 + void unlace(int a) {
1.545 int leftn=container[a].left_neighbor;
1.546 int rightn=container[a].right_neighbor;
1.547 container[leftn].right_neighbor=rightn;
1.548 container[rightn].left_neighbor=leftn;
1.549 - }
1.550 -
1.551 + }
1.552 +
1.553 +
1.554 + class store {
1.555 + friend class FibHeap;
1.556 +
1.557 + Item name;
1.558 + int parent;
1.559 + int left_neighbor;
1.560 + int right_neighbor;
1.561 + int child;
1.562 + int degree;
1.563 + bool marked;
1.564 + bool in;
1.565 + Prio prio;
1.566 +
1.567 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
1.568 + };
1.569 + };
1.570
1.571 } //namespace lemon
1.572