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