COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1331:7e93d3f0406d in lemon-0.x


Ignore:
Timestamp:
04/09/05 21:30:49 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1770
Message:

Documentation improvments.

Location:
src/lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/lemon/bin_heap.h

    r1270 r1331  
    6060    typedef Compare                          PrioCompare;
    6161
    62     /**
    63      * Each Item element have a state associated to it. It may be "in heap",
    64      * "pre heap" or "post heap". The later two are indifferent from the
    65      * heap's point of view, but may be useful to the user.
    66      *
    67      * The ItemIntMap _should_ be initialized in such way, that it maps
    68      * PRE_HEAP (-1) to any element to be put in the heap...
    69      */
    70     ///\todo it is used nowhere
    71     ///
     62    /// \brief Type to represent the items states.
     63    ///
     64    /// Each Item element have a state associated to it. It may be "in heap",
     65    /// "pre heap" or "post heap". The later two are indifferent from the
     66    /// heap's point of view, but may be useful to the user.
     67    ///
     68    /// The ItemIntMap _should_ be initialized in such way, that it maps
     69    /// PRE_HEAP (-1) to any element to be put in the heap...
    7270    enum state_enum {
    7371      IN_HEAP = 0,
    … …  
    7977    std::vector<PairType> data;
    8078    Compare comp;
    81     // FIXME: jo ez igy???
    8279    ItemIntMap &iim;
    8380
    8481  public:
    85     ///The constructor
    86 
    87     /**
    88        \c _iim should be given to the constructor, since it is used
    89        internally to handle the cross references.
    90     */
     82    /// \brief The constructor.
     83    ///
     84    /// The constructor.
     85    /// \param _iim should be given to the constructor, since it is used
     86    /// internally to handle the cross references. The value of the map
     87    /// should be PRE_HEAP (-1) for each element.
    9188    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    9289   
    93     ///The constructor
    94 
    95     /**
    96        \c _iim should be given to the constructor, since it is used
    97        internally to handle the cross references. \c _comp is an
    98        object for ordering of the priorities.
    99     */
     90    /// \brief The constructor.
     91    ///
     92    /// The constructor.
     93    /// \param _iim should be given to the constructor, since it is used
     94    /// internally to handle the cross references. The value of the map
     95    /// should be PRE_HEAP (-1) for each element.
     96    ///
     97    /// \param _comp The comparator function object.
    10098    BinHeap(ItemIntMap &_iim, const Compare &_comp)
    10199      : iim(_iim), comp(_comp) {}
    102100
    103101
    104     ///The number of items stored in the heap.
    105 
    106     /**
    107        Returns the number of items stored in the heap.
    108     */
     102    /// The number of items stored in the heap.
     103    ///
     104    /// \brief Returns the number of items stored in the heap.
    109105    int size() const { return data.size(); }
    110106   
    111     ///Checks if the heap stores no items.
    112    
    113     /**
    114        Returns \c true if and only if the heap stores no items.
    115     */
     107    /// \brief Checks if the heap stores no items.
     108    ///
     109    /// Returns \c true if and only if the heap stores no items.
    116110    bool empty() const { return data.empty(); }
    117111
    … …  
    143137
    144138  public:
    145     ///Adds \c p.first to the heap with priority \c p.second.
    146    
    147     /**
    148        Adds \c p.first to the heap with priority \c p.second.
    149        \c p.first must not be stored in the heap.
    150     */
     139    /// \brief Insert a pair of item and priority into the heap.
     140    ///
     141    /// Adds \c p.first to the heap with priority \c p.second.
     142    /// \param p The pair to insert.
    151143    void push(const PairType &p) {
    152144      int n = data.size();
    … …  
    155147    }
    156148
    157     ///Adds \c i to the heap with priority \c p.
    158    
    159     /**
    160        Adds \c i to the heap with priority \c p.
    161        \pre \c i must not be stored in the heap.
    162     */
     149    /// \brief Insert an item into the heap with the given heap.
     150    ///   
     151    /// Adds \c i to the heap with priority \c p.
     152    /// \param i The item to insert.
     153    /// \param p The priority of the item.
    163154    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
    164155
    165     ///Returns the item with minimum priority relative to \c Compare.
    166    
    167     /**
    168        This method returns the item with minimum priority relative to \c
    169        Compare. 
    170        \pre The heap must be nonempty. 
    171     */
     156    /// \brief Returns the item with minimum priority relative to \c Compare.
     157    ///
     158    /// This method returns the item with minimum priority relative to \c
     159    /// Compare. 
     160    /// \pre The heap must be nonempty. 
    172161    Item top() const {
    173162      return data[0].first;
    174163    }
    175164
    176     ///Returns the minimum priority relative to \c Compare.
    177 
    178     /**
    179        It returns the minimum priority relative to \c Compare.
    180        \pre The heap must be nonempty.
    181     */
     165    /// \brief Returns the minimum priority relative to \c Compare.
     166    ///
     167    /// It returns the minimum priority relative to \c Compare.
     168    /// \pre The heap must be nonempty.
    182169    Prio prio() const {
    183170      return data[0].second;
    184171    }
    185172
    186     ///Deletes the item with minimum priority relative to \c Compare.
    187 
    188     /**
    189     This method deletes the item with minimum priority relative to \c
    190     Compare from the heap. 
    191     \pre The heap must be non-empty. 
    192     */
     173    /// \brief Deletes the item with minimum priority relative to \c Compare.
     174    ///
     175    /// This method deletes the item with minimum priority relative to \c
     176    /// Compare from the heap. 
     177    /// \pre The heap must be non-empty. 
    193178    void pop() {
    194179      rmidx(0);
    195180    }
    196181
    197     ///Deletes \c i from the heap.
    198 
    199     /**
    200        This method deletes item \c i from the heap, if \c i was
    201        already stored in the heap.
    202     */
     182    /// \brief Deletes \c i from the heap.
     183    ///
     184    /// This method deletes item \c i from the heap, if \c i was
     185    /// already stored in the heap.
     186    /// \param i The item to erase.
    203187    void erase(const Item &i) {
    204188      rmidx(iim[i]);
    … …  
    206190
    207191   
    208     ///Returns the priority of \c i.
    209 
    210     /**
    211        This function returns the priority of item \c i. 
    212        \pre \c i must be in the heap.
    213     */
     192    /// \brief Returns the priority of \c i.
     193    ///
     194    /// This function returns the priority of item \c i. 
     195    /// \pre \c i must be in the heap.
     196    /// \param i The item.
    214197    Prio operator[](const Item &i) const {
    215198      int idx = iim[i];
    … …  
    217200    }
    218201
    219     ///\c i gets to the heap with priority \c p independently if \c i was already there.
    220 
    221     /**
    222        This method calls \ref push(\c i, \c p) if \c i is not stored
    223        in the heap and sets the priority of \c i to \c p otherwise.
    224     */
     202    /// \brief \c i gets to the heap with priority \c p independently
     203    /// if \c i was already there.
     204    ///
     205    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     206    /// in the heap and sets the priority of \c i to \c p otherwise.
     207    /// \param i The item.
     208    /// \param p The priority.
    225209    void set(const Item &i, const Prio &p) {
    226210      int idx = iim[i];
    … …  
    236220    }
    237221
    238     ///Decreases the priority of \c i to \c p.
    239 
    240     /**
    241        This method decreases the priority of item \c i to \c p.
    242        \pre \c i must be stored in the heap with priority at least \c
    243        p relative to \c Compare.
    244     */
     222    /// \brief Decreases the priority of \c i to \c p.
     223
     224    /// This method decreases the priority of item \c i to \c p.
     225    /// \pre \c i must be stored in the heap with priority at least \c
     226    /// p relative to \c Compare.
     227    /// \param i The item.
     228    /// \param p The priority.
    245229    void decrease(const Item &i, const Prio &p) {
    246230      int idx = iim[i];
    … …  
    248232    }
    249233   
    250     ///Increases the priority of \c i to \c p.
    251 
    252     /**
    253        This method sets the priority of item \c i to \c p.
    254        \pre \c i must be stored in the heap with priority at most \c
    255        p relative to \c Compare.
    256     */
     234    /// \brief Increases the priority of \c i to \c p.
     235    ///
     236    /// This method sets the priority of item \c i to \c p.
     237    /// \pre \c i must be stored in the heap with priority at most \c
     238    /// p relative to \c Compare.
     239    /// \param i The item.
     240    /// \param p The priority.
    257241    void increase(const Item &i, const Prio &p) {
    258242      int idx = iim[i];
    … …  
    260244    }
    261245
    262     ///Returns if \c item is in, has already been in, or has never been in the heap.
    263 
    264     /**
    265       This method returns PRE_HEAP if \c item has never been in the
    266       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    267       otherwise. In the latter case it is possible that \c item will
    268       get back to the heap again.
    269     */
     246    /// \brief Returns if \c item is in, has already been in, or has
     247    /// never been in the heap.
     248    ///
     249    /// This method returns PRE_HEAP if \c item has never been in the
     250    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     251    /// otherwise. In the latter case it is possible that \c item will
     252    /// get back to the heap again.
     253    /// \param i The item.
    270254    state_enum state(const Item &i) const {
    271255      int s = iim[i];

  • src/lemon/radix_heap.h

    r1205 r1331  
    11/* -*- C++ -*-
    2  * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
     2 * src/lemon/radix_heap.h - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    … …  
    3131  /// @{
    3232
    33   /// A Radix Heap implementation.
    34  
    35   ///\todo Please document...
    36   ///
    37   ///\sa BinHeap
    38   ///\sa Dijkstra
    39 
    40   class UnderFlowPriorityException : public RuntimeError {
     33  /// \brief Exception thrown by RadixHeap.
     34  /// 
     35  /// This Exception is thrown when a smaller priority
     36  /// is inserted into the \e RadixHeap then the last time erased.
     37  /// \see RadixHeap
     38  /// \author Balazs Dezso
     39
     40  class UnderFlowPriorityError : public RuntimeError {
    4141  public:
    4242    virtual const char* exceptionName() const {
    43       return "lemon::UnderFlowPriorityException";
     43      return "lemon::UnderFlowPriorityError";
    4444    } 
    4545  };
    4646
     47  /// \brief A Radix Heap implementation.
     48  ///
     49  /// This class implements the \e radix \e heap data structure. A \e heap
     50  /// is a data structure for storing items with specified values called \e
     51  /// priorities in such a way that finding the item with minimum priority is
     52  /// efficient. This heap type can store only items with \e int priority.
     53  /// In a heap one can change the priority of an item, add or erase an
     54  /// item, but the priority cannot be decreased under the last removed
     55  /// item's priority.
     56  ///
     57  /// \param _Item Type of the items to be stored. 
     58  /// \param _ItemIntMap A read and writable Item int map, used internally
     59  /// to handle the cross references.
     60  ///
     61  /// \see BinHeap
     62  /// \see Dijkstra
     63  /// \author Balazs Dezso
     64
    4765  template <typename _Item, typename _ItemIntMap>
    4866  class RadixHeap {
    … …  
    5068  public:
    5169    typedef _Item Item;
    52     // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
    5370    typedef int Prio;
    5471    typedef _ItemIntMap ItemIntMap;
    5572
    56     /**
    57      * Each Item element have a state associated to it. It may be "in heap",
    58      * "pre heap" or "post heap". The later two are indifferent from the
    59      * heap's point of view, but may be useful to the user.
    60      *
    61      * The ItemIntMap _should_ be initialized in such way, that it maps
    62      * PRE_HEAP (-1) to any element to be put in the heap...
    63      */
    64     ///\todo it is used nowhere
    65     ///
     73    /// \brief Type to represent the items states.
     74    ///
     75    /// Each Item element have a state associated to it. It may be "in heap",
     76    /// "pre heap" or "post heap". The later two are indifferent from the
     77    /// heap's point of view, but may be useful to the user.
     78    ///
     79    /// The ItemIntMap _should_ be initialized in such way, that it maps
     80    /// PRE_HEAP (-1) to any element to be put in the heap...
    6681    enum state_enum {
    6782      IN_HEAP = 0,
    … …  
    92107
    93108  public:
    94     ///\e
     109    /// \brief The constructor.
     110    ///
     111    /// The constructor.
     112    /// \param _iim should be given to the constructor, since it is used
     113    /// internally to handle the cross references. The value of the map
     114    /// should be PRE_HEAP (-1) for each element.
    95115    explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
    96116      boxes.push_back(RadixBox(0, 1));
    … …  
    98118    }
    99119
    100     ///\e
     120    /// \brief The constructor.
     121    ///
     122    /// The constructor.
     123    ///
     124    /// \param _iim It should be given to the constructor, since it is used
     125    /// internally to handle the cross references. The value of the map
     126    /// should be PRE_HEAP (-1) for each element.
     127    ///
     128    /// \param capacity It determines the initial capacity of the heap.
    101129    RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
    102130      boxes.push_back(RadixBox(0, 1));
    … …  
    107135    }
    108136
    109     ///\e
     137    /// The number of items stored in the heap.
     138    ///
     139    /// \brief Returns the number of items stored in the heap.
    110140    int size() const { return data.size(); }
    111     ///\e
     141    /// \brief Checks if the heap stores no items.
     142    ///
     143    /// Returns \c true if and only if the heap stores no items.
    112144    bool empty() const { return data.empty(); }
    113145
    … …  
    184216    int findDown(int start, int prio) {
    185217      while (upper(start, prio)) {
    186         if (--start < 0) throw UnderFlowPriorityException();
     218        if (--start < 0) throw UnderFlowPriorityError();
    187219      }
    188220      return start;
    … …  
    208240    /// first box not empty.
    209241    void moveDown() {
    210       //      print(); printf("moveDown\n"); fflush(stdout);       
    211242      int box = findFirst();
    212243      if (box == 0) return;
    … …  
    242273  public:
    243274
    244     ///\e
     275    /// \brief Insert an item into the heap with the given heap.
     276    ///   
     277    /// Adds \c i to the heap with priority \c p.
     278    /// \param i The item to insert.
     279    /// \param p The priority of the item.
    245280    void push(const Item &i, const Prio &p) {
    246       fflush(stdout);
    247281      int n = data.size();
    248282      iim.set(i, n);
    … …  
    253287      int box = findDown(boxes.size() - 1, p);
    254288      insert(box, n);
    255       //      printf("Push %d\n", p);
    256       //print();
    257     }
    258 
    259     ///\e
     289    }
     290
     291    /// \brief Returns the item with minimum priority.
     292    ///
     293    /// This method returns the item with minimum priority. 
     294    /// \pre The heap must be nonempty. 
    260295    Item top() const {
    261       //      print(); printf("top\n");  fflush(stdout);
    262296      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
    263297      return data[boxes[0].first].item;
    264       //      print(); printf("top_end\n");  fflush(stdout);
    265     }
    266 
    267     /// Returns the prio of the top element of the heap.
     298    }
     299
     300    /// \brief Returns the minimum priority.
     301    ///
     302    /// It returns the minimum priority.
     303    /// \pre The heap must be nonempty.
    268304    Prio prio() const {
    269       //      print(); printf("prio\n"); fflush(stdout);
    270305      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
    271306      return data[boxes[0].first].prio;
    272307     }
    273308
    274     ///\e
     309    /// \brief Deletes the item with minimum priority.
     310    ///
     311    /// This method deletes the item with minimum priority.
     312    /// \pre The heap must be non-empty. 
    275313    void pop() {
    276       //      print(); printf("pop\n"); fflush(stdout);
    277314      moveDown();
    278315      int index = boxes[0].first;
    … …  
    280317      remove(index);
    281318      relocate_last(index);
    282       //      printf("Pop \n");
    283       //print();
    284     }
    285 
    286     ///\e
     319    }
     320
     321    /// \brief Deletes \c i from the heap.
     322    ///
     323    /// This method deletes item \c i from the heap, if \c i was
     324    /// already stored in the heap.
     325    /// \param i The item to erase.
    287326    void erase(const Item &i) {
    288327      int index = iim[i];
    … …  
    292331   }
    293332
    294     ///\e
     333    /// \brief Returns the priority of \c i.
     334    ///
     335    /// This function returns the priority of item \c i. 
     336    /// \pre \c i must be in the heap.
     337    /// \param i The item.
    295338    Prio operator[](const Item &i) const {
    296339      int idx = iim[i];
    … …  
    298341    }
    299342
    300     ///\e
     343    /// \brief \c i gets to the heap with priority \c p independently
     344    /// if \c i was already there.
     345    ///
     346    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     347    /// in the heap and sets the priority of \c i to \c p otherwise.
     348    /// It may throw an \e UnderFlowPriorityException.
     349    /// \param i The item.
     350    /// \param p The priority.
    301351    void set(const Item &i, const Prio &p) {
    302352      int idx = iim[i];
    … …  
    313363    }
    314364
    315     ///\e
     365
     366    /// \brief Decreases the priority of \c i to \c p.
     367    ///
     368    /// This method decreases the priority of item \c i to \c p.
     369    /// \pre \c i must be stored in the heap with priority at least \c p, and
     370    /// \c should be greater then the last removed item's priority.
     371    /// \param i The item.
     372    /// \param p The priority.
    316373    void decrease(const Item &i, const Prio &p) {
    317       //      print(); printf("decrease\n"); fflush(stdout);
    318374      int idx = iim[i];
    319375      data[idx].prio = p;
    … …  
    321377    }
    322378
    323     ///\e
     379    /// \brief Increases the priority of \c i to \c p.
     380    ///
     381    /// This method sets the priority of item \c i to \c p.
     382    /// \pre \c i must be stored in the heap with priority at most \c
     383    /// p relative to \c Compare.
     384    /// \param i The item.
     385    /// \param p The priority.
    324386    void increase(const Item &i, const Prio &p) {
    325387      int idx = iim[i];
    … …  
    328390    }
    329391
    330     ///\e
     392    /// \brief Returns if \c item is in, has already been in, or has
     393    /// never been in the heap.
     394    ///
     395    /// This method returns PRE_HEAP if \c item has never been in the
     396    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     397    /// otherwise. In the latter case it is possible that \c item will
     398    /// get back to the heap again.
     399    /// \param i The item.
    331400    state_enum state(const Item &i) const {
    332401      int s = iim[i];
    … …  
    335404    }
    336405
    337 //     void print() const {
    338 //       for (int i = 0; i < boxes.size(); ++i) {
    339 //      printf("(%d, %d) ", boxes[i].min, boxes[i].size);
    340 //      for (int k = boxes[i].first; k != -1; k = data[k].next) {
    341 //        printf("%d ", data[k].prio);
    342 //      }
    343 //      printf("\n");
    344 //       }
    345 //       fflush(stdout);
    346 //     }
    347 
    348406  }; // class RadixHeap
    349407
Note: See TracChangeset for help on using the changeset viewer.