COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/fib_heap.h @ 1185:22bb02339808

Last change on this file since 1185:22bb02339808 was 1185:22bb02339808, checked in by Balazs Dezso, 15 years ago

make constructors explicit

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