COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/fib_heap.h @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 967:6563019430ba, checked in by Alpar Juttner, 19 years ago

Several changes in doc.

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