alpar@906: /* -*- C++ -*- ladanyi@1435: * lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1875: * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, 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 deba@1332: #include alpar@255: alpar@921: namespace lemon { alpar@255: deba@1834: /// \ingroup auxdat 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. alpar@1204: ///\param ItemIntMap A read and writable Item int map, used internally alpar@1204: ///to handle the cross references. 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@1717: /// \brief The constructor deba@1717: /// deba@1717: /// \c _iimap should be given to the constructor, since it is deba@1717: /// used internally to handle the cross references. deba@1185: explicit FibHeap(ItemIntMap &_iimap) deba@1185: : minimum(0), iimap(_iimap), num_items() {} jacint@1270: deba@1717: /// \brief The constructor deba@1717: /// deba@1717: /// \c _iimap should be given to the constructor, since it is used deba@1717: /// internally to handle the cross references. \c _comp is an deba@1717: /// object for ordering of the priorities. jacint@373: FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), jacint@1270: iimap(_iimap), comp(_comp), num_items() {} alpar@255: deba@1717: /// \brief The number of items stored in the heap. deba@1717: /// deba@1717: /// Returns the number of items stored in the heap. jacint@373: int size() const { return num_items; } jacint@373: deba@1717: /// \brief Checks if the heap stores no items. deba@1717: /// deba@1717: /// Returns \c true if and only if the heap stores no items. jacint@373: bool empty() const { return num_items==0; } jacint@373: deba@1717: /// \brief Make empty this heap. deba@1717: /// deba@1717: /// Make empty this heap. deba@1753: void clear() { deba@1753: if (num_items != 0) { deba@1753: for (int i = 0; i < (int)container.size(); ++i) { deba@1753: iimap[container[i].name] = -2; deba@1753: } deba@1717: } deba@1717: container.clear(); minimum = 0; num_items = 0; deba@1717: } jacint@373: deba@1717: /// \brief \c item gets to the heap with priority \c value independently deba@1717: /// if \c item was already there. deba@1717: /// deba@1717: /// This method calls \ref push(\c item, \c value) if \c item is not deba@1717: /// stored in the heap and it calls \ref decrease(\c item, \c value) or deba@1717: /// \ref increase(\c item, \c value) otherwise. jacint@387: void set (Item const item, PrioType const value); jacint@373: deba@1717: /// \brief Adds \c item to the heap with priority \c value. deba@1717: /// deba@1717: /// Adds \c item to the heap with priority \c value. deba@1717: /// \pre \c item must not be stored in the heap. jacint@387: void push (Item const item, PrioType const value); jacint@373: deba@1717: /// \brief Returns the item with minimum priority relative to \c Compare. deba@1717: /// deba@1717: /// This method returns the item with minimum priority relative to \c deba@1717: /// Compare. deba@1717: /// \pre The heap must be nonempty. jacint@373: Item top() const { return container[minimum].name; } jacint@373: deba@1717: /// \brief Returns the minimum priority relative to \c Compare. deba@1717: /// deba@1717: /// It returns the minimum priority relative to \c Compare. deba@1717: /// \pre The heap must be nonempty. jacint@373: PrioType prio() const { return container[minimum].prio; } jacint@373: deba@1717: /// \brief Returns the priority of \c item. deba@1717: /// deba@1717: /// This function returns the priority of \c item. deba@1717: /// \pre \c item must be in the heap. jacint@387: PrioType& operator[](const Item& item) { jacint@387: return container[iimap[item]].prio; jacint@387: } jacint@373: deba@1717: /// \brief Returns the priority of \c item. deba@1717: /// deba@1717: /// It returns the priority of \c item. deba@1717: /// \pre \c item must be in the heap. jacint@387: const PrioType& operator[](const Item& item) const { jacint@387: return container[iimap[item]].prio; alpar@255: } alpar@255: alpar@255: deba@1717: /// \brief Deletes the item with minimum priority relative to \c Compare. deba@1717: /// deba@1717: /// This method deletes the item with minimum priority relative to \c deba@1717: /// Compare from the heap. deba@1717: /// \pre The heap must be non-empty. jacint@373: void pop(); jacint@373: deba@1717: /// \brief Deletes \c item from the heap. deba@1717: /// deba@1717: /// This method deletes \c item from the heap, if \c item was already deba@1717: /// stored in the heap. It is quite inefficient in Fibonacci heaps. jacint@387: void erase (const Item& item); jacint@373: deba@1717: /// \brief Decreases the priority of \c item to \c value. deba@1717: /// deba@1717: /// This method decreases the priority of \c item to \c value. deba@1717: /// \pre \c item must be stored in the heap with priority at least \c deba@1717: /// value relative to \c Compare. jacint@387: void decrease (Item item, PrioType const value); jacint@373: deba@1717: /// \brief Increases the priority of \c item to \c value. deba@1717: /// deba@1717: /// This method sets the priority of \c item to \c value. Though deba@1717: /// there is no precondition on the priority of \c item, this deba@1717: /// method should be used only if it is indeed necessary to increase deba@1717: /// (relative to \c Compare) the priority of \c item, because this deba@1717: /// method is inefficient. jacint@387: void increase (Item item, PrioType const value) { jacint@387: erase(item); jacint@387: push(item, value); jacint@373: } jacint@373: jacint@373: deba@1717: /// \brief Returns if \c item is in, has already been in, or has never deba@1717: /// been in the heap. deba@1717: /// deba@1717: /// This method returns PRE_HEAP if \c item has never been in the deba@1717: /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP deba@1717: /// otherwise. In the latter case it is possible that \c item will deba@1717: /// get back to the heap again. 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: } deba@1902: deba@1902: /// \brief Sets the state of the \c item in the heap. deba@1902: /// deba@1902: /// Sets the state of the \c item in the heap. It can be used to deba@1902: /// manually clear the heap when it is important to achive the deba@1902: /// better time complexity. deba@1902: /// \param i The item. deba@1902: /// \param st The state. It should not be \c IN_HEAP. deba@1902: void state(const Item& i, state_enum st) { deba@1902: switch (st) { deba@1902: case POST_HEAP: deba@1902: case PRE_HEAP: deba@1902: if (state(i) == IN_HEAP) { deba@1902: erase(i); deba@1902: } deba@1903: iimap[i] = st; deba@1902: break; deba@1906: case IN_HEAP: deba@1906: break; deba@1902: } deba@1902: } 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: deba@1332: int maxdeg=int( std::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@921: } //namespace lemon alpar@477: alpar@921: #endif //LEMON_FIB_HEAP_H alpar@477: