COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/fib_heap.h @ 749:8e933219691e

Last change on this file since 749:8e933219691e was 539:fb261e3a9a0f, checked in by Akos Ladanyi, 17 years ago

Rename 'include' to 'hugo' (for automake)

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