COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/fib_heap.h @ 408:cc8629dc2935

Last change on this file since 408:cc8629dc2935 was 387:4406c93c862b, checked in by jacint, 18 years ago

Documentation added.

File size: 12.9 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 heap
19     is a data structure for storing items with specified values called \e
20     priorities, such that finding the item with minimum priority with respect
21     to \e Compare is efficient. In a heap one can change the priority of an
22     item, add or erase an item, etc.
23
24     The methods \ref increase and \ref erase are not efficient in a Fibonacci
25     heap. In case of many calls to these operations, it is better to use a
26     \e binary \e 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    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
71    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
72      iimap(_iimap), comp(_comp), num_items() {}
73   
74    ///The number of items stored in the heap.
75
76    /**
77       Returns the number of items stored in the heap.
78    */
79    int size() const { return num_items; }
80
81    ///Checks if the heap stores no items.
82   
83    /**
84       Returns \c true iff the heap stores no items.
85    */
86    bool empty() const { return num_items==0; }
87
88    ///\c item gets to the heap with priority \c value independently if \c item was already there.
89
90    /**
91       This method calls \ref push(\c item, \c value) if \c item is not
92       stored in the heap and it calls \ref decrease(\c item, \c value) or
93       \ref increase(\c item, \c value) otherwise.
94    */
95    void set (Item const item, PrioType const value);
96   
97    ///Adds \c item to the heap with priority \c value.
98   
99    /**
100       Adds \c item to the heap with priority \c value.
101       \pre \c item must not be stored in the heap.
102    */
103    void push (Item const item, PrioType const value);
104   
105   
106    ///Returns the item having the minimum priority w.r.t.  Compare.
107   
108    /**
109       This method returns the item having the minimum priority w.r.t.  Compare.
110       \pre The heap must be nonempty.
111    */
112    Item top() const { return container[minimum].name; }
113   
114
115    ///Returns the minimum priority w.r.t.  Compare.
116
117    /**
118       It returns the minimum priority w.r.t.  Compare.
119       \pre The heap must be nonempty.
120    */
121    PrioType prio() const { return container[minimum].prio; }
122   
123
124    ///Returns the priority of \c item.
125
126    /**
127       It returns the priority of \c item.
128       \pre \c item must be in the heap.
129    */
130    PrioType& operator[](const Item& item) {
131      return container[iimap[item]].prio;
132    }
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& item) const {
141      return container[iimap[item]].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);
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);
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 there is a need to really \e increase
178       (w.r.t.  Compare) the priority of \c item, because this
179       method is inefficient.
180    */
181    void increase (Item item, PrioType const value) {
182      erase(item);
183      push(item, value);
184    }
185
186
187    ///Tells if \c item is in, was already in, or has never 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 &item) const {
196      int i=iimap[item];
197      if( i>=0 ) {
198        if ( container[i].in ) i=0;
199        else i=-2;
200      }
201      return state_enum(i);
202    }   
203   
204  private:
205   
206    void balance();
207    void makeroot(int c);
208    void cut(int a, int b);
209    void cascade(int a);
210    void fuse(int a, int b);
211    void unlace(int a);
212
213
214    class store {
215      friend class FibHeap;
216     
217      Item name;
218      int parent;
219      int left_neighbor;
220      int right_neighbor;
221      int child;
222      int degree; 
223      bool marked;
224      bool in;
225      PrioType prio;
226     
227      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
228    };
229  };   
230 
231
232
233    // **********************************************************************
234    //  IMPLEMENTATIONS
235    // **********************************************************************
236   
237  template <typename Item, typename Prio, typename ItemIntMap,
238    typename Compare>
239  void FibHeap<Item, Prio, ItemIntMap, Compare>::set
240  (Item const item, PrioType const value)
241  {
242    int i=iimap[item];
243    if ( i >= 0 && container[i].in ) {
244      if ( comp(value, container[i].prio) ) decrease(item, value);
245      if ( comp(container[i].prio, value) ) increase(item, value);
246    } else push(item, value);
247  }
248   
249  template <typename Item, typename Prio, typename ItemIntMap,
250    typename Compare>
251  void FibHeap<Item, Prio, ItemIntMap, Compare>::push
252  (Item const item, PrioType const value) {
253      int i=iimap[item];     
254      if ( i < 0 ) {
255        int s=container.size();
256        iimap.set( item, s );   
257        store st;
258        st.name=item;
259        container.push_back(st);
260        i=s;
261      } else {
262        container[i].parent=container[i].child=-1;
263        container[i].degree=0;
264        container[i].in=true;
265        container[i].marked=false;
266      }
267
268      if ( num_items ) {
269        container[container[minimum].right_neighbor].left_neighbor=i;
270        container[i].right_neighbor=container[minimum].right_neighbor;
271        container[minimum].right_neighbor=i;
272        container[i].left_neighbor=minimum;
273        if ( comp( value, container[minimum].prio) ) minimum=i;
274      } else {
275        container[i].right_neighbor=container[i].left_neighbor=i;
276        minimum=i;     
277      }
278      container[i].prio=value;
279      ++num_items;
280    }
281   
282  template <typename Item, typename Prio, typename ItemIntMap,
283    typename Compare>
284  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
285      /*The first case is that there are only one root.*/
286      if ( container[minimum].left_neighbor==minimum ) {
287        container[minimum].in=false;
288        if ( container[minimum].degree!=0 ) {
289          makeroot(container[minimum].child);
290          minimum=container[minimum].child;
291          balance();
292        }
293      } else {
294        int right=container[minimum].right_neighbor;
295        unlace(minimum);
296        container[minimum].in=false;
297        if ( container[minimum].degree > 0 ) {
298          int left=container[minimum].left_neighbor;
299          int child=container[minimum].child;
300          int last_child=container[child].left_neighbor;
301       
302          makeroot(child);
303         
304          container[left].right_neighbor=child;
305          container[child].left_neighbor=left;
306          container[right].left_neighbor=last_child;
307          container[last_child].right_neighbor=right;
308        }
309        minimum=right;
310        balance();
311      } // the case where there are more roots
312      --num_items;   
313    }
314
315
316  template <typename Item, typename Prio, typename ItemIntMap,
317    typename Compare>
318  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
319  (const Item& item) {
320      int i=iimap[item];
321     
322      if ( i >= 0 && container[i].in ) {       
323        if ( container[i].parent!=-1 ) {
324          int p=container[i].parent;
325          cut(i,p);         
326          cascade(p);
327        }
328        minimum=i;     //As if its prio would be -infinity
329        pop();
330      }
331  }
332   
333  template <typename Item, typename Prio, typename ItemIntMap,
334    typename Compare>
335  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
336  (Item item, PrioType const value) {
337      int i=iimap[item];
338      container[i].prio=value;
339      int p=container[i].parent;
340     
341      if ( p!=-1 && comp(value, container[p].prio) ) {
342        cut(i,p);           
343        cascade(p);
344      }     
345      if ( comp(value, container[minimum].prio) ) minimum=i;
346  }
347 
348
349  template <typename Item, typename Prio, typename ItemIntMap,
350    typename Compare>
351  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {     
352
353    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
354 
355    std::vector<int> A(maxdeg,-1);
356   
357    /*
358     *Recall that now minimum does not point to the minimum prio element.
359     *We set minimum to this during balance().
360     */
361    int anchor=container[minimum].left_neighbor;
362    int next=minimum;
363    bool end=false;
364       
365       do {
366        int active=next;
367        if ( anchor==active ) end=true;
368        int d=container[active].degree;
369        next=container[active].right_neighbor;
370
371        while (A[d]!=-1) {       
372          if( comp(container[active].prio, container[A[d]].prio) ) {
373            fuse(active,A[d]);
374          } else {
375            fuse(A[d],active);
376            active=A[d];
377          }
378          A[d]=-1;
379          ++d;
380        }       
381        A[d]=active;
382       } while ( !end );
383
384
385       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
386       int s=minimum;
387       int m=minimum;
388       do { 
389         if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
390         s=container[s].right_neighbor;
391       } while ( s != m );
392    }
393
394  template <typename Item, typename Prio, typename ItemIntMap,
395    typename Compare>
396  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
397  (int c) {
398      int s=c;
399      do { 
400        container[s].parent=-1;
401        s=container[s].right_neighbor;
402      } while ( s != c );
403    }
404 
405 
406  template <typename Item, typename Prio, typename ItemIntMap,
407    typename Compare>
408  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
409  (int a, int b) {   
410    /*
411     *Replacing a from the children of b.
412     */
413    --container[b].degree;
414   
415    if ( container[b].degree !=0 ) {
416      int child=container[b].child;
417      if ( child==a )
418        container[b].child=container[child].right_neighbor;
419      unlace(a);
420    }
421   
422   
423    /*Lacing a to the roots.*/
424    int right=container[minimum].right_neighbor;
425    container[minimum].right_neighbor=a;
426    container[a].left_neighbor=minimum;
427    container[a].right_neighbor=right;
428    container[right].left_neighbor=a;
429   
430    container[a].parent=-1;
431    container[a].marked=false;
432  }
433 
434
435  template <typename Item, typename Prio, typename ItemIntMap,
436    typename Compare>
437  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
438  (int a)
439    {
440      if ( container[a].parent!=-1 ) {
441        int p=container[a].parent;
442       
443        if ( container[a].marked==false ) container[a].marked=true;
444        else {
445          cut(a,p);
446          cascade(p);
447        }
448      }
449    }
450
451
452  template <typename Item, typename Prio, typename ItemIntMap,
453    typename Compare>
454  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
455  (int a, int b) {
456      unlace(b);
457     
458      /*Lacing b under a.*/
459      container[b].parent=a;
460
461      if (container[a].degree==0) {
462        container[b].left_neighbor=b;
463        container[b].right_neighbor=b;
464        container[a].child=b;   
465      } else {
466        int child=container[a].child;
467        int last_child=container[child].left_neighbor;
468        container[child].left_neighbor=b;
469        container[b].right_neighbor=child;
470        container[last_child].right_neighbor=b;
471        container[b].left_neighbor=last_child;
472      }
473
474      ++container[a].degree;
475     
476      container[b].marked=false;
477    }
478
479 
480  /*
481   *It is invoked only if a has siblings.
482   */
483  template <typename Item, typename Prio, typename ItemIntMap,
484    typename Compare>
485  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
486  (int a) {     
487      int leftn=container[a].left_neighbor;
488      int rightn=container[a].right_neighbor;
489      container[leftn].right_neighbor=rightn;
490      container[rightn].left_neighbor=leftn;
491  }
492 
493} //namespace hugo
494#endif
Note: See TracBrowser for help on using the repository browser.