deba@681: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@681: * deba@681: * This file is a part of LEMON, a generic C++ optimization library. deba@681: * deba@681: * Copyright (C) 2003-2009 deba@681: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@681: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@681: * deba@681: * Permission to use, modify and distribute this software is granted deba@681: * provided that this copyright notice appears in all copies. For deba@681: * precise terms see the accompanying LICENSE file. deba@681: * deba@681: * This software is provided "AS IS" with no warranty of any kind, deba@681: * express or implied, and with no claim as to its suitability for any deba@681: * purpose. deba@681: * deba@681: */ deba@681: deba@681: #ifndef LEMON_FIB_HEAP_H deba@681: #define LEMON_FIB_HEAP_H deba@681: deba@681: ///\file kpeter@710: ///\ingroup heaps kpeter@709: ///\brief Fibonacci heap implementation. deba@681: deba@681: #include kpeter@709: #include deba@681: #include deba@681: #include deba@681: deba@681: namespace lemon { deba@681: kpeter@710: /// \ingroup heaps deba@681: /// kpeter@709: /// \brief Fibonacci heap data structure. deba@681: /// kpeter@709: /// This class implements the \e Fibonacci \e heap data structure. kpeter@709: /// It fully conforms to the \ref concepts::Heap "heap concept". deba@681: /// kpeter@709: /// The methods \ref increase() and \ref erase() are not efficient in a kpeter@709: /// Fibonacci heap. In case of many calls of these operations, it is kpeter@709: /// better to use other heap structure, e.g. \ref BinHeap "binary heap". deba@681: /// kpeter@709: /// \tparam PR Type of the priorities of the items. kpeter@709: /// \tparam IM A read-writable item map with \c int values, used kpeter@709: /// internally to handle the cross references. kpeter@709: /// \tparam CMP A functor class for comparing the priorities. kpeter@709: /// The default is \c std::less. deba@681: #ifdef DOXYGEN kpeter@709: template deba@681: #else kpeter@709: template > deba@681: #endif deba@681: class FibHeap { deba@681: public: kpeter@709: kpeter@709: /// Type of the item-int map. deba@683: typedef IM ItemIntMap; kpeter@709: /// Type of the priorities. kpeter@709: typedef PR Prio; kpeter@709: /// Type of the items stored in the heap. deba@681: typedef typename ItemIntMap::Key Item; kpeter@709: /// Type of the item-priority pairs. deba@681: typedef std::pair Pair; kpeter@709: /// Functor type for comparing the priorities. deba@683: typedef CMP Compare; deba@681: deba@681: private: deba@683: class Store; deba@681: deba@683: std::vector _data; deba@683: int _minimum; deba@683: ItemIntMap &_iim; deba@683: Compare _comp; deba@683: int _num; deba@681: deba@681: public: deba@683: kpeter@709: /// \brief Type to represent the states of the items. deba@683: /// kpeter@709: /// Each item has a state associated to it. It can be "in heap", kpeter@709: /// "pre-heap" or "post-heap". The latter two are indifferent from the deba@683: /// heap's point of view, but may be useful to the user. deba@683: /// deba@683: /// The item-int map must be initialized in such way that it assigns deba@683: /// \c PRE_HEAP (-1) to any element to be put in the heap. deba@681: enum State { deba@683: IN_HEAP = 0, ///< = 0. deba@683: PRE_HEAP = -1, ///< = -1. deba@683: POST_HEAP = -2 ///< = -2. deba@681: }; deba@681: kpeter@709: /// \brief Constructor. deba@681: /// kpeter@709: /// Constructor. kpeter@709: /// \param map A map that assigns \c int values to the items. kpeter@709: /// It is used internally to handle the cross references. kpeter@709: /// The assigned value must be \c PRE_HEAP (-1) for each item. deba@683: explicit FibHeap(ItemIntMap &map) deba@683: : _minimum(0), _iim(map), _num() {} deba@681: kpeter@709: /// \brief Constructor. deba@681: /// kpeter@709: /// Constructor. kpeter@709: /// \param map A map that assigns \c int values to the items. kpeter@709: /// It is used internally to handle the cross references. kpeter@709: /// The assigned value must be \c PRE_HEAP (-1) for each item. kpeter@709: /// \param comp The function object used for comparing the priorities. deba@683: FibHeap(ItemIntMap &map, const Compare &comp) deba@683: : _minimum(0), _iim(map), _comp(comp), _num() {} deba@681: deba@681: /// \brief The number of items stored in the heap. deba@681: /// kpeter@709: /// This function returns the number of items stored in the heap. deba@683: int size() const { return _num; } deba@681: kpeter@709: /// \brief Check if the heap is empty. deba@681: /// kpeter@709: /// This function returns \c true if the heap is empty. deba@683: bool empty() const { return _num==0; } deba@681: kpeter@709: /// \brief Make the heap empty. deba@681: /// kpeter@709: /// This functon makes the heap empty. kpeter@709: /// It does not change the cross reference map. If you want to reuse kpeter@709: /// a heap that is not surely empty, you should first clear it and kpeter@709: /// then you should set the cross reference map to \c PRE_HEAP kpeter@709: /// for each item. deba@681: void clear() { deba@683: _data.clear(); _minimum = 0; _num = 0; deba@681: } deba@681: kpeter@709: /// \brief Insert an item into the heap with the given priority. deba@681: /// kpeter@709: /// This function inserts the given item into the heap with the kpeter@709: /// given priority. kpeter@709: /// \param item The item to insert. kpeter@709: /// \param prio The priority of the item. kpeter@709: /// \pre \e item must not be stored in the heap. kpeter@709: void push (const Item& item, const Prio& prio) { deba@683: int i=_iim[item]; deba@681: if ( i < 0 ) { deba@683: int s=_data.size(); deba@683: _iim.set( item, s ); deba@683: Store st; deba@681: st.name=item; deba@683: _data.push_back(st); deba@681: i=s; deba@681: } else { deba@683: _data[i].parent=_data[i].child=-1; deba@683: _data[i].degree=0; deba@683: _data[i].in=true; deba@683: _data[i].marked=false; deba@681: } deba@681: deba@683: if ( _num ) { deba@683: _data[_data[_minimum].right_neighbor].left_neighbor=i; deba@683: _data[i].right_neighbor=_data[_minimum].right_neighbor; deba@683: _data[_minimum].right_neighbor=i; deba@683: _data[i].left_neighbor=_minimum; kpeter@709: if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; deba@681: } else { deba@683: _data[i].right_neighbor=_data[i].left_neighbor=i; deba@683: _minimum=i; deba@681: } kpeter@709: _data[i].prio=prio; deba@683: ++_num; deba@681: } deba@681: kpeter@709: /// \brief Return the item having minimum priority. deba@681: /// kpeter@709: /// This function returns the item having minimum priority. kpeter@709: /// \pre The heap must be non-empty. deba@683: Item top() const { return _data[_minimum].name; } deba@681: kpeter@709: /// \brief The minimum priority. deba@681: /// kpeter@709: /// This function returns the minimum priority. kpeter@709: /// \pre The heap must be non-empty. kpeter@709: Prio prio() const { return _data[_minimum].prio; } deba@681: kpeter@709: /// \brief Remove the item having minimum priority. deba@681: /// kpeter@709: /// This function removes the item having minimum priority. deba@681: /// \pre The heap must be non-empty. deba@681: void pop() { deba@681: /*The first case is that there are only one root.*/ deba@683: if ( _data[_minimum].left_neighbor==_minimum ) { deba@683: _data[_minimum].in=false; deba@683: if ( _data[_minimum].degree!=0 ) { kpeter@711: makeRoot(_data[_minimum].child); deba@683: _minimum=_data[_minimum].child; deba@681: balance(); deba@681: } deba@681: } else { deba@683: int right=_data[_minimum].right_neighbor; deba@683: unlace(_minimum); deba@683: _data[_minimum].in=false; deba@683: if ( _data[_minimum].degree > 0 ) { deba@683: int left=_data[_minimum].left_neighbor; deba@683: int child=_data[_minimum].child; deba@683: int last_child=_data[child].left_neighbor; deba@681: kpeter@711: makeRoot(child); deba@681: deba@683: _data[left].right_neighbor=child; deba@683: _data[child].left_neighbor=left; deba@683: _data[right].left_neighbor=last_child; deba@683: _data[last_child].right_neighbor=right; deba@681: } deba@683: _minimum=right; deba@681: balance(); deba@681: } // the case where there are more roots deba@683: --_num; deba@681: } deba@681: kpeter@709: /// \brief Remove the given item from the heap. deba@681: /// kpeter@709: /// This function removes the given item from the heap if it is kpeter@709: /// already stored. kpeter@709: /// \param item The item to delete. kpeter@709: /// \pre \e item must be in the heap. deba@681: void erase (const Item& item) { deba@683: int i=_iim[item]; deba@681: deba@683: if ( i >= 0 && _data[i].in ) { deba@683: if ( _data[i].parent!=-1 ) { deba@683: int p=_data[i].parent; deba@681: cut(i,p); deba@681: cascade(p); deba@681: } deba@683: _minimum=i; //As if its prio would be -infinity deba@681: pop(); deba@681: } deba@681: } deba@681: kpeter@709: /// \brief The priority of the given item. deba@681: /// kpeter@709: /// This function returns the priority of the given item. kpeter@709: /// \param item The item. kpeter@709: /// \pre \e item must be in the heap. kpeter@709: Prio operator[](const Item& item) const { kpeter@709: return _data[_iim[item]].prio; kpeter@709: } kpeter@709: kpeter@709: /// \brief Set the priority of an item or insert it, if it is kpeter@709: /// not stored in the heap. kpeter@709: /// kpeter@709: /// This method sets the priority of the given item if it is kpeter@709: /// already stored in the heap. Otherwise it inserts the given kpeter@709: /// item into the heap with the given priority. kpeter@709: /// \param item The item. kpeter@709: /// \param prio The priority. kpeter@709: void set (const Item& item, const Prio& prio) { deba@683: int i=_iim[item]; kpeter@709: if ( i >= 0 && _data[i].in ) { kpeter@709: if ( _comp(prio, _data[i].prio) ) decrease(item, prio); kpeter@709: if ( _comp(_data[i].prio, prio) ) increase(item, prio); kpeter@709: } else push(item, prio); kpeter@709: } kpeter@709: kpeter@709: /// \brief Decrease the priority of an item to the given value. kpeter@709: /// kpeter@709: /// This function decreases the priority of an item to the given value. kpeter@709: /// \param item The item. kpeter@709: /// \param prio The priority. kpeter@709: /// \pre \e item must be stored in the heap with priority at least \e prio. kpeter@709: void decrease (const Item& item, const Prio& prio) { kpeter@709: int i=_iim[item]; kpeter@709: _data[i].prio=prio; deba@683: int p=_data[i].parent; deba@681: kpeter@709: if ( p!=-1 && _comp(prio, _data[p].prio) ) { deba@681: cut(i,p); deba@681: cascade(p); deba@681: } kpeter@709: if ( _comp(prio, _data[_minimum].prio) ) _minimum=i; deba@681: } deba@681: kpeter@709: /// \brief Increase the priority of an item to the given value. deba@681: /// kpeter@709: /// This function increases the priority of an item to the given value. kpeter@709: /// \param item The item. kpeter@709: /// \param prio The priority. kpeter@709: /// \pre \e item must be stored in the heap with priority at most \e prio. kpeter@709: void increase (const Item& item, const Prio& prio) { deba@681: erase(item); kpeter@709: push(item, prio); deba@681: } deba@681: kpeter@709: /// \brief Return the state of an item. deba@681: /// kpeter@709: /// This method returns \c PRE_HEAP if the given item has never kpeter@709: /// been in the heap, \c IN_HEAP if it is in the heap at the moment, kpeter@709: /// and \c POST_HEAP otherwise. kpeter@709: /// In the latter case it is possible that the item will get back kpeter@709: /// to the heap again. kpeter@709: /// \param item The item. deba@681: State state(const Item &item) const { deba@683: int i=_iim[item]; deba@681: if( i>=0 ) { deba@683: if ( _data[i].in ) i=0; deba@681: else i=-2; deba@681: } deba@681: return State(i); deba@681: } deba@681: kpeter@709: /// \brief Set the state of an item in the heap. deba@681: /// kpeter@709: /// This function sets the state of the given item in the heap. kpeter@709: /// It can be used to manually clear the heap when it is important kpeter@709: /// to achive better time complexity. deba@681: /// \param i The item. deba@681: /// \param st The state. It should not be \c IN_HEAP. deba@681: void state(const Item& i, State st) { deba@681: switch (st) { deba@681: case POST_HEAP: deba@681: case PRE_HEAP: deba@681: if (state(i) == IN_HEAP) { deba@681: erase(i); deba@681: } deba@683: _iim[i] = st; deba@681: break; deba@681: case IN_HEAP: deba@681: break; deba@681: } deba@681: } deba@681: deba@681: private: deba@681: deba@681: void balance() { deba@681: deba@683: int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1; deba@681: deba@681: std::vector A(maxdeg,-1); deba@681: deba@681: /* deba@681: *Recall that now minimum does not point to the minimum prio element. deba@681: *We set minimum to this during balance(). deba@681: */ deba@683: int anchor=_data[_minimum].left_neighbor; deba@683: int next=_minimum; deba@681: bool end=false; deba@681: deba@681: do { deba@681: int active=next; deba@681: if ( anchor==active ) end=true; deba@683: int d=_data[active].degree; deba@683: next=_data[active].right_neighbor; deba@681: deba@681: while (A[d]!=-1) { deba@683: if( _comp(_data[active].prio, _data[A[d]].prio) ) { deba@681: fuse(active,A[d]); deba@681: } else { deba@681: fuse(A[d],active); deba@681: active=A[d]; deba@681: } deba@681: A[d]=-1; deba@681: ++d; deba@681: } deba@681: A[d]=active; deba@681: } while ( !end ); deba@681: deba@681: deba@683: while ( _data[_minimum].parent >=0 ) deba@683: _minimum=_data[_minimum].parent; deba@683: int s=_minimum; deba@683: int m=_minimum; deba@681: do { deba@683: if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s; deba@683: s=_data[s].right_neighbor; deba@681: } while ( s != m ); deba@681: } deba@681: kpeter@711: void makeRoot(int c) { deba@681: int s=c; deba@681: do { deba@683: _data[s].parent=-1; deba@683: s=_data[s].right_neighbor; deba@681: } while ( s != c ); deba@681: } deba@681: deba@681: void cut(int a, int b) { deba@681: /* deba@681: *Replacing a from the children of b. deba@681: */ deba@683: --_data[b].degree; deba@681: deba@683: if ( _data[b].degree !=0 ) { deba@683: int child=_data[b].child; deba@681: if ( child==a ) deba@683: _data[b].child=_data[child].right_neighbor; deba@681: unlace(a); deba@681: } deba@681: deba@681: deba@681: /*Lacing a to the roots.*/ deba@683: int right=_data[_minimum].right_neighbor; deba@683: _data[_minimum].right_neighbor=a; deba@683: _data[a].left_neighbor=_minimum; deba@683: _data[a].right_neighbor=right; deba@683: _data[right].left_neighbor=a; deba@681: deba@683: _data[a].parent=-1; deba@683: _data[a].marked=false; deba@681: } deba@681: deba@681: void cascade(int a) { deba@683: if ( _data[a].parent!=-1 ) { deba@683: int p=_data[a].parent; deba@681: deba@683: if ( _data[a].marked==false ) _data[a].marked=true; deba@681: else { deba@681: cut(a,p); deba@681: cascade(p); deba@681: } deba@681: } deba@681: } deba@681: deba@681: void fuse(int a, int b) { deba@681: unlace(b); deba@681: deba@681: /*Lacing b under a.*/ deba@683: _data[b].parent=a; deba@681: deba@683: if (_data[a].degree==0) { deba@683: _data[b].left_neighbor=b; deba@683: _data[b].right_neighbor=b; deba@683: _data[a].child=b; deba@681: } else { deba@683: int child=_data[a].child; deba@683: int last_child=_data[child].left_neighbor; deba@683: _data[child].left_neighbor=b; deba@683: _data[b].right_neighbor=child; deba@683: _data[last_child].right_neighbor=b; deba@683: _data[b].left_neighbor=last_child; deba@681: } deba@681: deba@683: ++_data[a].degree; deba@681: deba@683: _data[b].marked=false; deba@681: } deba@681: deba@681: /* deba@681: *It is invoked only if a has siblings. deba@681: */ deba@681: void unlace(int a) { deba@683: int leftn=_data[a].left_neighbor; deba@683: int rightn=_data[a].right_neighbor; deba@683: _data[leftn].right_neighbor=rightn; deba@683: _data[rightn].left_neighbor=leftn; deba@681: } deba@681: deba@681: deba@683: class Store { deba@681: friend class FibHeap; deba@681: deba@681: Item name; deba@681: int parent; deba@681: int left_neighbor; deba@681: int right_neighbor; deba@681: int child; deba@681: int degree; deba@681: bool marked; deba@681: bool in; deba@681: Prio prio; deba@681: deba@683: Store() : parent(-1), child(-1), degree(), marked(false), in(true) {} deba@681: }; deba@681: }; deba@681: deba@681: } //namespace lemon deba@681: deba@681: #endif //LEMON_FIB_HEAP_H deba@681: