COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/fib_heap.h @ 167:7949a29a334e

Last change on this file since 167:7949a29a334e was 167:7949a29a334e, checked in by jacint, 16 years ago

* empty log message *

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