NodeSubGraphWrapper, test, and ducumentation modifications.
2 * src/lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
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
17 #ifndef LEMON_FIB_HEAP_H
18 #define LEMON_FIB_HEAP_H
22 ///\brief Fibonacci Heap implementation.
30 /// \addtogroup auxdat
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.
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
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
49 ///\param Compare A class for the ordering of the priorities. The
50 ///default is \c std::less<Prio>.
52 ///\author Jacint Szabo
55 template <typename Item,
60 template <typename Item,
63 typename Compare = std::less<Prio> >
67 typedef Prio PrioType;
72 std::vector<store> container;
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() {}
89 ///The number of items stored in the heap.
92 Returns the number of items stored in the heap.
94 int size() const { return num_items; }
96 ///Checks if the heap stores no items.
99 Returns \c true if and only if the heap stores no items.
101 bool empty() const { return num_items==0; }
103 ///\c item gets to the heap with priority \c value independently if \c item was already there.
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.
110 void set (Item const item, PrioType const value);
112 ///Adds \c item to the heap with priority \c value.
115 Adds \c item to the heap with priority \c value.
116 \pre \c item must not be stored in the heap.
118 void push (Item const item, PrioType const value);
120 ///Returns the item with minimum priority relative to \c Compare.
123 This method returns the item with minimum priority relative to \c
125 \pre The heap must be nonempty.
127 Item top() const { return container[minimum].name; }
129 ///Returns the minimum priority relative to \c Compare.
132 It returns the minimum priority relative to \c Compare.
133 \pre The heap must be nonempty.
135 PrioType prio() const { return container[minimum].prio; }
137 ///Returns the priority of \c item.
140 This function returns the priority of \c item.
141 \pre \c item must be in the heap.
143 PrioType& operator[](const Item& item) {
144 return container[iimap[item]].prio;
147 ///Returns the priority of \c item.
150 It returns the priority of \c item.
151 \pre \c item must be in the heap.
153 const PrioType& operator[](const Item& item) const {
154 return container[iimap[item]].prio;
158 ///Deletes the item with minimum priority relative to \c Compare.
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.
167 ///Deletes \c item from the heap.
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.
173 void erase (const Item& item);
175 ///Decreases the priority of \c item to \c value.
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.
182 void decrease (Item item, PrioType const value);
184 ///Increases the priority of \c item to \c value.
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.
193 void increase (Item item, PrioType const value) {
199 ///Returns if \c item is in, has already been in, or has never been in the heap.
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.
207 state_enum state(const Item &item) const {
210 if ( container[i].in ) i=0;
213 return state_enum(i);
219 void makeroot(int c);
220 void cut(int a, int b);
222 void fuse(int a, int b);
227 friend class FibHeap;
239 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
245 // **********************************************************************
247 // **********************************************************************
249 template <typename Item, typename Prio, typename ItemIntMap,
251 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
252 (Item const item, PrioType const value)
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);
261 template <typename Item, typename Prio, typename ItemIntMap,
263 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
264 (Item const item, PrioType const value) {
267 int s=container.size();
268 iimap.set( item, s );
271 container.push_back(st);
274 container[i].parent=container[i].child=-1;
275 container[i].degree=0;
276 container[i].in=true;
277 container[i].marked=false;
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;
287 container[i].right_neighbor=container[i].left_neighbor=i;
290 container[i].prio=value;
294 template <typename Item, typename Prio, typename ItemIntMap,
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;
306 int right=container[minimum].right_neighbor;
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;
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;
323 } // the case where there are more roots
328 template <typename Item, typename Prio, typename ItemIntMap,
330 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
334 if ( i >= 0 && container[i].in ) {
335 if ( container[i].parent!=-1 ) {
336 int p=container[i].parent;
340 minimum=i; //As if its prio would be -infinity
345 template <typename Item, typename Prio, typename ItemIntMap,
347 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
348 (Item item, PrioType const value) {
350 container[i].prio=value;
351 int p=container[i].parent;
353 if ( p!=-1 && comp(value, container[p].prio) ) {
357 if ( comp(value, container[minimum].prio) ) minimum=i;
361 template <typename Item, typename Prio, typename ItemIntMap,
363 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
365 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
367 std::vector<int> A(maxdeg,-1);
370 *Recall that now minimum does not point to the minimum prio element.
371 *We set minimum to this during balance().
373 int anchor=container[minimum].left_neighbor;
379 if ( anchor==active ) end=true;
380 int d=container[active].degree;
381 next=container[active].right_neighbor;
384 if( comp(container[active].prio, container[A[d]].prio) ) {
397 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
401 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
402 s=container[s].right_neighbor;
406 template <typename Item, typename Prio, typename ItemIntMap,
408 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
412 container[s].parent=-1;
413 s=container[s].right_neighbor;
418 template <typename Item, typename Prio, typename ItemIntMap,
420 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
423 *Replacing a from the children of b.
425 --container[b].degree;
427 if ( container[b].degree !=0 ) {
428 int child=container[b].child;
430 container[b].child=container[child].right_neighbor;
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;
442 container[a].parent=-1;
443 container[a].marked=false;
447 template <typename Item, typename Prio, typename ItemIntMap,
449 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
452 if ( container[a].parent!=-1 ) {
453 int p=container[a].parent;
455 if ( container[a].marked==false ) container[a].marked=true;
464 template <typename Item, typename Prio, typename ItemIntMap,
466 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
470 /*Lacing b under a.*/
471 container[b].parent=a;
473 if (container[a].degree==0) {
474 container[b].left_neighbor=b;
475 container[b].right_neighbor=b;
476 container[a].child=b;
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;
486 ++container[a].degree;
488 container[b].marked=false;
493 *It is invoked only if a has siblings.
495 template <typename Item, typename Prio, typename ItemIntMap,
497 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
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;
509 #endif //LEMON_FIB_HEAP_H