fib_heap.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_FIB_HEAP_H
00020 #define LEMON_FIB_HEAP_H
00021 
00025 
00026 #include <vector>
00027 #include <functional>
00028 #include <cmath>
00029 
00030 namespace lemon {
00031   
00033 
00035 
00056  
00057 #ifdef DOXYGEN
00058   template <typename Item, 
00059             typename Prio, 
00060             typename ItemIntMap, 
00061             typename Compare>
00062 #else
00063   template <typename Item, 
00064             typename Prio, 
00065             typename ItemIntMap, 
00066             typename Compare = std::less<Prio> >
00067 #endif
00068   class FibHeap {
00069   public:     
00070     typedef Prio PrioType;
00071     
00072   private:
00073     class store;
00074     
00075     std::vector<store> container;
00076     int minimum;
00077     ItemIntMap &iimap;
00078     Compare comp;
00079     int num_items;
00080     
00081   public:
00083     enum state_enum {
00085       IN_HEAP = 0,
00087       PRE_HEAP = -1,
00089       POST_HEAP = -2
00090     };
00091     
00096     explicit FibHeap(ItemIntMap &_iimap) 
00097       : minimum(0), iimap(_iimap), num_items() {} 
00098  
00104     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
00105                   iimap(_iimap), comp(_comp), num_items() {}
00106     
00110     int size() const { return num_items; }
00111 
00115     bool empty() const { return num_items==0; }
00116 
00120     void clear() {
00121       if (num_items != 0) {
00122         for (int i = 0; i < (int)container.size(); ++i) {
00123           iimap[container[i].name] = -2;
00124         }
00125       }
00126       container.clear(); minimum = 0; num_items = 0;
00127     }
00128 
00135     void set (Item const item, PrioType const value); 
00136     
00141     void push (Item const item, PrioType const value);
00142     
00148     Item top() const { return container[minimum].name; }
00149 
00154     PrioType prio() const { return container[minimum].prio; }
00155     
00160     PrioType& operator[](const Item& item) { 
00161       return container[iimap[item]].prio; 
00162     }
00163     
00168     const PrioType& operator[](const Item& item) const { 
00169       return container[iimap[item]].prio; 
00170     }
00171 
00172 
00178     void pop();
00179 
00184     void erase (const Item& item); 
00185 
00191     void decrease (Item item, PrioType const value); 
00192 
00200     void increase (Item item, PrioType const value) {
00201       erase(item);
00202       push(item, value);
00203     }
00204 
00205 
00213     state_enum state(const Item &item) const {
00214       int i=iimap[item];
00215       if( i>=0 ) {
00216         if ( container[i].in ) i=0;
00217         else i=-2; 
00218       }
00219       return state_enum(i);
00220     }    
00221 
00229     void state(const Item& i, state_enum st) {
00230       switch (st) {
00231       case POST_HEAP:
00232       case PRE_HEAP:
00233         if (state(i) == IN_HEAP) {
00234           erase(i);
00235         }
00236         iimap[i] = st;
00237         break;
00238       case IN_HEAP:
00239         break;
00240       }
00241     }
00242     
00243   private:
00244     
00245     void balance();
00246     void makeroot(int c);
00247     void cut(int a, int b);
00248     void cascade(int a);
00249     void fuse(int a, int b);
00250     void unlace(int a);
00251 
00252 
00253     class store {
00254       friend class FibHeap;
00255       
00256       Item name;
00257       int parent;
00258       int left_neighbor;
00259       int right_neighbor;
00260       int child;
00261       int degree;  
00262       bool marked;
00263       bool in;
00264       PrioType prio;
00265       
00266       store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
00267     };
00268   };    
00269  
00270 
00271 
00272     // **********************************************************************
00273     //  IMPLEMENTATIONS
00274     // **********************************************************************
00275     
00276   template <typename Item, typename Prio, typename ItemIntMap, 
00277     typename Compare>
00278   void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
00279   (Item const item, PrioType const value) 
00280   {
00281     int i=iimap[item];
00282     if ( i >= 0 && container[i].in ) {
00283       if ( comp(value, container[i].prio) ) decrease(item, value); 
00284       if ( comp(container[i].prio, value) ) increase(item, value); 
00285     } else push(item, value);
00286   }
00287     
00288   template <typename Item, typename Prio, typename ItemIntMap, 
00289     typename Compare>
00290   void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
00291   (Item const item, PrioType const value) {
00292       int i=iimap[item];      
00293       if ( i < 0 ) {
00294         int s=container.size();
00295         iimap.set( item, s );   
00296         store st;
00297         st.name=item;
00298         container.push_back(st);
00299         i=s;
00300       } else {
00301         container[i].parent=container[i].child=-1;
00302         container[i].degree=0;
00303         container[i].in=true;
00304         container[i].marked=false;
00305       }
00306 
00307       if ( num_items ) {
00308         container[container[minimum].right_neighbor].left_neighbor=i;
00309         container[i].right_neighbor=container[minimum].right_neighbor;
00310         container[minimum].right_neighbor=i;
00311         container[i].left_neighbor=minimum;
00312         if ( comp( value, container[minimum].prio) ) minimum=i; 
00313       } else {
00314         container[i].right_neighbor=container[i].left_neighbor=i;
00315         minimum=i;      
00316       }
00317       container[i].prio=value;
00318       ++num_items;
00319     }
00320     
00321   template <typename Item, typename Prio, typename ItemIntMap, 
00322     typename Compare>
00323   void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
00324       /*The first case is that there are only one root.*/
00325       if ( container[minimum].left_neighbor==minimum ) {
00326         container[minimum].in=false;
00327         if ( container[minimum].degree!=0 ) { 
00328           makeroot(container[minimum].child);
00329           minimum=container[minimum].child;
00330           balance();
00331         }
00332       } else {
00333         int right=container[minimum].right_neighbor;
00334         unlace(minimum);
00335         container[minimum].in=false;
00336         if ( container[minimum].degree > 0 ) {
00337           int left=container[minimum].left_neighbor;
00338           int child=container[minimum].child;
00339           int last_child=container[child].left_neighbor;
00340         
00341           makeroot(child);
00342           
00343           container[left].right_neighbor=child;
00344           container[child].left_neighbor=left;
00345           container[right].left_neighbor=last_child;
00346           container[last_child].right_neighbor=right;
00347         }
00348         minimum=right;
00349         balance();
00350       } // the case where there are more roots
00351       --num_items;   
00352     }
00353 
00354 
00355   template <typename Item, typename Prio, typename ItemIntMap, 
00356     typename Compare>
00357   void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
00358   (const Item& item) {
00359       int i=iimap[item];
00360       
00361       if ( i >= 0 && container[i].in ) {        
00362         if ( container[i].parent!=-1 ) {
00363           int p=container[i].parent;
00364           cut(i,p);         
00365           cascade(p);
00366         }
00367         minimum=i;     //As if its prio would be -infinity
00368         pop();
00369       }
00370   }
00371     
00372   template <typename Item, typename Prio, typename ItemIntMap, 
00373     typename Compare>
00374   void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
00375   (Item item, PrioType const value) {
00376       int i=iimap[item];
00377       container[i].prio=value;
00378       int p=container[i].parent;
00379       
00380       if ( p!=-1 && comp(value, container[p].prio) ) {
00381         cut(i,p);           
00382         cascade(p);
00383       }      
00384       if ( comp(value, container[minimum].prio) ) minimum=i; 
00385   }
00386  
00387 
00388   template <typename Item, typename Prio, typename ItemIntMap, 
00389     typename Compare>
00390   void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
00391 
00392     int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
00393   
00394     std::vector<int> A(maxdeg,-1); 
00395     
00396     /*
00397      *Recall that now minimum does not point to the minimum prio element.
00398      *We set minimum to this during balance().
00399      */
00400     int anchor=container[minimum].left_neighbor; 
00401     int next=minimum; 
00402     bool end=false; 
00403         
00404        do {
00405         int active=next;
00406         if ( anchor==active ) end=true;
00407         int d=container[active].degree;
00408         next=container[active].right_neighbor;
00409 
00410         while (A[d]!=-1) {        
00411           if( comp(container[active].prio, container[A[d]].prio) ) {
00412             fuse(active,A[d]); 
00413           } else { 
00414             fuse(A[d],active);
00415             active=A[d];
00416           } 
00417           A[d]=-1;
00418           ++d;
00419         }       
00420         A[d]=active;
00421        } while ( !end );
00422 
00423 
00424        while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
00425        int s=minimum;
00426        int m=minimum;
00427        do {  
00428          if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
00429          s=container[s].right_neighbor;
00430        } while ( s != m );
00431     }
00432 
00433   template <typename Item, typename Prio, typename ItemIntMap, 
00434     typename Compare>
00435   void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
00436   (int c) {
00437       int s=c;
00438       do {  
00439         container[s].parent=-1;
00440         s=container[s].right_neighbor;
00441       } while ( s != c );
00442     }
00443   
00444   
00445   template <typename Item, typename Prio, typename ItemIntMap, 
00446     typename Compare>
00447   void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
00448   (int a, int b) {    
00449     /*
00450      *Replacing a from the children of b.
00451      */
00452     --container[b].degree;
00453     
00454     if ( container[b].degree !=0 ) {
00455       int child=container[b].child;
00456       if ( child==a ) 
00457         container[b].child=container[child].right_neighbor;
00458       unlace(a);
00459     }
00460     
00461     
00462     /*Lacing a to the roots.*/
00463     int right=container[minimum].right_neighbor;
00464     container[minimum].right_neighbor=a;
00465     container[a].left_neighbor=minimum;
00466     container[a].right_neighbor=right;
00467     container[right].left_neighbor=a;
00468     
00469     container[a].parent=-1;
00470     container[a].marked=false;
00471   }
00472   
00473 
00474   template <typename Item, typename Prio, typename ItemIntMap, 
00475     typename Compare>
00476   void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
00477   (int a) 
00478     {
00479       if ( container[a].parent!=-1 ) {
00480         int p=container[a].parent;
00481         
00482         if ( container[a].marked==false ) container[a].marked=true;
00483         else {
00484           cut(a,p);
00485           cascade(p);
00486         }
00487       }
00488     }
00489 
00490 
00491   template <typename Item, typename Prio, typename ItemIntMap, 
00492     typename Compare>
00493   void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
00494   (int a, int b) {
00495       unlace(b);
00496       
00497       /*Lacing b under a.*/
00498       container[b].parent=a;
00499 
00500       if (container[a].degree==0) {
00501         container[b].left_neighbor=b;
00502         container[b].right_neighbor=b;
00503         container[a].child=b;   
00504       } else {
00505         int child=container[a].child;
00506         int last_child=container[child].left_neighbor;
00507         container[child].left_neighbor=b;
00508         container[b].right_neighbor=child;
00509         container[last_child].right_neighbor=b;
00510         container[b].left_neighbor=last_child;
00511       }
00512 
00513       ++container[a].degree;
00514       
00515       container[b].marked=false;
00516     }
00517 
00518   
00519   /*
00520    *It is invoked only if a has siblings.
00521    */
00522   template <typename Item, typename Prio, typename ItemIntMap, 
00523     typename Compare>
00524   void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
00525   (int a) {      
00526       int leftn=container[a].left_neighbor;
00527       int rightn=container[a].right_neighbor;
00528       container[leftn].right_neighbor=rightn;
00529       container[rightn].left_neighbor=leftn;
00530   }
00531   
00532 
00533 } //namespace lemon
00534 
00535 #endif //LEMON_FIB_HEAP_H
00536 

Generated on Fri Feb 3 18:36:50 2006 for LEMON by  doxygen 1.4.6