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