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

    r730 r758  
    2121
    2222///\file
    23 ///\ingroup auxdat
    24 ///\brief Fibonacci Heap implementation.
     23///\ingroup heaps
     24///\brief Fibonacci heap implementation.
    2525
    2626#include <vector>
     27#include <utility>
    2728#include <functional>
    2829#include <lemon/math.h>
    … …  
    3031namespace lemon {
    3132
    32   /// \ingroup auxdat
     33  /// \ingroup heaps
    3334  ///
    34   ///\brief Fibonacci Heap.
     35  /// \brief Fibonacci heap data structure.
    3536  ///
    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.
     37  /// This class implements the \e Fibonacci \e heap data structure.
     38  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4139  ///
    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".
     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".
    4543  ///
    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
     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>.
    5449#ifdef DOXYGEN
    55   template <typename PRIO, typename IM, typename CMP>
     50  template <typename PR, typename IM, typename CMP>
    5651#else
    57   template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
     52  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5853#endif
    5954  class FibHeap {
    6055  public:
    61     ///\e
     56
     57    /// Type of the item-int map.
    6258    typedef IM ItemIntMap;
    63     ///\e
    64     typedef PRIO Prio;
    65     ///\e
     59    /// Type of the priorities.
     60    typedef PR Prio;
     61    /// Type of the items stored in the heap.
    6662    typedef typename ItemIntMap::Key Item;
    67     ///\e
     63    /// Type of the item-priority pairs.
    6864    typedef std::pair<Item,Prio> Pair;
    69     ///\e
     65    /// Functor type for comparing the priorities.
    7066    typedef CMP Compare;
    7167
    … …  
    8177  public:
    8278
    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
     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
    8783    /// heap's point of view, but may be useful to the user.
    8884    ///
    … …  
    9591    };
    9692
    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.
     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.
    10199    explicit FibHeap(ItemIntMap &map)
    102100      : _minimum(0), _iim(map), _num() {}
    103101
    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.
     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.
    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     /// Returns the number of items stored in the heap.
     114    /// This function returns the number of items stored in the heap.
    115115    int size() const { return _num; }
    116116
    117     /// \brief Checks if the heap stores no items.
    118     ///
    119     ///   Returns \c true if and only if the heap stores no items.
     117    /// \brief Check if the heap is empty.
     118    ///
     119    /// This function returns \c true if the heap is empty.
    120120    bool empty() const { return _num==0; }
    121121
    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.
     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.
    128129    void clear() {
    129130      _data.clear(); _minimum = 0; _num = 0;
    130131    }
    131132
    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) {
     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) {
    151141      int i=_iim[item];
    152142      if ( i < 0 ) {
    … …  
    169159        _data[_minimum].right_neighbor=i;
    170160        _data[i].left_neighbor=_minimum;
    171         if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
     161        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
    172162      } else {
    173163        _data[i].right_neighbor=_data[i].left_neighbor=i;
    174164        _minimum=i;
    175165      }
    176       _data[i].prio=value;
     166      _data[i].prio=prio;
    177167      ++_num;
    178168    }
    179169
    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.
     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.
    185174    Item top() const { return _data[_minimum].name; }
    186175
    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.
     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.
    205185    /// \pre The heap must be non-empty.
    206186    void pop() {
    … …  
    209189        _data[_minimum].in=false;
    210190        if ( _data[_minimum].degree!=0 ) {
    211           makeroot(_data[_minimum].child);
     191          makeRoot(_data[_minimum].child);
    212192          _minimum=_data[_minimum].child;
    213193          balance();
    … …  
    222202          int last_child=_data[child].left_neighbor;
    223203
    224           makeroot(child);
     204          makeRoot(child);
    225205
    226206          _data[left].right_neighbor=child;
    … …  
    235215    }
    236216
    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.
     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.
    241223    void erase (const Item& item) {
    242224      int i=_iim[item];
    … …  
    253235    }
    254236
    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) {
     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) {
    261255      int i=_iim[item];
    262       _data[i].prio=value;
     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;
    263271      int p=_data[i].parent;
    264272
    265       if ( p!=-1 && _comp(value, _data[p].prio) ) {
     273      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
    266274        cut(i,p);
    267275        cascade(p);
    268276      }
    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) {
     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) {
    280287      erase(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.
     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.
    292299    State state(const Item &item) const {
    293300      int i=_iim[item];
    … …  
    299306    }
    300307
    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.
     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.
    306313    /// \param i The item.
    307314    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    366373    }
    367374
    368     void makeroot(int c) {
     375    void makeRoot(int c) {
    369376      int s=c;
    370377      do {
Note: See TracChangeset for help on using the changeset viewer.