COIN-OR::LEMON - Graph Library

Changeset 1270:806451fd084b in lemon-0.x


Ignore:
Timestamp:
03/29/05 09:35:09 (15 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1698
Message:

bugfixes in doc

Location:
src/lemon
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bfs.h

    r1236 r1270  
    136136  ///a Bfs traits class.
    137137  ///
    138   ///\author Jacint Szabo and Alpar Juttner
     138  ///\author Alpar Juttner
    139139  ///\todo A compare object would be nice.
    140140
     
    349349    ///\ref named-templ-param "Named parameter"
    350350    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
    351     ///If you don't set it explicitely, it will be automatically allocated.
     351    ///If you don't set it explicitly, it will be automatically allocated.
    352352    template <class T>
    353353    class DefProcessedMapToBeDefaultMap :
     
    386386    ///Sets the map storing the predecessor edges.
    387387    ///If you don't use this function before calling \ref run(),
    388     ///it will allocate one. The destuctor deallocates this
     388    ///it will allocate one. The destructor deallocates this
    389389    ///automatically allocated map, of course.
    390390    ///\return <tt> (*this) </tt>
     
    403403    ///Sets the map indicating the reached nodes.
    404404    ///If you don't use this function before calling \ref run(),
    405     ///it will allocate one. The destuctor deallocates this
     405    ///it will allocate one. The destructor deallocates this
    406406    ///automatically allocated map, of course.
    407407    ///\return <tt> (*this) </tt>
     
    420420    ///Sets the map indicating the processed nodes.
    421421    ///If you don't use this function before calling \ref run(),
    422     ///it will allocate one. The destuctor deallocates this
     422    ///it will allocate one. The destructor deallocates this
    423423    ///automatically allocated map, of course.
    424424    ///\return <tt> (*this) </tt>
     
    437437//     ///Sets the map storing the predecessor nodes.
    438438//     ///If you don't use this function before calling \ref run(),
    439 //     ///it will allocate one. The destuctor deallocates this
     439//     ///it will allocate one. The destructor deallocates this
    440440//     ///automatically allocated map, of course.
    441441//     ///\return <tt> (*this) </tt>
     
    454454    ///Sets the map storing the distances calculated by the algorithm.
    455455    ///If you don't use this function before calling \ref run(),
    456     ///it will allocate one. The destuctor deallocates this
     456    ///it will allocate one. The destructor deallocates this
    457457    ///automatically allocated map, of course.
    458458    ///\return <tt> (*this) </tt>
     
    659659    ///\pre \ref run() must be called before using this function.
    660660    ///\warning If node \c v in unreachable from the root(s) the return value
    661     ///of this funcion is undefined.
     661    ///of this function is undefined.
    662662    int dist(Node v) const { return (*_dist)[v]; }
    663663
     
    716716
    717717    ///Returns \c true if \c v is reachable from the root.
    718     ///\warning The source nodes are inditated as unreached.
     718    ///\warning The source nodes are indicated as unreached.
    719719    ///\pre Either \ref run() or \ref start()
    720720    ///must be called before using this function.
  • src/lemon/bin_heap.h

    r1191 r1270  
    2121///\file
    2222///\brief Binary Heap implementation.
    23 ///\todo It should be documented.
    2423
    2524#include <vector>
     
    3231  /// @{
    3332
    34    /// A Binary Heap implementation.
     33  /// A Binary Heap implementation.
    3534 
    36   ///\todo Please document...
     35  ///This class implements the \e binary \e heap data structure. A \e heap
     36  ///is a data structure for storing items with specified values called \e
     37  ///priorities in such a way that finding the item with minimum priority is
     38  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
     39  ///one can change the priority of an item, add or erase an item, etc.
     40  ///
     41  ///\param Item Type of the items to be stored. 
     42  ///\param Prio Type of the priority of the items.
     43  ///\param ItemIntMap A read and writable Item int map, used internally
     44  ///to handle the cross references.
     45  ///\param Compare A class for the ordering of the priorities. The
     46  ///default is \c std::less<Prio>.
    3747  ///
    3848  ///\sa FibHeap
     
    7383
    7484  public:
    75     ///\e
     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    */
    7691    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    77     ///\e
     92   
     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    */
    78100    BinHeap(ItemIntMap &_iim, const Compare &_comp)
    79101      : iim(_iim), comp(_comp) {}
    80102
    81103
    82     ///\e
     104    ///The number of items stored in the heap.
     105
     106    /**
     107       Returns the number of items stored in the heap.
     108    */
    83109    int size() const { return data.size(); }
    84     ///\e
     110   
     111    ///Checks if the heap stores no items.
     112   
     113    /**
     114       Returns \c true if and only if the heap stores no items.
     115    */
    85116    bool empty() const { return data.empty(); }
    86117
     
    112143
    113144  public:
    114     ///\e
     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    */
    115151    void push(const PairType &p) {
    116152      int n = data.size();
     
    118154      bubble_up(n, p);
    119155    }
    120     ///\e
     156
     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    */
    121163    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
    122164
    123     ///\e
     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    */
    124172    Item top() const {
    125173      return data[0].first;
    126174    }
    127     /// Returns the prio of the top element of the heap.
     175
     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    */
    128182    Prio prio() const {
    129183      return data[0].second;
    130184    }
    131185
    132     ///\e
     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    */
    133193    void pop() {
    134194      rmidx(0);
    135195    }
    136196
    137     ///\e
     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    */
    138203    void erase(const Item &i) {
    139204      rmidx(iim[i]);
    140205    }
    141206
    142     ///\e
     207   
     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    */
    143214    Prio operator[](const Item &i) const {
    144215      int idx = iim[i];
     
    146217    }
    147218
    148     ///\e
     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    */
    149225    void set(const Item &i, const Prio &p) {
    150226      int idx = iim[i];
     
    160236    }
    161237
    162     ///\e
     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    */
    163245    void decrease(const Item &i, const Prio &p) {
    164246      int idx = iim[i];
    165247      bubble_up(idx, PairType(i,p));
    166248    }
    167     ///\e
     249   
     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    */
    168257    void increase(const Item &i, const Prio &p) {
    169258      int idx = iim[i];
     
    171260    }
    172261
    173     ///\e
     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    */
    174270    state_enum state(const Item &i) const {
    175271      int s = iim[i];
  • src/lemon/concept/path.h

    r1228 r1270  
    3737    //! \param GR The graph type in which the path is.
    3838    //!
    39     //! In a sense, the path can be treated as a graph, for is has \c NodeIt
     39    //! In a sense, the path can be treated as a graph, for it has \c NodeIt
    4040    //! and \c EdgeIt with the same usage. These types converts to the \c Node
    4141    //! and \c Edge of the original graph.
     
    173173       *
    174174       * While the builder is active (after the first modifying
    175        * operation and until the call of \ref commit())
    176        * the underlining Path is in a
    177        * "transitional" state (operations on it have undefined result).
     175       * operation and until the call of \ref commit()) the
     176       * underlining Path is in a "transitional" state (operations on
     177       * it have undefined result).
    178178       */
    179179      class Builder {
     
    191191        /// Sets the starting node of the path. Edge added to the path
    192192        /// afterwards have to be incident to this node.
    193         /// You \em must start building an empry path with this functions.
     193        /// You \em must start building an empty path with these functions.
    194194        /// (And you \em must \em not use it later).
    195195        /// \sa pushFront()
     
    216216        ///Reserve (front) storage for the builder in advance.
    217217
    218         ///If you know an reasonable upper bound of the number of the edges
     218        ///If you know a reasonable upper bound on the number of the edges
    219219        ///to add to the front of the path,
    220220        ///using this function you may speed up the building.
     
    222222        ///Reserve (back) storage for the builder in advance.
    223223
    224         ///If you know an reasonable upper bound of the number of the edges
     224        ///If you know a reasonable upper bound on the number of the edges
    225225        ///to add to the back of the path,
    226226        ///using this function you may speed up the building.
  • src/lemon/fib_heap.h

    r1204 r1270  
    8989    };
    9090   
     91    ///The constructor
     92
     93    /**
     94       \c _iimap should be given to the constructor, since it is
     95       used internally to handle the cross references.
     96    */
    9197    explicit FibHeap(ItemIntMap &_iimap)
    9298      : minimum(0), iimap(_iimap), num_items() {}
     99 
     100    ///The constructor
     101
     102    /**
     103       \c _iimap should be given to the constructor, since it is used
     104       internally to handle the cross references. \c _comp is an
     105       object for ordering of the priorities.
     106    */
    93107    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
    94       iimap(_iimap), comp(_comp), num_items() {}
     108                  iimap(_iimap), comp(_comp), num_items() {}
    95109   
    96110    ///The number of items stored in the heap.
  • src/lemon/min_cost_flow.h

    r1164 r1270  
    3737  ///
    3838  ///
    39   /// The class \ref lemon::MinCostFlow "MinCostFlow" implements
    40   /// an algorithm for finding a flow of value \c k
    41   /// having minimal total cost
    42   /// from a given source node to a given target node in an
    43   /// edge-weighted directed graph. To this end,
    44   /// the edge-capacities and edge-weitghs have to be nonnegative.
    45   /// The edge-capacities should be integers, but the edge-weights can be
    46   /// integers, reals or of other comparable numeric type.
    47   /// This algorithm is intended to use only for small values of \c k,
    48   /// since it is only polynomial in k,
    49   /// not in the length of k (which is log k).
    50   /// In order to find the minimum cost flow of value \c k it
    51   /// finds the minimum cost flow of value \c i for every
    52   /// \c i between 0 and \c k.
     39  /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an
     40  /// algorithm for finding a flow of value \c k having minimal total
     41  /// cost from a given source node to a given target node in an
     42  /// edge-weighted directed graph. To this end, the edge-capacities
     43  /// and edge-weights have to be nonnegative.  The edge-capacities
     44  /// should be integers, but the edge-weights can be integers, reals
     45  /// or of other comparable numeric type.  This algorithm is intended
     46  /// to be used only for small values of \c k, since it is only
     47  /// polynomial in k, not in the length of k (which is log k):  in
     48  /// order to find the minimum cost flow of value \c k it finds the
     49  /// minimum cost flow of value \c i for every \c i between 0 and \c
     50  /// k.
    5351  ///
    5452  ///\param Graph The directed graph type the algorithm runs on.
     
    150148          potential.set(n, potential[n]+dijkstra.distMap()[n]);
    151149       
    152         //Augmenting on the sortest path
     150        //Augmenting on the shortest path
    153151        Node n=t;
    154152        ResGraphEdge e;
     
    227225
    228226    This function checks, whether the given flow and potential
    229     satisfiy the complementary slackness cnditions (i.e. these are optimal).
     227    satisfy the complementary slackness conditions (i.e. these are optimal).
    230228    This function only checks optimality, doesn't bother with feasibility.
    231229    For testing purpose.
  • src/lemon/utility.h

    r1256 r1270  
    3838{
    3939
    40   /// Basic type for defining "tags". A "YES" condidion for enable_if.
     40  /// Basic type for defining "tags". A "YES" condition for enable_if.
    4141
    4242  /// \todo This should go to a separate "basic_types.h" (or something)
     
    4646  };
    4747
    48   /// Basic type for defining "tags". A "NO" condidion for enable_if.
     48  /// Basic type for defining "tags". A "NO" condition for enable_if.
    4949  struct False {
    5050    static const bool value = false;
Note: See TracChangeset for help on using the changeset viewer.