COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/fib_heap.h @ 161:743fa50c442e

Last change on this file since 161:743fa50c442e was 161:743fa50c442e, checked in by jacint, 17 years ago

* empty log message *

File size: 8.0 KB
Line 
1// -*- C++ -*-
2/*
3 *template <typename Item,
4 *          typename Prio,
5 *          typename ItemIntMap,
6 *          typename Compare = std::less<Prio> >
7 *
8 *constructors:
9 *
10 *FibHeap(ItemIntMap),   FibHeap(ItemIntMap, Compare)
11 *
12 *Member functions:
13 *
14 *int size() : returns the number of elements in the heap
15 *
16 *bool empty() : true iff size()=0
17 *
18 *void set(Item, Prio) : calls push(Item, Prio) if Item is not
19 *     in the heap, and calls decrease/increase(Item, Prio) otherwise
20 *
21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
22 *     mustn't be in the heap.
23 *
24 *Item top() : returns the Item with least Prio
25 *
26 *Prio prio() : returns the least Prio
27 * 
28 *Prio get(Item) : returns Prio of Item
29 *
30 *void pop() : deletes the Item with least Prio
31 *
32 *void erase(Item) : deletes Item from the heap if it was already there
33 *
34 *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap
35 *     with prio at least P.
36 *
37 *void increase(Item, P) : sets prio of Item to P.
38 *
39 *
40 *In Fibonacci heaps, increase and erase are not efficient, in case of
41 *many calls to these operations, it is better to use bin_heap.
42 */
43
44#ifndef FIB_HEAP_H
45#define FIB_HEAP_H
46
47#include <vector>
48#include <functional>
49#include <math.h>
50
51namespace hugo {
52 
53  template <typename Item, typename Prio, typename ItemIntMap,
54    typename Compare = std::less<Prio> >
55 
56  class FibHeap {
57 
58    typedef Prio PrioType;
59   
60    class store;
61   
62    std::vector<store> container;
63    int minimum;
64    bool blank;
65    ItemIntMap &iimap;
66    Compare comp;
67   
68  public :
69   
70    FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {}
71    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
72      blank(true), iimap(_iimap), comp(_comp) {}
73   
74   
75    int size() const {
76      int s=0;
77      for ( unsigned int i=0; i!=container.size(); ++i )
78        if ( container[i].in ) ++s;
79      return s;
80    }
81
82
83    bool empty() const { return blank; }
84
85
86    void set (Item const it, PrioType const value) {
87      int i=iimap.get(it);
88      if ( i >= 0 && container[i].in ) {
89        if ( !comp(container[i].prio, value) ) decrease(it, value);
90        if ( comp(container[i].prio, value) ) increase(it, value);
91      } else push(it, value);
92    }
93   
94
95    void push (Item const it, PrioType const value) {
96      int i=iimap.get(it);     
97      if ( i < 0 ) {
98        int s=container.size();
99        iimap.set( it, s );     
100        store st;
101        st.name=it;
102        container.push_back(st);
103        i=s;
104      }
105     
106      if ( !blank ) {
107        container[container[minimum].right_neighbor].left_neighbor=i;
108        container[i].right_neighbor=container[minimum].right_neighbor;
109        container[minimum].right_neighbor=i;
110        container[i].left_neighbor=minimum;
111        if ( !comp( container[minimum].prio, value) ) minimum=i;
112       
113      } else {
114        container[i].right_neighbor=container[i].left_neighbor=i;
115        minimum=i;     
116        blank=false;
117      }
118      container[i].prio=value;
119    }
120   
121
122
123    Item top() const {
124      if ( !blank ) {
125        return container[minimum].name;
126      } else {
127        return Item();
128      }
129    }
130   
131   
132    PrioType prio() const {
133      if ( !blank ) {
134        return container[minimum].prio;
135      } else {
136        return PrioType();
137      }
138    }
139   
140
141    const PrioType get(const Item& it) const
142    {
143      int i=iimap.get(it);
144     
145      if ( i >= 0 && container[i].in ) {
146        return container[i].prio;
147      } else {
148        return PrioType();
149      }
150    }
151
152
153    void pop() {
154      if ( !blank ) {
155       
156        /*The first case is that there are only one root.*/
157        if ( container[minimum].left_neighbor==minimum ) {
158          container[minimum].in=false;
159          if ( container[minimum].degree==0 ) blank=true;
160          else {
161            makeroot(container[minimum].child);
162            minimum=container[minimum].child;
163            balance();
164          }
165       } else {
166         int right=container[minimum].right_neighbor;
167         unlace(minimum);
168         container[minimum].in=false;
169         if ( container[minimum].degree > 0 ) {
170           int left=container[minimum].left_neighbor;
171           int child=container[minimum].child;
172           int last_child=container[child].left_neighbor;
173           
174           container[left].right_neighbor=child;
175           container[child].left_neighbor=left;
176           container[right].left_neighbor=last_child;
177           container[last_child].right_neighbor=right;
178           
179           makeroot(child);
180         }
181         minimum=right;
182         balance();
183       } // the case where there are more roots
184     }
185   }
186
187   
188   void erase (const Item& it) {
189     int i=iimap.get(it);
190     
191     if ( i >= 0 && container[i].in ) {
192       
193       if ( container[i].parent!=-1 ) {
194         int p=container[i].parent;
195         cut(i,p);         
196         cascade(p);
197         minimum=i;     //As if its prio would be -infinity
198       }
199       pop();
200     }
201   }
202   
203
204    void decrease (Item it, PrioType const value) {
205      int i=iimap.get(it);
206      container[i].prio=value;
207      int p=container[i].parent;
208 
209      if ( p!=-1 && comp(value, container[p].prio) ) {
210        cut(i,p);           
211        cascade(p);
212        if ( comp(value, container[minimum].prio) ) minimum=i;
213      }
214    }
215   
216
217    void increase (Item it, PrioType const value) {
218      erase(it);
219      push(it, value);
220    }
221
222
223  private:
224   
225    void balance() {     
226    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
227 
228    std::vector<int> A(maxdeg,-1);
229   
230    /*
231     *Recall that now minimum does not point to the minimum prio element.
232     *We set minimum to this during balance().
233     */
234    int anchor=container[minimum].left_neighbor;
235    int next=minimum;
236    bool end=false;
237       
238       do {
239        int active=next;
240        int d=container[active].degree;
241        if ( anchor==active ) end=true;
242        next = container[active].right_neighbor;
243        if ( !comp(container[minimum].prio, container[active].prio) )
244          minimum=active;
245
246        while (A[d]!=-1) {
247         
248          if( comp(container[active].prio, container[A[d]].prio) ) {
249            fuse(active,A[d]);
250          } else {
251            fuse(A[d],active);
252            active=A[d];
253          }
254          A[d]=-1;
255          ++d;
256        }
257       
258        A[d]=active;
259       } while ( !end );
260  }
261
262
263
264
265    /*
266     *All the siblings of a are made roots.
267     */
268    void makeroot (int c) 
269    {
270      int s=c;
271      do { 
272        container[s].parent=-1;
273        s=container[s].right_neighbor;
274      } while ( s != c );
275    }
276   
277
278    void cut (int a, int b)
279    {   
280
281      /*
282       *Replacing a from the children of b.
283       */
284      --container[b].degree;
285
286      if ( container[b].degree !=0 ) {
287      int child=container[b].child;
288      if ( child==a )
289        container[b].child=container[child].right_neighbor;
290     
291      unlace(a);
292       
293      }
294   
295
296      /*Lacing i to the roots.*/
297      int right=container[minimum].right_neighbor;
298      container[minimum].right_neighbor=a;
299      container[a].left_neighbor=minimum;
300      container[a].right_neighbor=right;
301      container[right].left_neighbor=a;
302
303      container[a].parent=-1;
304      container[a].marked=false;
305    }
306
307
308    void cascade (int a)
309    {
310      if ( container[a].parent!=-1 ) {
311        int p=container[a].parent;
312       
313        if ( container[a].marked==false ) container[a].marked=true;
314        else {
315          cut(a,p);
316          cascade(p);
317        }
318      }
319    }
320
321
322    void fuse (int a, int b)
323    {
324     
325      unlace(b);
326
327     
328      /*Lacing b under a.*/
329      container[b].parent=a;
330
331      if (container[a].degree==0) {
332        container[b].left_neighbor=b;
333        container[b].right_neighbor=b;
334        container[a].child=b;   
335      } else {
336        int child=container[a].child;
337        int last_child=container[child].left_neighbor;
338        container[child].left_neighbor=b;
339        container[b].right_neighbor=child;
340        container[last_child].right_neighbor=b;
341        container[b].left_neighbor=last_child;
342      }
343
344      ++container[a].degree;
345     
346      container[b].marked=false;
347    }
348
349
350    /*
351     *It is invoked only if a has siblings.
352     */
353
354    void unlace (int a) {     
355      int leftn=container[a].left_neighbor;
356      int rightn=container[a].right_neighbor;
357      container[leftn].right_neighbor=rightn;
358      container[rightn].left_neighbor=leftn;
359    }
360
361
362    class store {
363      friend class FibHeap;
364     
365      Item name;
366      int parent;
367      int left_neighbor;
368      int right_neighbor;
369      int child;
370      int degree; 
371      bool marked;
372      bool in;
373      PrioType prio;
374
375      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
376    };
377   
378  };
379 
380} //namespace hugo
381#endif
382
383
384
385
386
387
Note: See TracBrowser for help on using the repository browser.