COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/fib_heap.h @ 898:c46cfb2651ec

Last change on this file since 898:c46cfb2651ec was 857:4e948fd205f7, checked in by jacint, 20 years ago

docs changes

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