COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/fib_heap.h @ 430:60e4627e8c74

Last change on this file since 430:60e4627e8c74 was 430:60e4627e8c74, checked in by Alpar Juttner, 17 years ago

Many new modules (groups) in the documentation.

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