COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/fib_heap.h

    r758 r730  
    2121
    2222///\file
    23 ///\ingroup heaps
    24 ///\brief Fibonacci heap implementation.
     23///\ingroup auxdat
     24///\brief Fibonacci Heap implementation.
    2525
    2626#include <vector>
    27 #include <utility>
    2827#include <functional>
    2928#include <lemon/math.h>
    … …  
    3130namespace lemon {
    3231
    33   /// \ingroup heaps
     32  /// \ingroup auxdat
    3433  ///
    35   /// \brief Fibonacci heap data structure.
     34  ///\brief Fibonacci Heap.
    3635  ///
    37   /// This class implements the \e Fibonacci \e heap data structure.
    38   /// It fully conforms to the \ref concepts::Heap "heap concept".
     36  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
     37  ///is a data structure for storing items with specified values called \e
     38  ///priorities in such a way that finding the item with minimum priority is
     39  ///efficient. \c CMP specifies the ordering of the priorities. In a heap
     40  ///one can change the priority of an item, add or erase an item, etc.
    3941  ///
    40   /// The methods \ref increase() and \ref erase() are not efficient in a
    41   /// Fibonacci heap. In case of many calls of these operations, it is
    42   /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
     42  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
     43  ///heap. In case of many calls to these operations, it is better to use a
     44  ///\ref BinHeap "binary heap".
    4345  ///
    44   /// \tparam PR Type of the priorities of the items.
    45   /// \tparam IM A read-writable item map with \c int values, used
    46   /// internally to handle the cross references.
    47   /// \tparam CMP A functor class for comparing the priorities.
    48   /// The default is \c std::less<PR>.
     46  ///\param PRIO Type of the priority of the items.
     47  ///\param IM A read and writable Item int map, used internally
     48  ///to handle the cross references.
     49  ///\param CMP A class for the ordering of the priorities. The
     50  ///default is \c std::less<PRIO>.
     51  ///
     52  ///\sa BinHeap
     53  ///\sa Dijkstra
    4954#ifdef DOXYGEN
    50   template <typename PR, typename IM, typename CMP>
     55  template <typename PRIO, typename IM, typename CMP>
    5156#else
    52   template <typename PR, typename IM, typename CMP = std::less<PR> >
     57  template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
    5358#endif
    5459  class FibHeap {
    5560  public:
    56 
    57     /// Type of the item-int map.
     61    ///\e
    5862    typedef IM ItemIntMap;
    59     /// Type of the priorities.
    60     typedef PR Prio;
    61     /// Type of the items stored in the heap.
     63    ///\e
     64    typedef PRIO Prio;
     65    ///\e
    6266    typedef typename ItemIntMap::Key Item;
    63     /// Type of the item-priority pairs.
     67    ///\e
    6468    typedef std::pair<Item,Prio> Pair;
    65     /// Functor type for comparing the priorities.
     69    ///\e
    6670    typedef CMP Compare;
    6771
    … …  
    7781  public:
    7882
    79     /// \brief Type to represent the states of the items.
    80     ///
    81     /// Each item has a state associated to it. It can be "in heap",
    82     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     83    /// \brief Type to represent the items states.
     84    ///
     85    /// Each Item element have a state associated to it. It may be "in heap",
     86    /// "pre heap" or "post heap". The latter two are indifferent from the
    8387    /// heap's point of view, but may be useful to the user.
    8488    ///
    … …  
    9195    };
    9296
    93     /// \brief Constructor.
    94     ///
    95     /// Constructor.
    96     /// \param map A map that assigns \c int values to the items.
    97     /// It is used internally to handle the cross references.
    98     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     97    /// \brief The constructor
     98    ///
     99    /// \c map should be given to the constructor, since it is
     100    ///   used internally to handle the cross references.
    99101    explicit FibHeap(ItemIntMap &map)
    100102      : _minimum(0), _iim(map), _num() {}
    101103
    102     /// \brief Constructor.
    103     ///
    104     /// Constructor.
    105     /// \param map A map that assigns \c int values to the items.
    106     /// It is used internally to handle the cross references.
    107     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    108     /// \param comp The function object used for comparing the priorities.
     104    /// \brief The constructor
     105    ///
     106    /// \c map should be given to the constructor, since it is used
     107    /// internally to handle the cross references. \c comp is an
     108    /// object for ordering of the priorities.
    109109    FibHeap(ItemIntMap &map, const Compare &comp)
    110110      : _minimum(0), _iim(map), _comp(comp), _num() {}
    … …  
    112112    /// \brief The number of items stored in the heap.
    113113    ///
    114     /// This function returns the number of items stored in the heap.
     114    /// Returns the number of items stored in the heap.
    115115    int size() const { return _num; }
    116116
    117     /// \brief Check if the heap is empty.
    118     ///
    119     /// This function returns \c true if the heap is empty.
     117    /// \brief Checks if the heap stores no items.
     118    ///
     119    ///   Returns \c true if and only if the heap stores no items.
    120120    bool empty() const { return _num==0; }
    121121
    122     /// \brief Make the heap empty.
    123     ///
    124     /// This functon makes the heap empty.
    125     /// It does not change the cross reference map. If you want to reuse
    126     /// a heap that is not surely empty, you should first clear it and
    127     /// then you should set the cross reference map to \c PRE_HEAP
    128     /// for each item.
     122    /// \brief Make empty this heap.
     123    ///
     124    /// Make empty this heap. It does not change the cross reference
     125    /// map.  If you want to reuse a heap what is not surely empty you
     126    /// should first clear the heap and after that you should set the
     127    /// cross reference map for each item to \c PRE_HEAP.
    129128    void clear() {
    130129      _data.clear(); _minimum = 0; _num = 0;
    131130    }
    132131
    133     /// \brief Insert an item into the heap with the given priority.
    134     ///
    135     /// This function inserts the given item into the heap with the
    136     /// given priority.
    137     /// \param item The item to insert.
    138     /// \param prio The priority of the item.
    139     /// \pre \e item must not be stored in the heap.
    140     void push (const Item& item, const Prio& prio) {
     132    /// \brief \c item gets to the heap with priority \c value independently
     133    /// if \c item was already there.
     134    ///
     135    /// This method calls \ref push(\c item, \c value) if \c item is not
     136    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
     137    /// \ref increase(\c item, \c value) otherwise.
     138    void set (const Item& item, const Prio& value) {
     139      int i=_iim[item];
     140      if ( i >= 0 && _data[i].in ) {
     141        if ( _comp(value, _data[i].prio) ) decrease(item, value);
     142        if ( _comp(_data[i].prio, value) ) increase(item, value);
     143      } else push(item, value);
     144    }
     145
     146    /// \brief Adds \c item to the heap with priority \c value.
     147    ///
     148    /// Adds \c item to the heap with priority \c value.
     149    /// \pre \c item must not be stored in the heap.
     150    void push (const Item& item, const Prio& value) {
    141151      int i=_iim[item];
    142152      if ( i < 0 ) {
    … …  
    159169        _data[_minimum].right_neighbor=i;
    160170        _data[i].left_neighbor=_minimum;
    161         if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
     171        if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
    162172      } else {
    163173        _data[i].right_neighbor=_data[i].left_neighbor=i;
    164174        _minimum=i;
    165175      }
    166       _data[i].prio=prio;
     176      _data[i].prio=value;
    167177      ++_num;
    168178    }
    169179
    170     /// \brief Return the item having minimum priority.
    171     ///
    172     /// This function returns the item having minimum priority.
    173     /// \pre The heap must be non-empty.
     180    /// \brief Returns the item with minimum priority relative to \c Compare.
     181    ///
     182    /// This method returns the item with minimum priority relative to \c
     183    /// Compare.
     184    /// \pre The heap must be nonempty.
    174185    Item top() const { return _data[_minimum].name; }
    175186
    176     /// \brief The minimum priority.
    177     ///
    178     /// This function returns the minimum priority.
    179     /// \pre The heap must be non-empty.
    180     Prio prio() const { return _data[_minimum].prio; }
    181 
    182     /// \brief Remove the item having minimum priority.
    183     ///
    184     /// This function removes the item having minimum priority.
     187    /// \brief Returns the minimum priority relative to \c Compare.
     188    ///
     189    /// It returns the minimum priority relative to \c Compare.
     190    /// \pre The heap must be nonempty.
     191    const Prio& prio() const { return _data[_minimum].prio; }
     192
     193    /// \brief Returns the priority of \c item.
     194    ///
     195    /// It returns the priority of \c item.
     196    /// \pre \c item must be in the heap.
     197    const Prio& operator[](const Item& item) const {
     198      return _data[_iim[item]].prio;
     199    }
     200
     201    /// \brief Deletes the item with minimum priority relative to \c Compare.
     202    ///
     203    /// This method deletes the item with minimum priority relative to \c
     204    /// Compare from the heap.
    185205    /// \pre The heap must be non-empty.
    186206    void pop() {
    … …  
    189209        _data[_minimum].in=false;
    190210        if ( _data[_minimum].degree!=0 ) {
    191           makeRoot(_data[_minimum].child);
     211          makeroot(_data[_minimum].child);
    192212          _minimum=_data[_minimum].child;
    193213          balance();
    … …  
    202222          int last_child=_data[child].left_neighbor;
    203223
    204           makeRoot(child);
     224          makeroot(child);
    205225
    206226          _data[left].right_neighbor=child;
    … …  
    215235    }
    216236
    217     /// \brief Remove the given item from the heap.
    218     ///
    219     /// This function removes the given item from the heap if it is
    220     /// already stored.
    221     /// \param item The item to delete.
    222     /// \pre \e item must be in the heap.
     237    /// \brief Deletes \c item from the heap.
     238    ///
     239    /// This method deletes \c item from the heap, if \c item was already
     240    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
    223241    void erase (const Item& item) {
    224242      int i=_iim[item];
    … …  
    235253    }
    236254
    237     /// \brief The priority of the given item.
    238     ///
    239     /// This function returns the priority of the given item.
    240     /// \param item The item.
    241     /// \pre \e item must be in the heap.
    242     Prio operator[](const Item& item) const {
    243       return _data[_iim[item]].prio;
    244     }
    245 
    246     /// \brief Set the priority of an item or insert it, if it is
    247     /// not stored in the heap.
    248     ///
    249     /// This method sets the priority of the given item if it is
    250     /// already stored in the heap. Otherwise it inserts the given
    251     /// item into the heap with the given priority.
    252     /// \param item The item.
    253     /// \param prio The priority.
    254     void set (const Item& item, const Prio& prio) {
     255    /// \brief Decreases the priority of \c item to \c value.
     256    ///
     257    /// This method decreases the priority of \c item to \c value.
     258    /// \pre \c item must be stored in the heap with priority at least \c
     259    ///   value relative to \c Compare.
     260    void decrease (Item item, const Prio& value) {
    255261      int i=_iim[item];
    256       if ( i >= 0 && _data[i].in ) {
    257         if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
    258         if ( _comp(_data[i].prio, prio) ) increase(item, prio);
    259       } else push(item, prio);
    260     }
    261 
    262     /// \brief Decrease the priority of an item to the given value.
    263     ///
    264     /// This function decreases the priority of an item to the given value.
    265     /// \param item The item.
    266     /// \param prio The priority.
    267     /// \pre \e item must be stored in the heap with priority at least \e prio.
    268     void decrease (const Item& item, const Prio& prio) {
    269       int i=_iim[item];
    270       _data[i].prio=prio;
     262      _data[i].prio=value;
    271263      int p=_data[i].parent;
    272264
    273       if ( p!=-1 && _comp(prio, _data[p].prio) ) {
     265      if ( p!=-1 && _comp(value, _data[p].prio) ) {
    274266        cut(i,p);
    275267        cascade(p);
    276268      }
    277       if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
    278     }
    279 
    280     /// \brief Increase the priority of an item to the given value.
    281     ///
    282     /// This function increases the priority of an item to the given value.
    283     /// \param item The item.
    284     /// \param prio The priority.
    285     /// \pre \e item must be stored in the heap with priority at most \e prio.
    286     void increase (const Item& item, const Prio& prio) {
     269      if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
     270    }
     271
     272    /// \brief Increases the priority of \c item to \c value.
     273    ///
     274    /// This method sets the priority of \c item to \c value. Though
     275    /// there is no precondition on the priority of \c item, this
     276    /// method should be used only if it is indeed necessary to increase
     277    /// (relative to \c Compare) the priority of \c item, because this
     278    /// method is inefficient.
     279    void increase (Item item, const Prio& value) {
    287280      erase(item);
    288       push(item, prio);
    289     }
    290 
    291     /// \brief Return the state of an item.
    292     ///
    293     /// This method returns \c PRE_HEAP if the given item has never
    294     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    295     /// and \c POST_HEAP otherwise.
    296     /// In the latter case it is possible that the item will get back
    297     /// to the heap again.
    298     /// \param item The item.
     281      push(item, value);
     282    }
     283
     284
     285    /// \brief Returns if \c item is in, has already been in, or has never
     286    /// been in the heap.
     287    ///
     288    /// This method returns PRE_HEAP if \c item has never been in the
     289    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     290    /// otherwise. In the latter case it is possible that \c item will
     291    /// get back to the heap again.
    299292    State state(const Item &item) const {
    300293      int i=_iim[item];
    … …  
    306299    }
    307300
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     301    /// \brief Sets the state of the \c item in the heap.
     302    ///
     303    /// Sets the state of the \c item in the heap. It can be used to
     304    /// manually clear the heap when it is important to achive the
     305    /// better time _complexity.
    313306    /// \param i The item.
    314307    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    373366    }
    374367
    375     void makeRoot(int c) {
     368    void makeroot(int c) {
    376369      int s=c;
    377370      do {
Note: See TracChangeset for help on using the changeset viewer.