lemon/fib_heap.h
author alpar
Fri, 19 Aug 2005 12:09:21 +0000
changeset 1644 62548b317e65
parent 1359 1581f961cfaa
child 1717 75fe24093ded
permissions -rw-r--r--
Put an end to every gcc-4.0 warning.
     1 /* -*- C++ -*-
     2  * lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_FIB_HEAP_H
    18 #define LEMON_FIB_HEAP_H
    19 
    20 ///\file
    21 ///\ingroup auxdat
    22 ///\brief Fibonacci Heap implementation.
    23 
    24 #include <vector>
    25 #include <functional>
    26 #include <cmath>
    27 
    28 namespace lemon {
    29   
    30   /// \addtogroup auxdat
    31   /// @{
    32 
    33   /// Fibonacci Heap.
    34 
    35   ///This class implements the \e Fibonacci \e heap data structure. A \e heap
    36   ///is a data structure for storing items with specified values called \e
    37   ///priorities in such a way that finding the item with minimum priority is
    38   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    39   ///one can change the priority of an item, add or erase an item, etc.
    40   ///
    41   ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
    42   ///heap. In case of many calls to these operations, it is better to use a
    43   ///\e binary \e heap.
    44   ///
    45   ///\param Item Type of the items to be stored.  
    46   ///\param Prio Type of the priority of the items.
    47   ///\param ItemIntMap A read and writable Item int map, used internally
    48   ///to handle the cross references.
    49   ///\param Compare A class for the ordering of the priorities. The
    50   ///default is \c std::less<Prio>.
    51   ///
    52   ///\sa BinHeap
    53   ///\sa Dijkstra
    54   ///\author Jacint Szabo 
    55  
    56 #ifdef DOXYGEN
    57   template <typename Item, 
    58 	    typename Prio, 
    59 	    typename ItemIntMap, 
    60 	    typename Compare>
    61 #else
    62   template <typename Item, 
    63 	    typename Prio, 
    64 	    typename ItemIntMap, 
    65 	    typename Compare = std::less<Prio> >
    66 #endif
    67   class FibHeap {
    68   public:     
    69     typedef Prio PrioType;
    70     
    71   private:
    72     class store;
    73     
    74     std::vector<store> container;
    75     int minimum;
    76     ItemIntMap &iimap;
    77     Compare comp;
    78     int num_items;
    79     
    80   public:
    81     ///Status of the nodes
    82     enum state_enum {
    83       ///The node is in the heap
    84       IN_HEAP = 0,
    85       ///The node has never been in the heap
    86       PRE_HEAP = -1,
    87       ///The node was in the heap but it got out of it
    88       POST_HEAP = -2
    89     };
    90     
    91     ///The constructor
    92 
    93     /**
    94        \c _iimap should be given to the constructor, since it is
    95        used internally to handle the cross references.
    96     */
    97     explicit FibHeap(ItemIntMap &_iimap) 
    98       : minimum(0), iimap(_iimap), num_items() {} 
    99  
   100     ///The constructor
   101 
   102     /**
   103        \c _iimap should be given to the constructor, since it is used
   104        internally to handle the cross references. \c _comp is an
   105        object for ordering of the priorities. 
   106     */
   107     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
   108 		  iimap(_iimap), comp(_comp), num_items() {}
   109     
   110     ///The number of items stored in the heap.
   111 
   112     /**
   113        Returns the number of items stored in the heap.
   114     */
   115     int size() const { return num_items; }
   116 
   117     ///Checks if the heap stores no items.
   118     
   119     /**
   120        Returns \c true if and only if the heap stores no items.
   121     */
   122     bool empty() const { return num_items==0; }
   123 
   124     ///\c item gets to the heap with priority \c value independently if \c item was already there.
   125 
   126     /**
   127        This method calls \ref push(\c item, \c value) if \c item is not
   128        stored in the heap and it calls \ref decrease(\c item, \c value) or
   129        \ref increase(\c item, \c value) otherwise.
   130     */
   131     void set (Item const item, PrioType const value); 
   132     
   133     ///Adds \c item to the heap with priority \c value. 
   134     
   135     /**
   136        Adds \c item to the heap with priority \c value. 
   137        \pre \c item must not be stored in the heap. 
   138     */
   139     void push (Item const item, PrioType const value);
   140     
   141     ///Returns the item with minimum priority relative to \c Compare.
   142     
   143     /**
   144        This method returns the item with minimum priority relative to \c
   145        Compare.  
   146        \pre The heap must be nonempty.  
   147     */
   148     Item top() const { return container[minimum].name; }
   149 
   150     ///Returns the minimum priority relative to \c Compare.
   151 
   152     /**
   153        It returns the minimum priority relative to \c Compare.
   154        \pre The heap must be nonempty.
   155     */
   156     PrioType prio() const { return container[minimum].prio; }
   157     
   158     ///Returns the priority of \c item.
   159 
   160     /**
   161        This function returns the priority of \c item.
   162        \pre \c item must be in the heap.
   163     */
   164     PrioType& operator[](const Item& item) { 
   165       return container[iimap[item]].prio; 
   166     }
   167     
   168     ///Returns the priority of \c item.
   169     
   170     /**
   171        It returns the priority of \c item.
   172        \pre \c item must be in the heap.
   173     */
   174     const PrioType& operator[](const Item& item) const { 
   175       return container[iimap[item]].prio; 
   176     }
   177 
   178 
   179     ///Deletes the item with minimum priority relative to \c Compare.
   180 
   181     /**
   182     This method deletes the item with minimum priority relative to \c
   183     Compare from the heap.  
   184     \pre The heap must be non-empty.  
   185     */
   186     void pop();
   187 
   188     ///Deletes \c item from the heap.
   189 
   190     /**
   191        This method deletes \c item from the heap, if \c item was already
   192        stored in the heap. It is quite inefficient in Fibonacci heaps.
   193     */
   194     void erase (const Item& item); 
   195 
   196     ///Decreases the priority of \c item to \c value.
   197 
   198     /**
   199        This method decreases the priority of \c item to \c value.
   200        \pre \c item must be stored in the heap with priority at least \c
   201        value relative to \c Compare.
   202     */
   203     void decrease (Item item, PrioType const value); 
   204 
   205     ///Increases the priority of \c item to \c value.
   206 
   207     /**
   208        This method sets the priority of \c item to \c value. Though
   209        there is no precondition on the priority of \c item, this
   210        method should be used only if it is indeed necessary to increase
   211        (relative to \c Compare) the priority of \c item, because this
   212        method is inefficient.
   213     */
   214     void increase (Item item, PrioType const value) {
   215       erase(item);
   216       push(item, value);
   217     }
   218 
   219 
   220     ///Returns if \c item is in, has already been in, or has never been in the heap.
   221 
   222     /**
   223        This method returns PRE_HEAP if \c item has never been in the
   224        heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   225        otherwise. In the latter case it is possible that \c item will
   226        get back to the heap again.
   227     */
   228     state_enum state(const Item &item) const {
   229       int i=iimap[item];
   230       if( i>=0 ) {
   231 	if ( container[i].in ) i=0;
   232 	else i=-2; 
   233       }
   234       return state_enum(i);
   235     }    
   236     
   237   private:
   238     
   239     void balance();
   240     void makeroot(int c);
   241     void cut(int a, int b);
   242     void cascade(int a);
   243     void fuse(int a, int b);
   244     void unlace(int a);
   245 
   246 
   247     class store {
   248       friend class FibHeap;
   249       
   250       Item name;
   251       int parent;
   252       int left_neighbor;
   253       int right_neighbor;
   254       int child;
   255       int degree;  
   256       bool marked;
   257       bool in;
   258       PrioType prio;
   259       
   260       store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
   261     };
   262   };    
   263  
   264 
   265 
   266     // **********************************************************************
   267     //  IMPLEMENTATIONS
   268     // **********************************************************************
   269     
   270   template <typename Item, typename Prio, typename ItemIntMap, 
   271     typename Compare>
   272   void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
   273   (Item const item, PrioType const value) 
   274   {
   275     int i=iimap[item];
   276     if ( i >= 0 && container[i].in ) {
   277       if ( comp(value, container[i].prio) ) decrease(item, value); 
   278       if ( comp(container[i].prio, value) ) increase(item, value); 
   279     } else push(item, value);
   280   }
   281     
   282   template <typename Item, typename Prio, typename ItemIntMap, 
   283     typename Compare>
   284   void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
   285   (Item const item, PrioType const value) {
   286       int i=iimap[item];      
   287       if ( i < 0 ) {
   288 	int s=container.size();
   289 	iimap.set( item, s );	
   290 	store st;
   291 	st.name=item;
   292 	container.push_back(st);
   293 	i=s;
   294       } else {
   295 	container[i].parent=container[i].child=-1;
   296 	container[i].degree=0;
   297 	container[i].in=true;
   298 	container[i].marked=false;
   299       }
   300 
   301       if ( num_items ) {
   302 	container[container[minimum].right_neighbor].left_neighbor=i;
   303 	container[i].right_neighbor=container[minimum].right_neighbor;
   304 	container[minimum].right_neighbor=i;
   305 	container[i].left_neighbor=minimum;
   306 	if ( comp( value, container[minimum].prio) ) minimum=i; 
   307       } else {
   308 	container[i].right_neighbor=container[i].left_neighbor=i;
   309 	minimum=i;	
   310       }
   311       container[i].prio=value;
   312       ++num_items;
   313     }
   314     
   315   template <typename Item, typename Prio, typename ItemIntMap, 
   316     typename Compare>
   317   void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
   318       /*The first case is that there are only one root.*/
   319       if ( container[minimum].left_neighbor==minimum ) {
   320 	container[minimum].in=false;
   321 	if ( container[minimum].degree!=0 ) { 
   322 	  makeroot(container[minimum].child);
   323 	  minimum=container[minimum].child;
   324 	  balance();
   325 	}
   326       } else {
   327 	int right=container[minimum].right_neighbor;
   328 	unlace(minimum);
   329 	container[minimum].in=false;
   330 	if ( container[minimum].degree > 0 ) {
   331 	  int left=container[minimum].left_neighbor;
   332 	  int child=container[minimum].child;
   333 	  int last_child=container[child].left_neighbor;
   334 	
   335 	  makeroot(child);
   336 	  
   337 	  container[left].right_neighbor=child;
   338 	  container[child].left_neighbor=left;
   339 	  container[right].left_neighbor=last_child;
   340 	  container[last_child].right_neighbor=right;
   341 	}
   342 	minimum=right;
   343 	balance();
   344       } // the case where there are more roots
   345       --num_items;   
   346     }
   347 
   348 
   349   template <typename Item, typename Prio, typename ItemIntMap, 
   350     typename Compare>
   351   void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
   352   (const Item& item) {
   353       int i=iimap[item];
   354       
   355       if ( i >= 0 && container[i].in ) { 	
   356 	if ( container[i].parent!=-1 ) {
   357 	  int p=container[i].parent;
   358 	  cut(i,p);	    
   359 	  cascade(p);
   360 	}
   361 	minimum=i;     //As if its prio would be -infinity
   362 	pop();
   363       }
   364   }
   365     
   366   template <typename Item, typename Prio, typename ItemIntMap, 
   367     typename Compare>
   368   void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
   369   (Item item, PrioType const value) {
   370       int i=iimap[item];
   371       container[i].prio=value;
   372       int p=container[i].parent;
   373       
   374       if ( p!=-1 && comp(value, container[p].prio) ) {
   375 	cut(i,p);	    
   376 	cascade(p);
   377       }      
   378       if ( comp(value, container[minimum].prio) ) minimum=i; 
   379   }
   380  
   381 
   382   template <typename Item, typename Prio, typename ItemIntMap, 
   383     typename Compare>
   384   void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
   385 
   386     int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
   387   
   388     std::vector<int> A(maxdeg,-1); 
   389     
   390     /*
   391      *Recall that now minimum does not point to the minimum prio element.
   392      *We set minimum to this during balance().
   393      */
   394     int anchor=container[minimum].left_neighbor; 
   395     int next=minimum; 
   396     bool end=false; 
   397     	
   398        do {
   399 	int active=next;
   400 	if ( anchor==active ) end=true;
   401 	int d=container[active].degree;
   402 	next=container[active].right_neighbor;
   403 
   404 	while (A[d]!=-1) {	  
   405 	  if( comp(container[active].prio, container[A[d]].prio) ) {
   406 	    fuse(active,A[d]); 
   407 	  } else { 
   408 	    fuse(A[d],active);
   409 	    active=A[d];
   410 	  } 
   411 	  A[d]=-1;
   412 	  ++d;
   413 	}	
   414 	A[d]=active;
   415        } while ( !end );
   416 
   417 
   418        while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
   419        int s=minimum;
   420        int m=minimum;
   421        do {  
   422 	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
   423 	 s=container[s].right_neighbor;
   424        } while ( s != m );
   425     }
   426 
   427   template <typename Item, typename Prio, typename ItemIntMap, 
   428     typename Compare>
   429   void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
   430   (int c) {
   431       int s=c;
   432       do {  
   433 	container[s].parent=-1;
   434 	s=container[s].right_neighbor;
   435       } while ( s != c );
   436     }
   437   
   438   
   439   template <typename Item, typename Prio, typename ItemIntMap, 
   440     typename Compare>
   441   void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
   442   (int a, int b) {    
   443     /*
   444      *Replacing a from the children of b.
   445      */
   446     --container[b].degree;
   447     
   448     if ( container[b].degree !=0 ) {
   449       int child=container[b].child;
   450       if ( child==a ) 
   451 	container[b].child=container[child].right_neighbor;
   452       unlace(a);
   453     }
   454     
   455     
   456     /*Lacing a to the roots.*/
   457     int right=container[minimum].right_neighbor;
   458     container[minimum].right_neighbor=a;
   459     container[a].left_neighbor=minimum;
   460     container[a].right_neighbor=right;
   461     container[right].left_neighbor=a;
   462     
   463     container[a].parent=-1;
   464     container[a].marked=false;
   465   }
   466   
   467 
   468   template <typename Item, typename Prio, typename ItemIntMap, 
   469     typename Compare>
   470   void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
   471   (int a) 
   472     {
   473       if ( container[a].parent!=-1 ) {
   474 	int p=container[a].parent;
   475 	
   476 	if ( container[a].marked==false ) container[a].marked=true;
   477 	else {
   478 	  cut(a,p);
   479 	  cascade(p);
   480 	}
   481       }
   482     }
   483 
   484 
   485   template <typename Item, typename Prio, typename ItemIntMap, 
   486     typename Compare>
   487   void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
   488   (int a, int b) {
   489       unlace(b);
   490       
   491       /*Lacing b under a.*/
   492       container[b].parent=a;
   493 
   494       if (container[a].degree==0) {
   495 	container[b].left_neighbor=b;
   496 	container[b].right_neighbor=b;
   497 	container[a].child=b;	
   498       } else {
   499 	int child=container[a].child;
   500 	int last_child=container[child].left_neighbor;
   501 	container[child].left_neighbor=b;
   502 	container[b].right_neighbor=child;
   503 	container[last_child].right_neighbor=b;
   504 	container[b].left_neighbor=last_child;
   505       }
   506 
   507       ++container[a].degree;
   508       
   509       container[b].marked=false;
   510     }
   511 
   512   
   513   /*
   514    *It is invoked only if a has siblings.
   515    */
   516   template <typename Item, typename Prio, typename ItemIntMap, 
   517     typename Compare>
   518   void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
   519   (int a) {      
   520       int leftn=container[a].left_neighbor;
   521       int rightn=container[a].right_neighbor;
   522       container[leftn].right_neighbor=rightn;
   523       container[rightn].left_neighbor=leftn;
   524   }
   525   
   526   ///@}
   527 
   528 } //namespace lemon
   529 
   530 #endif //LEMON_FIB_HEAP_H
   531