COIN-OR::LEMON - Graph Library

Changeset 857:4e948fd205f7 in lemon-0.x


Ignore:
Timestamp:
09/15/04 16:04:57 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1157
Message:

docs changes

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/fib_heap.h

    r539 r857  
    44#define HUGO_FIB_HEAP_H
    55
     6///\file
    67///\ingroup auxdat
    7 ///\file
    88///\brief Fibonacci Heap implementation.
    99
     
    1717  /// @{
    1818
    19   /// An implementation of the Fibonacci Heap.
    20 
    21   /**
    22      This class implements the \e Fibonacci \e heap data structure. A \e heap
    23      is a data structure for storing items with specified values called \e
    24      priorities, such that finding the item with minimum priority with respect
    25      to \e Compare is efficient. In a heap one can change the priority of an
    26      item, add or erase an item, etc.
    27 
    28      The methods \ref increase and \ref erase are not efficient in a Fibonacci
    29      heap. In case of many calls to these operations, it is better to use a
    30      \e binary \e heap.
    31      
    32      \param Item The type of the items to be stored. 
    33      \param Prio The type of the priority of the items.
    34      \param ItemIntMap A read and writable Item int map, for the usage of
    35      the heap.
    36      \param Compare A class for the comparison of the priorities. The
    37      default is \c std::less<Prio>.
    38 
    39   */
    40 
     19  /// Fibonacci Heap.
     20
     21  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
     22  ///is a data structure for storing items with specified values called \e
     23  ///priorities in such a way that finding the item with minimum priority is
     24  ///efficient. \ref Compare specifies the ordering of the priorities. In a heap
     25  ///one can change the priority of an item, add or erase an item, etc.
     26  ///
     27  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
     28  ///heap. In case of many calls to these operations, it is better to use a
     29  ///\e binary \e heap.
     30  ///
     31  ///\param Item Type of the items to be stored. 
     32  ///\param Prio Type of the priority of the items.
     33  ///\param ItemIntMap A read and writable Item int map, for the usage of
     34  ///the heap.
     35  ///\param Compare A class for the ordering of the priorities. The
     36  ///default is \c std::less<Prio>.
     37  ///
     38  ///\author Jacint Szabo
     39 
    4140#ifdef DOXYGEN
    4241  template <typename Item,
     
    8483   
    8584    /**
    86        Returns \c true iff the heap stores no items.
     85       Returns \c true if and only if the heap stores no items.
    8786    */
    8887    bool empty() const { return num_items==0; }
     
    105104    void push (Item const item, PrioType const value);
    106105   
    107    
    108     ///Returns the item having the minimum priority w.r.t.  Compare.
    109    
    110     /**
    111        This method returns the item having the minimum priority w.r.t.  Compare.
     106    ///Returns the item with minimum priority relative to \ref Compare.
     107   
     108    /**
     109       This method returns the item with minimum priority relative to \ref
     110       Compare. 
     111       \pre The heap must be nonempty. 
     112    */
     113    Item top() const { return container[minimum].name; }
     114
     115    ///Returns the minimum priority relative to \ref Compare.
     116
     117    /**
     118       It returns the minimum priority relative to \ref Compare.
    112119       \pre The heap must be nonempty.
    113120    */
    114     Item top() const { return container[minimum].name; }
    115    
    116 
    117     ///Returns the minimum priority w.r.t.  Compare.
    118 
    119     /**
    120        It returns the minimum priority w.r.t.  Compare.
    121        \pre The heap must be nonempty.
    122     */
    123121    PrioType prio() const { return container[minimum].prio; }
    124122   
    125 
    126123    ///Returns the priority of \c item.
    127124
     125    /**
     126       This function returns the priority of \c item.
     127       \pre \c item must be in the heap.
     128    */
     129    PrioType& operator[](const Item& item) {
     130      return container[iimap[item]].prio;
     131    }
     132   
     133    ///Returns the priority of \c item.
     134   
    128135    /**
    129136       It returns the priority of \c item.
    130137       \pre \c item must be in the heap.
    131138    */
    132     PrioType& operator[](const Item& item) {
    133       return container[iimap[item]].prio;
    134     }
    135    
    136     ///Returns the priority of \c item.
    137    
    138     /**
    139        It returns the priority of \c item.
    140        \pre \c item must be in the heap.
    141     */
    142139    const PrioType& operator[](const Item& item) const {
    143140      return container[iimap[item]].prio;
     
    145142
    146143
    147     ///Deletes the item with minimum priority w.r.t. Compare.
    148 
    149     /**
    150     This method deletes the item with minimum priority w.r.t.
    151     Compare from the heap.
    152     \pre The heap must be non-empty.
     144    ///Deletes the item with minimum priority relative to \ref Compare.
     145
     146    /**
     147    This method deletes the item with minimum priority relative to \ref
     148    Compare from the heap. 
     149    \pre The heap must be non-empty. 
    153150    */
    154151    void pop();
     
    167164       This method decreases the priority of \c item to \c value.
    168165       \pre \c item must be stored in the heap with priority at least \c
    169        value w.r.t. Compare.
     166       value relative to \ref Compare.
    170167    */
    171168    void decrease (Item item, PrioType const value);
    172 
    173169
    174170    ///Increases the priority of \c item to \c value.
     
    177173       This method sets the priority of \c item to \c value. Though
    178174       there is no precondition on the priority of \c item, this
    179        method should be used only if there is a need to really \e increase
    180        (w.r.t. Compare) the priority of \c item, because this
     175       method should be used only if it is indeed necessary to increase
     176       (relative to \ref Compare) the priority of \c item, because this
    181177       method is inefficient.
    182178    */
     
    187183
    188184
    189     ///Tells if \c item is in, was already in, or has never been in the heap.
     185    ///Returns if \c item is in, has already been in, or has never been in the heap.
    190186
    191187    /**
Note: See TracChangeset for help on using the changeset viewer.