COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/dijkstra/fib_heap.h @ 222:0c6bd3a98edf

Last change on this file since 222:0c6bd3a98edf was 222:0c6bd3a98edf, checked in by Alpar Juttner, 16 years ago

Aprosagok...

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