COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/fib_heap.h @ 947:93e9c45703ea

Last change on this file since 947:93e9c45703ea was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

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