alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * 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 alpar@2569: #include alpar@255: alpar@921: namespace lemon { alpar@255: deba@1834: /// \ingroup auxdat deba@2529: /// deba@2529: ///\brief Fibonacci Heap. deba@2529: /// 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 deba@2547: ///\ref BinHeap "binary heap". jacint@857: /// deba@2547: ///\param _Prio Type of the priority of the items. deba@2547: ///\param _ItemIntMap A read and writable Item int map, used internally alpar@1204: ///to handle the cross references. deba@2547: ///\param _Compare A class for the ordering of the priorities. The deba@2547: ///default is \c std::less<_Prio>. jacint@857: /// alpar@967: ///\sa BinHeap alpar@967: ///\sa Dijkstra jacint@857: ///\author Jacint Szabo jacint@857: jacint@373: #ifdef DOXYGEN deba@2547: template jacint@373: #else deba@2547: template > jacint@373: #endif alpar@255: class FibHeap { mqrelly@2263: public: deba@2547: typedef _ItemIntMap ItemIntMap; deba@2547: typedef _Prio Prio; mqrelly@2263: typedef typename ItemIntMap::Key Item; deba@2547: typedef std::pair Pair; deba@2547: typedef _Compare Compare; 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 deba@2547: enum State { 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. deba@2547: FibHeap(ItemIntMap &_iimap, const Compare &_comp) deba@2547: : minimum(0), 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@2050: /// Make empty this heap. It does not change the cross reference deba@2050: /// map. If you want to reuse a heap what is not surely empty you deba@2050: /// should first clear the heap and after that you should set the deba@2050: /// cross reference map for each item to \c PRE_HEAP. deba@1753: void clear() { 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. deba@2547: void set (const Item& item, const Prio& value) { deba@2547: int i=iimap[item]; deba@2547: if ( i >= 0 && container[i].in ) { deba@2547: if ( comp(value, container[i].prio) ) decrease(item, value); deba@2547: if ( comp(container[i].prio, value) ) increase(item, value); deba@2547: } else push(item, value); deba@2547: } 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. deba@2547: void push (const Item& item, const Prio& 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: deba@2547: /// \brief Returns the item with minimum priority relative to \c Compare. deba@2547: /// deba@2547: /// This method returns the item with minimum priority relative to \c deba@2547: /// Compare. deba@2547: /// \pre The heap must be nonempty. deba@2547: Item top() const { return container[minimum].name; } deba@2547: deba@2547: /// \brief Returns the minimum priority relative to \c Compare. deba@2547: /// deba@2547: /// It returns the minimum priority relative to \c Compare. deba@2547: /// \pre The heap must be nonempty. deba@2547: const Prio& prio() const { return container[minimum].prio; } deba@2547: deba@2547: /// \brief Returns the priority of \c item. deba@2547: /// deba@2547: /// It returns the priority of \c item. deba@2547: /// \pre \c item must be in the heap. deba@2547: const Prio& operator[](const Item& item) const { deba@2547: return container[iimap[item]].prio; deba@2547: } deba@2547: deba@2547: /// \brief Deletes the item with minimum priority relative to \c Compare. deba@2547: /// deba@2547: /// This method deletes the item with minimum priority relative to \c deba@2547: /// Compare from the heap. deba@2547: /// \pre The heap must be non-empty. deba@2547: void 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; deba@2547: 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: deba@2547: /// \brief Deletes \c item from the heap. deba@2547: /// deba@2547: /// This method deletes \c item from the heap, if \c item was already deba@2547: /// stored in the heap. It is quite inefficient in Fibonacci heaps. deba@2547: void erase (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: } deba@2547: } deba@2547: deba@2547: /// \brief Decreases the priority of \c item to \c value. deba@2547: /// deba@2547: /// This method decreases the priority of \c item to \c value. deba@2547: /// \pre \c item must be stored in the heap with priority at least \c deba@2547: /// value relative to \c Compare. deba@2547: void decrease (Item item, const Prio& 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; deba@2547: } alpar@255: deba@2547: /// \brief Increases the priority of \c item to \c value. deba@2547: /// deba@2547: /// This method sets the priority of \c item to \c value. Though deba@2547: /// there is no precondition on the priority of \c item, this deba@2547: /// method should be used only if it is indeed necessary to increase deba@2547: /// (relative to \c Compare) the priority of \c item, because this deba@2547: /// method is inefficient. deba@2547: void increase (Item item, const Prio& value) { deba@2547: erase(item); deba@2547: push(item, value); deba@2547: } alpar@255: deba@2547: deba@2547: /// \brief Returns if \c item is in, has already been in, or has never deba@2547: /// been in the heap. deba@2547: /// deba@2547: /// This method returns PRE_HEAP if \c item has never been in the deba@2547: /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP deba@2547: /// otherwise. In the latter case it is possible that \c item will deba@2547: /// get back to the heap again. deba@2547: State state(const Item &item) const { deba@2547: int i=iimap[item]; deba@2547: if( i>=0 ) { deba@2547: if ( container[i].in ) i=0; deba@2547: else i=-2; deba@2547: } deba@2547: return State(i); deba@2547: } deba@2547: deba@2547: /// \brief Sets the state of the \c item in the heap. deba@2547: /// deba@2547: /// Sets the state of the \c item in the heap. It can be used to deba@2547: /// manually clear the heap when it is important to achive the deba@2547: /// better time complexity. deba@2547: /// \param i The item. deba@2547: /// \param st The state. It should not be \c IN_HEAP. deba@2547: void state(const Item& i, State st) { deba@2547: switch (st) { deba@2547: case POST_HEAP: deba@2547: case PRE_HEAP: deba@2547: if (state(i) == IN_HEAP) { deba@2547: erase(i); deba@2547: } deba@2547: iimap[i] = st; deba@2547: break; deba@2547: case IN_HEAP: deba@2547: break; deba@2547: } deba@2547: } deba@2547: deba@2547: private: deba@2547: deba@2547: void balance() { deba@2547: deba@2547: int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; alpar@255: deba@2547: std::vector A(maxdeg,-1); alpar@255: deba@2547: /* deba@2547: *Recall that now minimum does not point to the minimum prio element. deba@2547: *We set minimum to this during balance(). deba@2547: */ deba@2547: int anchor=container[minimum].left_neighbor; deba@2547: int next=minimum; deba@2547: bool end=false; alpar@255: deba@2547: 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; deba@2547: } while ( !end ); alpar@255: alpar@255: deba@2547: while ( container[minimum].parent >=0 ) deba@2547: minimum=container[minimum].parent; deba@2547: int s=minimum; deba@2547: int m=minimum; deba@2547: do { deba@2547: if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; deba@2547: s=container[s].right_neighbor; deba@2547: } while ( s != m ); alpar@255: } alpar@255: deba@2547: void makeroot(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: } deba@2547: deba@2547: void cut(int a, int b) { deba@2547: /* deba@2547: *Replacing a from the children of b. deba@2547: */ deba@2547: --container[b].degree; alpar@255: deba@2547: if ( container[b].degree !=0 ) { deba@2547: int child=container[b].child; deba@2547: if ( child==a ) deba@2547: container[b].child=container[child].right_neighbor; deba@2547: unlace(a); deba@2547: } deba@2547: deba@2547: deba@2547: /*Lacing a to the roots.*/ deba@2547: int right=container[minimum].right_neighbor; deba@2547: container[minimum].right_neighbor=a; deba@2547: container[a].left_neighbor=minimum; deba@2547: container[a].right_neighbor=right; deba@2547: container[right].left_neighbor=a; deba@2547: deba@2547: container[a].parent=-1; deba@2547: container[a].marked=false; jacint@387: } alpar@255: deba@2547: void cascade(int a) { 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: deba@2547: void fuse(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: deba@2547: /* deba@2547: *It is invoked only if a has siblings. deba@2547: */ deba@2547: void unlace(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; deba@2547: } deba@2547: deba@2547: deba@2547: class store { deba@2547: friend class FibHeap; deba@2547: deba@2547: Item name; deba@2547: int parent; deba@2547: int left_neighbor; deba@2547: int right_neighbor; deba@2547: int child; deba@2547: int degree; deba@2547: bool marked; deba@2547: bool in; deba@2547: Prio prio; deba@2547: deba@2547: store() : parent(-1), child(-1), degree(), marked(false), in(true) {} deba@2547: }; deba@2547: }; alpar@430: alpar@921: } //namespace lemon alpar@477: alpar@921: #endif //LEMON_FIB_HEAP_H alpar@477: