Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

fib_heap.h

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

Generated on Sat Mar 19 10:58:39 2005 for LEMON by  doxygen 1.4.1