COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fib_heap.h @ 1435:8e85e6bbefdf

Last change on this file since 1435:8e85e6bbefdf was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 15 years ago

trunk/src/* move to trunk/

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