COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/fib_heap.h @ 159:0defa5aa1229

Last change on this file since 159:0defa5aa1229 was 159:0defa5aa1229, checked in by jacint, 17 years ago

* empty log message *

File size: 8.3 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 push(Item, Prio) : pushes Item to the heap with priority Prio. If
19 *     Item was already in the heap, it calls decrease(Item, Prio)
20 *
21 *Item top() : returns the Item with least Prio
22 *
23 *Prio prio() : returns the least Prio
24 * 
25 *Prio get(Item) : returns Prio of Item
26 *
27 *void pop() : deletes the Item with least Prio
28 *
29 *void erase(Item) : deletes Item from the heap if it was already there
30 *
31 *void decrease(Item, P) : If Item was not in the heap, then it calls
32 *     push(Item, P). If item is in the heap with Prio more than P
33 *     then sets its Prio to P.
34 *
35 *void increase(Item, P) : If Item was not in the heap, then it calls
36 *     push(Item, P). If item is in the heap with Prio less than P
37 *     then sets its Prio 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 push (Item const it, PrioType const value)
87   {
88   
89     int i=iimap.get(it);
90     
91     if ( i >= 0 && container[i].in ) decrease(it, value);
92     else {
93       if ( i < 0 ) {
94         int s=container.size();
95         iimap.set( it, s );   
96         store st;
97         st.name=it;
98         container.push_back(st);
99         i=s;
100       }
101       
102       if ( !blank ) {
103         container[container[minimum].right_neighbor].left_neighbor=i;
104         container[i].right_neighbor=container[minimum].right_neighbor;
105         container[minimum].right_neighbor=i;
106         container[i].left_neighbor=minimum;
107         if ( !comp( container[minimum].prio, value) ) minimum=i;
108
109
110
111       } else {
112         container[i].right_neighbor=container[i].left_neighbor=i;
113         minimum=i;     
114         blank=false;
115       }
116       container[i].prio=value;
117     }
118   }
119
120
121    Item top() const {
122      if ( !blank ) {
123        return container[minimum].name;
124      } else {
125        return Item();
126      }
127    }
128   
129   
130    PrioType prio() const {
131      if ( !blank ) {
132        return container[minimum].prio;
133      } else {
134        return PrioType();
135      }
136    }
137   
138
139    const PrioType get(const Item& it) const
140    {
141      int i=iimap.get(it);
142     
143      if ( i >= 0 && container[i].in ) {
144        return container[i].prio;
145      } else {
146        return PrioType();
147      }
148    }
149
150
151    void pop() {
152      if ( !blank ) {
153       
154        /*The first case is that there are only one root.*/
155        if ( container[minimum].left_neighbor==minimum ) {
156          container[minimum].in=false;
157          if ( container[minimum].degree==0 ) blank=true;
158          else {
159            makeroot(container[minimum].child);
160            minimum=container[minimum].child;
161            balance();
162          }
163       } else {
164         int right=container[minimum].right_neighbor;
165         unlace(minimum);
166         container[minimum].in=false;
167         if ( container[minimum].degree > 0 ) {
168           int left=container[minimum].left_neighbor;
169           int child=container[minimum].child;
170           int last_child=container[child].left_neighbor;
171           
172           container[left].right_neighbor=child;
173           container[child].left_neighbor=left;
174           container[right].left_neighbor=last_child;
175           container[last_child].right_neighbor=right;
176           
177           makeroot(child);
178         }
179         minimum=right;
180         balance();
181       } // the case where there are more roots
182     }
183   }
184
185   
186   void erase (const Item& it) {
187     int i=iimap.get(it);
188     
189     if ( i >= 0 && container[i].in ) {
190       
191       if ( container[i].parent!=-1 ) {
192         int p=container[i].parent;
193         cut(i,p);         
194         cascade(p);
195         minimum=i;     //As if its prio would be -infinity
196       }
197       pop();
198     }
199   }
200   
201
202   void decrease (Item it, PrioType const value) {
203     int i=iimap.get(it);
204     if ( i >= 0 && container[i].in ) {
205       
206       if ( comp(value, container[i].prio) ) {
207         container[i].prio=value;
208         
209         if ( container[i].parent!=-1 ) {
210           int p=container[i].parent;
211           
212           if ( !comp(container[p].prio, value) ) {
213             cut(i,p);     
214             cascade(p);
215             if ( comp(value, container[minimum].prio) ) minimum=i;
216           }
217         }
218       }
219     } else push(it, value);
220   }
221   
222
223    void increase (Item it, PrioType const value) {
224      int i=iimap.get(it);
225     
226      if ( i >= 0 && container[i].in ) {
227        if ( comp(container[i].prio, value) ) {
228          erase(it);
229          push(it, value);
230        }
231      } else push(it, value);
232    }
233
234
235  private:
236   
237    void balance() {     
238    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
239 
240    std::vector<int> A(maxdeg,-1);
241   
242    /*
243     *Recall that now minimum does not point to the minimum prio element.
244     *We set minimum to this during balance().
245     */
246    int anchor=container[minimum].left_neighbor;
247    int next=minimum;
248    bool end=false;
249       
250       do {
251        int active=next;
252        int d=container[active].degree;
253        if ( anchor==active ) end=true;
254        next = container[active].right_neighbor;
255        if ( !comp(container[minimum].prio, container[active].prio) )
256          minimum=active;
257
258        while (A[d]!=-1) {
259         
260          if( comp(container[active].prio, container[A[d]].prio) ) {
261            fuse(active,A[d]);
262          } else {
263            fuse(A[d],active);
264            active=A[d];
265          }
266          A[d]=-1;
267          ++d;
268        }
269       
270        A[d]=active;
271       } while ( !end );
272  }
273
274
275
276
277    /*
278     *All the siblings of a are made roots.
279     */
280    void makeroot (int c) 
281    {
282      int s=c;
283      do { 
284        container[s].parent=-1;
285        s=container[s].right_neighbor;
286      } while ( s != c );
287    }
288   
289
290    void cut (int a, int b)
291    {   
292
293      /*
294       *Replacing a from the children of b.
295       */
296      --container[b].degree;
297
298      if ( container[b].degree !=0 ) {
299      int child=container[b].child;
300      if ( child==a )
301        container[b].child=container[child].right_neighbor;
302     
303      unlace(a);
304       
305      }
306   
307
308      /*Lacing i to the roots.*/
309      int right=container[minimum].right_neighbor;
310      container[minimum].right_neighbor=a;
311      container[a].left_neighbor=minimum;
312      container[a].right_neighbor=right;
313      container[right].left_neighbor=a;
314
315      container[a].parent=-1;
316      container[a].marked=false;
317    }
318
319
320    void cascade (int a)
321    {
322      if ( container[a].parent!=-1 ) {
323        int p=container[a].parent;
324       
325        if ( container[a].marked==false ) container[a].marked=true;
326        else {
327          cut(a,p);
328          cascade(p);
329        }
330      }
331    }
332
333
334    void fuse (int a, int b)
335    {
336     
337      unlace(b);
338
339     
340      /*Lacing b under a.*/
341      container[b].parent=a;
342
343      if (container[a].degree==0) {
344        container[b].left_neighbor=b;
345        container[b].right_neighbor=b;
346        container[a].child=b;   
347      } else {
348        int child=container[a].child;
349        int last_child=container[child].left_neighbor;
350        container[child].left_neighbor=b;
351        container[b].right_neighbor=child;
352        container[last_child].right_neighbor=b;
353        container[b].left_neighbor=last_child;
354      }
355
356      ++container[a].degree;
357     
358      container[b].marked=false;
359    }
360
361
362    /*
363     *It is invoked only if a has siblings.
364     */
365
366    void unlace (int a) {     
367      int leftn=container[a].left_neighbor;
368      int rightn=container[a].right_neighbor;
369      container[leftn].right_neighbor=rightn;
370      container[rightn].left_neighbor=leftn;
371    }
372
373
374    class store {
375      friend class FibHeap;
376     
377      Item name;
378      int parent;
379      int left_neighbor;
380      int right_neighbor;
381      int child;
382      int degree; 
383      bool marked;
384      bool in;
385      PrioType prio;
386
387      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
388    };
389   
390  };
391 
392} //namespace hugo
393#endif
394
395
396
397
398
399
Note: See TracBrowser for help on using the repository browser.