alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@255: alpar@921: #ifndef LEMON_FIB_HEAP_H alpar@921: #define LEMON_FIB_HEAP_H alpar@255: jacint@857: ///\file klao@491: ///\ingroup auxdat alpar@255: ///\brief Fibonacci Heap implementation. alpar@255: alpar@255: #include alpar@255: #include alpar@255: #include alpar@255: alpar@921: namespace lemon { alpar@255: alpar@430: /// \addtogroup auxdat alpar@430: /// @{ alpar@430: jacint@857: /// Fibonacci Heap. jacint@373: jacint@857: ///This class implements the \e Fibonacci \e heap data structure. A \e heap jacint@857: ///is a data structure for storing items with specified values called \e jacint@857: ///priorities in such a way that finding the item with minimum priority is alpar@911: ///efficient. \c Compare specifies the ordering of the priorities. In a heap jacint@857: ///one can change the priority of an item, add or erase an item, etc. jacint@857: /// jacint@857: ///The methods \ref increase and \ref erase are not efficient in a Fibonacci jacint@857: ///heap. In case of many calls to these operations, it is better to use a jacint@857: ///\e binary \e heap. jacint@857: /// jacint@857: ///\param Item Type of the items to be stored. jacint@857: ///\param Prio Type of the priority of the items. jacint@857: ///\param ItemIntMap A read and writable Item int map, for the usage of jacint@857: ///the heap. jacint@857: ///\param Compare A class for the ordering of the priorities. The jacint@857: ///default is \c std::less. jacint@857: /// alpar@967: ///\sa BinHeap alpar@967: ///\sa Dijkstra jacint@857: ///\author Jacint Szabo jacint@857: jacint@373: #ifdef DOXYGEN jacint@373: template jacint@373: #else jacint@373: template > jacint@373: #endif alpar@255: class FibHeap { jacint@387: public: alpar@255: typedef Prio PrioType; alpar@255: jacint@373: private: alpar@255: class store; alpar@255: alpar@255: std::vector container; alpar@255: int minimum; alpar@255: ItemIntMap &iimap; alpar@255: Compare comp; alpar@255: int num_items; jacint@373: alpar@255: public: alpar@1127: ///Status of the nodes alpar@255: enum state_enum { alpar@1127: ///The node is in the heap alpar@255: IN_HEAP = 0, alpar@1127: ///The node has never been in the heap alpar@255: PRE_HEAP = -1, alpar@1127: ///The node was in the heap but it got out of it alpar@255: POST_HEAP = -2 alpar@255: }; alpar@255: deba@1185: explicit FibHeap(ItemIntMap &_iimap) deba@1185: : minimum(0), iimap(_iimap), num_items() {} jacint@373: FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), alpar@255: iimap(_iimap), comp(_comp), num_items() {} alpar@255: jacint@373: ///The number of items stored in the heap. jacint@373: jacint@373: /** jacint@387: Returns the number of items stored in the heap. jacint@373: */ jacint@373: int size() const { return num_items; } jacint@373: jacint@373: ///Checks if the heap stores no items. alpar@255: jacint@373: /** jacint@857: Returns \c true if and only if the heap stores no items. jacint@373: */ jacint@373: bool empty() const { return num_items==0; } jacint@373: jacint@387: ///\c item gets to the heap with priority \c value independently if \c item was already there. jacint@373: jacint@373: /** jacint@387: This method calls \ref push(\c item, \c value) if \c item is not jacint@387: stored in the heap and it calls \ref decrease(\c item, \c value) or jacint@387: \ref increase(\c item, \c value) otherwise. jacint@373: */ jacint@387: void set (Item const item, PrioType const value); jacint@373: jacint@373: ///Adds \c item to the heap with priority \c value. jacint@373: jacint@373: /** jacint@373: Adds \c item to the heap with priority \c value. jacint@373: \pre \c item must not be stored in the heap. jacint@373: */ jacint@387: void push (Item const item, PrioType const value); jacint@373: alpar@911: ///Returns the item with minimum priority relative to \c Compare. jacint@373: jacint@373: /** alpar@911: This method returns the item with minimum priority relative to \c jacint@857: Compare. jacint@857: \pre The heap must be nonempty. jacint@373: */ jacint@373: Item top() const { return container[minimum].name; } jacint@373: alpar@911: ///Returns the minimum priority relative to \c Compare. jacint@373: jacint@373: /** alpar@911: It returns the minimum priority relative to \c Compare. jacint@373: \pre The heap must be nonempty. jacint@373: */ jacint@373: PrioType prio() const { return container[minimum].prio; } jacint@373: jacint@373: ///Returns the priority of \c item. jacint@373: jacint@373: /** jacint@857: This function returns the priority of \c item. jacint@373: \pre \c item must be in the heap. jacint@373: */ jacint@387: PrioType& operator[](const Item& item) { jacint@387: return container[iimap[item]].prio; jacint@387: } jacint@373: jacint@373: ///Returns the priority of \c item. jacint@373: jacint@373: /** jacint@373: It returns the priority of \c item. jacint@373: \pre \c item must be in the heap. jacint@373: */ jacint@387: const PrioType& operator[](const Item& item) const { jacint@387: return container[iimap[item]].prio; alpar@255: } alpar@255: alpar@255: alpar@911: ///Deletes the item with minimum priority relative to \c Compare. alpar@255: jacint@373: /** alpar@911: This method deletes the item with minimum priority relative to \c jacint@857: Compare from the heap. jacint@857: \pre The heap must be non-empty. jacint@373: */ jacint@373: void pop(); jacint@373: jacint@373: ///Deletes \c item from the heap. jacint@373: jacint@373: /** jacint@373: This method deletes \c item from the heap, if \c item was already jacint@373: stored in the heap. It is quite inefficient in Fibonacci heaps. jacint@373: */ jacint@387: void erase (const Item& item); jacint@373: jacint@373: ///Decreases the priority of \c item to \c value. jacint@373: jacint@373: /** jacint@373: This method decreases the priority of \c item to \c value. jacint@373: \pre \c item must be stored in the heap with priority at least \c alpar@911: value relative to \c Compare. jacint@373: */ jacint@387: void decrease (Item item, PrioType const value); jacint@373: jacint@373: ///Increases the priority of \c item to \c value. jacint@373: jacint@373: /** jacint@373: This method sets the priority of \c item to \c value. Though jacint@373: there is no precondition on the priority of \c item, this jacint@857: method should be used only if it is indeed necessary to increase alpar@911: (relative to \c Compare) the priority of \c item, because this jacint@373: method is inefficient. jacint@373: */ jacint@387: void increase (Item item, PrioType const value) { jacint@387: erase(item); jacint@387: push(item, value); jacint@373: } jacint@373: jacint@373: jacint@857: ///Returns if \c item is in, has already been in, or has never been in the heap. jacint@373: jacint@373: /** jacint@373: This method returns PRE_HEAP if \c item has never been in the jacint@373: heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP jacint@373: otherwise. In the latter case it is possible that \c item will jacint@373: get back to the heap again. jacint@373: */ jacint@387: state_enum state(const Item &item) const { jacint@387: int i=iimap[item]; jacint@387: if( i>=0 ) { jacint@387: if ( container[i].in ) i=0; jacint@387: else i=-2; jacint@387: } jacint@387: return state_enum(i); jacint@387: } jacint@387: jacint@387: private: jacint@387: jacint@387: void balance(); jacint@387: void makeroot(int c); jacint@387: void cut(int a, int b); jacint@387: void cascade(int a); jacint@387: void fuse(int a, int b); jacint@387: void unlace(int a); jacint@373: jacint@373: jacint@387: class store { jacint@387: friend class FibHeap; jacint@387: jacint@387: Item name; jacint@387: int parent; jacint@387: int left_neighbor; jacint@387: int right_neighbor; jacint@387: int child; jacint@387: int degree; jacint@387: bool marked; jacint@387: bool in; jacint@387: PrioType prio; jacint@387: jacint@387: store() : parent(-1), child(-1), degree(), marked(false), in(true) {} jacint@387: }; jacint@387: }; jacint@387: jacint@387: jacint@373: jacint@373: // ********************************************************************** jacint@373: // IMPLEMENTATIONS jacint@373: // ********************************************************************** jacint@373: jacint@387: template jacint@387: void FibHeap::set jacint@387: (Item const item, PrioType const value) jacint@387: { jacint@387: int i=iimap[item]; jacint@387: if ( i >= 0 && container[i].in ) { jacint@387: if ( comp(value, container[i].prio) ) decrease(item, value); jacint@387: if ( comp(container[i].prio, value) ) increase(item, value); jacint@387: } else push(item, value); jacint@387: } alpar@255: jacint@387: template jacint@387: void FibHeap::push jacint@387: (Item const item, PrioType const value) { jacint@387: int i=iimap[item]; alpar@255: if ( i < 0 ) { alpar@255: int s=container.size(); jacint@387: iimap.set( item, s ); alpar@255: store st; jacint@387: st.name=item; alpar@255: container.push_back(st); alpar@255: i=s; alpar@255: } else { alpar@255: container[i].parent=container[i].child=-1; alpar@255: container[i].degree=0; alpar@255: container[i].in=true; alpar@255: container[i].marked=false; alpar@255: } alpar@255: alpar@255: if ( num_items ) { alpar@255: container[container[minimum].right_neighbor].left_neighbor=i; alpar@255: container[i].right_neighbor=container[minimum].right_neighbor; alpar@255: container[minimum].right_neighbor=i; alpar@255: container[i].left_neighbor=minimum; alpar@255: if ( comp( value, container[minimum].prio) ) minimum=i; alpar@255: } else { alpar@255: container[i].right_neighbor=container[i].left_neighbor=i; alpar@255: minimum=i; alpar@255: } alpar@255: container[i].prio=value; alpar@255: ++num_items; alpar@255: } alpar@255: jacint@387: template jacint@387: void FibHeap::pop() { alpar@255: /*The first case is that there are only one root.*/ alpar@255: if ( container[minimum].left_neighbor==minimum ) { alpar@255: container[minimum].in=false; alpar@255: if ( container[minimum].degree!=0 ) { alpar@255: makeroot(container[minimum].child); alpar@255: minimum=container[minimum].child; alpar@255: balance(); alpar@255: } alpar@255: } else { alpar@255: int right=container[minimum].right_neighbor; alpar@255: unlace(minimum); alpar@255: container[minimum].in=false; alpar@255: if ( container[minimum].degree > 0 ) { alpar@255: int left=container[minimum].left_neighbor; alpar@255: int child=container[minimum].child; alpar@255: int last_child=container[child].left_neighbor; alpar@255: alpar@255: makeroot(child); alpar@255: alpar@255: container[left].right_neighbor=child; alpar@255: container[child].left_neighbor=left; alpar@255: container[right].left_neighbor=last_child; alpar@255: container[last_child].right_neighbor=right; alpar@255: } alpar@255: minimum=right; alpar@255: balance(); alpar@255: } // the case where there are more roots alpar@255: --num_items; alpar@255: } alpar@255: jacint@387: jacint@387: template jacint@387: void FibHeap::erase jacint@387: (const Item& item) { jacint@387: int i=iimap[item]; alpar@255: alpar@255: if ( i >= 0 && container[i].in ) { alpar@255: if ( container[i].parent!=-1 ) { alpar@255: int p=container[i].parent; alpar@255: cut(i,p); alpar@255: cascade(p); alpar@255: } alpar@255: minimum=i; //As if its prio would be -infinity alpar@255: pop(); alpar@255: } jacint@387: } alpar@255: jacint@387: template jacint@387: void FibHeap::decrease jacint@387: (Item item, PrioType const value) { jacint@387: int i=iimap[item]; alpar@255: container[i].prio=value; alpar@255: int p=container[i].parent; alpar@255: alpar@255: if ( p!=-1 && comp(value, container[p].prio) ) { alpar@255: cut(i,p); alpar@255: cascade(p); alpar@255: } alpar@255: if ( comp(value, container[minimum].prio) ) minimum=i; jacint@387: } jacint@387: alpar@255: jacint@387: template jacint@387: void FibHeap::balance() { alpar@255: alpar@255: int maxdeg=int( floor( 2.08*log(double(container.size()))))+1; alpar@255: alpar@255: std::vector A(maxdeg,-1); alpar@255: alpar@255: /* alpar@255: *Recall that now minimum does not point to the minimum prio element. alpar@255: *We set minimum to this during balance(). alpar@255: */ alpar@255: int anchor=container[minimum].left_neighbor; alpar@255: int next=minimum; alpar@255: bool end=false; alpar@255: alpar@255: do { alpar@255: int active=next; alpar@255: if ( anchor==active ) end=true; alpar@255: int d=container[active].degree; alpar@255: next=container[active].right_neighbor; alpar@255: alpar@255: while (A[d]!=-1) { alpar@255: if( comp(container[active].prio, container[A[d]].prio) ) { alpar@255: fuse(active,A[d]); alpar@255: } else { alpar@255: fuse(A[d],active); alpar@255: active=A[d]; alpar@255: } alpar@255: A[d]=-1; alpar@255: ++d; alpar@255: } alpar@255: A[d]=active; alpar@255: } while ( !end ); alpar@255: alpar@255: alpar@255: while ( container[minimum].parent >=0 ) minimum=container[minimum].parent; alpar@255: int s=minimum; alpar@255: int m=minimum; alpar@255: do { alpar@255: if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; alpar@255: s=container[s].right_neighbor; alpar@255: } while ( s != m ); alpar@255: } alpar@255: jacint@387: template jacint@387: void FibHeap::makeroot jacint@387: (int c) { alpar@255: int s=c; alpar@255: do { alpar@255: container[s].parent=-1; alpar@255: s=container[s].right_neighbor; alpar@255: } while ( s != c ); alpar@255: } jacint@387: jacint@387: jacint@387: template jacint@387: void FibHeap::cut jacint@387: (int a, int b) { jacint@387: /* jacint@387: *Replacing a from the children of b. jacint@387: */ jacint@387: --container[b].degree; alpar@255: jacint@387: if ( container[b].degree !=0 ) { jacint@387: int child=container[b].child; jacint@387: if ( child==a ) jacint@387: container[b].child=container[child].right_neighbor; jacint@387: unlace(a); jacint@387: } jacint@387: jacint@387: jacint@387: /*Lacing a to the roots.*/ jacint@387: int right=container[minimum].right_neighbor; jacint@387: container[minimum].right_neighbor=a; jacint@387: container[a].left_neighbor=minimum; jacint@387: container[a].right_neighbor=right; jacint@387: container[right].left_neighbor=a; jacint@387: jacint@387: container[a].parent=-1; jacint@387: container[a].marked=false; jacint@387: } jacint@387: alpar@255: jacint@387: template jacint@387: void FibHeap::cascade jacint@387: (int a) alpar@255: { alpar@255: if ( container[a].parent!=-1 ) { alpar@255: int p=container[a].parent; alpar@255: alpar@255: if ( container[a].marked==false ) container[a].marked=true; alpar@255: else { alpar@255: cut(a,p); alpar@255: cascade(p); alpar@255: } alpar@255: } alpar@255: } alpar@255: alpar@255: jacint@387: template jacint@387: void FibHeap::fuse jacint@387: (int a, int b) { alpar@255: unlace(b); alpar@255: alpar@255: /*Lacing b under a.*/ alpar@255: container[b].parent=a; alpar@255: alpar@255: if (container[a].degree==0) { alpar@255: container[b].left_neighbor=b; alpar@255: container[b].right_neighbor=b; alpar@255: container[a].child=b; alpar@255: } else { alpar@255: int child=container[a].child; alpar@255: int last_child=container[child].left_neighbor; alpar@255: container[child].left_neighbor=b; alpar@255: container[b].right_neighbor=child; alpar@255: container[last_child].right_neighbor=b; alpar@255: container[b].left_neighbor=last_child; alpar@255: } alpar@255: alpar@255: ++container[a].degree; alpar@255: alpar@255: container[b].marked=false; alpar@255: } alpar@255: jacint@387: jacint@387: /* jacint@387: *It is invoked only if a has siblings. jacint@387: */ jacint@387: template jacint@387: void FibHeap::unlace jacint@387: (int a) { alpar@255: int leftn=container[a].left_neighbor; alpar@255: int rightn=container[a].right_neighbor; alpar@255: container[leftn].right_neighbor=rightn; alpar@255: container[rightn].left_neighbor=leftn; jacint@387: } alpar@255: alpar@430: ///@} alpar@430: alpar@921: } //namespace lemon alpar@477: alpar@921: #endif //LEMON_FIB_HEAP_H alpar@477: