COIN-OR::LEMON - Graph Library

Changeset 330:5ba887b7def4 in lemon-1.2 for lemon/max_matching.h


Ignore:
Timestamp:
10/22/08 14:53:34 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Doc improvements in lemon/max_matching.h

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_matching.h

    r327 r330  
    4040  /// \brief Edmonds' alternating forest maximum matching algorithm.
    4141  ///
    42   /// This class provides Edmonds' alternating forest matching
    43   /// algorithm. The starting matching (if any) can be passed to the
    44   /// algorithm using some of init functions.
     42  /// This class implements Edmonds' alternating forest matching
     43  /// algorithm. The algorithm can be started from an arbitrary initial
     44  /// matching (the default is the empty one)
    4545  ///
    46   /// The dual side of a matching is a map of the nodes to
     46  /// The dual solution of the problem is a map of the nodes to
    4747  /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
    4848  /// MATCHED/C showing the Gallai-Edmonds decomposition of the
     
    5050  /// factor-critical components, the nodes in \c ODD/A form the
    5151  /// barrier, and the nodes in \c MATCHED/C induce a graph having a
    52   /// perfect matching. The number of the fractor critical components
     52  /// perfect matching. The number of the factor-critical components
    5353  /// minus the number of barrier nodes is a lower bound on the
    54   /// unmatched nodes, and if the matching is optimal this bound is
     54  /// unmatched nodes, and the matching is optimal if and only if this bound is
    5555  /// tight. This decomposition can be attained by calling \c
    5656  /// decomposition() after running the algorithm.
     
    6767    ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
    6868    ///
    69     ///Indicates the Gallai-Edmonds decomposition of the graph, which
    70     ///shows an upper bound on the size of a maximum matching. The
     69    ///Indicates the Gallai-Edmonds decomposition of the graph. The
    7170    ///nodes with Status \c EVEN/D induce a graph with factor-critical
    7271    ///components, the nodes in \c ODD/A form the canonical barrier,
     
    411410
    412411    /// \name Execution control
    413     /// The simplest way to execute the algorithm is to use the member
     412    /// The simplest way to execute the algorithm is to use the
    414413    /// \c run() member function.
    415414    /// \n
    416415
    417     /// If you need more control on the execution, first you must call
     416    /// If you need better control on the execution, you must call
    418417    /// \ref init(), \ref greedyInit() or \ref matchingInit()
    419     /// functions, then you can start the algorithm with the \ref
     418    /// functions first, then you can start the algorithm with the \ref
    420419    /// startParse() or startDense() functions.
    421420
     
    434433    }
    435434
    436     ///\brief Finds a greedy matching for initial matching.
    437     ///
    438     ///For initial matchig it finds a maximal greedy matching.
     435    ///\brief Finds an initial matching in a greedy way
     436    ///
     437    ///It finds an initial matching in a greedy way.
    439438    void greedyInit() {
    440439      createStructures();
     
    460459
    461460
    462     /// \brief Initialize the matching from the map containing a matching.
     461    /// \brief Initialize the matching from a map containing.
    463462    ///
    464463    /// Initialize the matching from a \c bool valued \c Edge map. This
     
    508507    ///
    509508    /// It runs Edmonds' algorithm with a heuristic of postponing
    510     /// shrinks, giving a faster algorithm for dense graphs.
     509    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
    511510    void startDense() {
    512511      for(NodeIt n(_graph); n != INVALID; ++n) {
     
    539538
    540539    /// \name Primal solution
    541     /// Functions for get the primal solution, ie. the matching.
     540    /// Functions to get the primal solution, ie. the matching.
    542541
    543542    /// @{
    544543
    545     ///\brief Returns the size of the actual matching stored.
    546     ///
    547     ///Returns the size of the actual matching stored. After \ref
     544    ///\brief Returns the size of the current matching.
     545    ///
     546    ///Returns the size of the current matching. After \ref
    548547    ///run() it returns the size of the maximum matching in the graph.
    549548    int matchingSize() const {
     
    584583
    585584    /// \name Dual solution
    586     /// Functions for get the dual solution, ie. the decomposition.
     585    /// Functions to get the dual solution, ie. the decomposition.
    587586
    588587    /// @{
     
    646645  /// solution can be get with \c nodeValue(), \c blossomNum() and \c
    647646  /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
    648   /// "BlossomIt" nested class which is able to iterate on the nodes
     647  /// "BlossomIt" nested class, which is able to iterate on the nodes
    649648  /// of a blossom. If the value type is integral then the dual
    650649  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
     
    16311630
    16321631    /// \name Execution control
    1633     /// The simplest way to execute the algorithm is to use the member
     1632    /// The simplest way to execute the algorithm is to use the
    16341633    /// \c run() member function.
    16351634
     
    17921791
    17931792    /// \name Primal solution
    1794     /// Functions for get the primal solution, ie. the matching.
     1793    /// Functions to get the primal solution, ie. the matching.
    17951794
    17961795    /// @{
    17971796
    1798     /// \brief Returns the matching value.
    1799     ///
    1800     /// Returns the matching value.
     1797    /// \brief Returns the weight of the matching.
     1798    ///
     1799    /// Returns the weight of the matching.
    18011800    Value matchingValue() const {
    18021801      Value sum = 0;
     
    18491848
    18501849    /// \name Dual solution
    1851     /// Functions for get the dual solution.
     1850    /// Functions to get the dual solution.
    18521851
    18531852    /// @{
     
    18991898    }
    19001899
    1901     /// \brief Lemon iterator for get the items of the blossom.
    1902     ///
    1903     /// Lemon iterator for get the nodes of the blossom. This class
    1904     /// provides a common style lemon iterator which gives back a
     1900    /// \brief Iterator for obtaining the nodes of the blossom.
     1901    ///
     1902    /// Iterator for obtaining the nodes of the blossom. This class
     1903    /// provides a common lemon style iterator for listing a
    19051904    /// subset of the nodes.
    19061905    class BlossomIt {
     
    19091908      /// \brief Constructor.
    19101909      ///
    1911       /// Constructor for get the nodes of the variable.
     1910      /// Constructor to get the nodes of the variable.
    19121911      BlossomIt(const MaxWeightedMatching& algorithm, int variable)
    19131912        : _algorithm(&algorithm)
     
    28182817
    28192818    /// \name Execution control
    2820     /// The simplest way to execute the algorithm is to use the member
     2819    /// The simplest way to execute the algorithm is to use the
    28212820    /// \c run() member function.
    28222821
     
    29562955
    29572956    /// \name Primal solution
    2958     /// Functions for get the primal solution, ie. the matching.
     2957    /// Functions to get the primal solution, ie. the matching.
    29592958
    29602959    /// @{
     
    29972996
    29982997    /// \name Dual solution
    2999     /// Functions for get the dual solution.
     2998    /// Functions to get the dual solution.
    30002999
    30013000    /// @{
     
    30473046    }
    30483047
    3049     /// \brief Lemon iterator for get the items of the blossom.
    3050     ///
    3051     /// Lemon iterator for get the nodes of the blossom. This class
    3052     /// provides a common style lemon iterator which gives back a
     3048    /// \brief Iterator for obtaining the nodes of the blossom.
     3049    ///
     3050    /// Iterator for obtaining the nodes of the blossom. This class
     3051    /// provides a common lemon style iterator for listing a
    30533052    /// subset of the nodes.
    30543053    class BlossomIt {
     
    30573056      /// \brief Constructor.
    30583057      ///
    3059       /// Constructor for get the nodes of the variable.
     3058      /// Constructor to get the nodes of the variable.
    30603059      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
    30613060        : _algorithm(&algorithm)
Note: See TracChangeset for help on using the changeset viewer.