COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/fib_heap.h @ 1165:c5e56125959a

Last change on this file since 1165:c5e56125959a was 1164:80bb73097736, checked in by Alpar Juttner, 19 years ago

A year has passed again.

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