COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/fib_heap.h @ 373:259ea2d741a2

Last change on this file since 373:259ea2d741a2 was 373:259ea2d741a2, checked in by jacint, 17 years ago

Changes in the documentation.

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