1.1 --- a/lemon/max_matching.h Mon Oct 13 14:00:11 2008 +0200
1.2 +++ b/lemon/max_matching.h Wed Oct 22 13:53:34 2008 +0100
1.3 @@ -39,19 +39,19 @@
1.4 ///
1.5 /// \brief Edmonds' alternating forest maximum matching algorithm.
1.6 ///
1.7 - /// This class provides Edmonds' alternating forest matching
1.8 - /// algorithm. The starting matching (if any) can be passed to the
1.9 - /// algorithm using some of init functions.
1.10 + /// This class implements Edmonds' alternating forest matching
1.11 + /// algorithm. The algorithm can be started from an arbitrary initial
1.12 + /// matching (the default is the empty one)
1.13 ///
1.14 - /// The dual side of a matching is a map of the nodes to
1.15 + /// The dual solution of the problem is a map of the nodes to
1.16 /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
1.17 /// MATCHED/C showing the Gallai-Edmonds decomposition of the
1.18 /// graph. The nodes in \c EVEN/D induce a graph with
1.19 /// factor-critical components, the nodes in \c ODD/A form the
1.20 /// barrier, and the nodes in \c MATCHED/C induce a graph having a
1.21 - /// perfect matching. The number of the fractor critical components
1.22 + /// perfect matching. The number of the factor-critical components
1.23 /// minus the number of barrier nodes is a lower bound on the
1.24 - /// unmatched nodes, and if the matching is optimal this bound is
1.25 + /// unmatched nodes, and the matching is optimal if and only if this bound is
1.26 /// tight. This decomposition can be attained by calling \c
1.27 /// decomposition() after running the algorithm.
1.28 ///
1.29 @@ -66,8 +66,7 @@
1.30
1.31 ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
1.32 ///
1.33 - ///Indicates the Gallai-Edmonds decomposition of the graph, which
1.34 - ///shows an upper bound on the size of a maximum matching. The
1.35 + ///Indicates the Gallai-Edmonds decomposition of the graph. The
1.36 ///nodes with Status \c EVEN/D induce a graph with factor-critical
1.37 ///components, the nodes in \c ODD/A form the canonical barrier,
1.38 ///and the nodes in \c MATCHED/C induce a graph having a perfect
1.39 @@ -410,13 +409,13 @@
1.40 }
1.41
1.42 /// \name Execution control
1.43 - /// The simplest way to execute the algorithm is to use the member
1.44 + /// The simplest way to execute the algorithm is to use the
1.45 /// \c run() member function.
1.46 /// \n
1.47
1.48 - /// If you need more control on the execution, first you must call
1.49 + /// If you need better control on the execution, you must call
1.50 /// \ref init(), \ref greedyInit() or \ref matchingInit()
1.51 - /// functions, then you can start the algorithm with the \ref
1.52 + /// functions first, then you can start the algorithm with the \ref
1.53 /// startParse() or startDense() functions.
1.54
1.55 ///@{
1.56 @@ -433,9 +432,9 @@
1.57 }
1.58 }
1.59
1.60 - ///\brief Finds a greedy matching for initial matching.
1.61 + ///\brief Finds an initial matching in a greedy way
1.62 ///
1.63 - ///For initial matchig it finds a maximal greedy matching.
1.64 + ///It finds an initial matching in a greedy way.
1.65 void greedyInit() {
1.66 createStructures();
1.67 for (NodeIt n(_graph); n != INVALID; ++n) {
1.68 @@ -459,7 +458,7 @@
1.69 }
1.70
1.71
1.72 - /// \brief Initialize the matching from the map containing a matching.
1.73 + /// \brief Initialize the matching from a map containing.
1.74 ///
1.75 /// Initialize the matching from a \c bool valued \c Edge map. This
1.76 /// map must have the property that there are no two incident edges
1.77 @@ -507,7 +506,7 @@
1.78 /// \brief Starts Edmonds' algorithm.
1.79 ///
1.80 /// It runs Edmonds' algorithm with a heuristic of postponing
1.81 - /// shrinks, giving a faster algorithm for dense graphs.
1.82 + /// shrinks, therefore resulting in a faster algorithm for dense graphs.
1.83 void startDense() {
1.84 for(NodeIt n(_graph); n != INVALID; ++n) {
1.85 if ((*_status)[n] == UNMATCHED) {
1.86 @@ -538,13 +537,13 @@
1.87 /// @}
1.88
1.89 /// \name Primal solution
1.90 - /// Functions for get the primal solution, ie. the matching.
1.91 + /// Functions to get the primal solution, ie. the matching.
1.92
1.93 /// @{
1.94
1.95 - ///\brief Returns the size of the actual matching stored.
1.96 + ///\brief Returns the size of the current matching.
1.97 ///
1.98 - ///Returns the size of the actual matching stored. After \ref
1.99 + ///Returns the size of the current matching. After \ref
1.100 ///run() it returns the size of the maximum matching in the graph.
1.101 int matchingSize() const {
1.102 int size = 0;
1.103 @@ -583,7 +582,7 @@
1.104 /// @}
1.105
1.106 /// \name Dual solution
1.107 - /// Functions for get the dual solution, ie. the decomposition.
1.108 + /// Functions to get the dual solution, ie. the decomposition.
1.109
1.110 /// @{
1.111
1.112 @@ -645,7 +644,7 @@
1.113 /// be asked with \c matching() or mate() functions. The dual
1.114 /// solution can be get with \c nodeValue(), \c blossomNum() and \c
1.115 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
1.116 - /// "BlossomIt" nested class which is able to iterate on the nodes
1.117 + /// "BlossomIt" nested class, which is able to iterate on the nodes
1.118 /// of a blossom. If the value type is integral then the dual
1.119 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
1.120 template <typename _Graph,
1.121 @@ -1630,7 +1629,7 @@
1.122 }
1.123
1.124 /// \name Execution control
1.125 - /// The simplest way to execute the algorithm is to use the member
1.126 + /// The simplest way to execute the algorithm is to use the
1.127 /// \c run() member function.
1.128
1.129 ///@{
1.130 @@ -1791,13 +1790,13 @@
1.131 /// @}
1.132
1.133 /// \name Primal solution
1.134 - /// Functions for get the primal solution, ie. the matching.
1.135 + /// Functions to get the primal solution, ie. the matching.
1.136
1.137 /// @{
1.138
1.139 - /// \brief Returns the matching value.
1.140 + /// \brief Returns the weight of the matching.
1.141 ///
1.142 - /// Returns the matching value.
1.143 + /// Returns the weight of the matching.
1.144 Value matchingValue() const {
1.145 Value sum = 0;
1.146 for (NodeIt n(_graph); n != INVALID; ++n) {
1.147 @@ -1848,7 +1847,7 @@
1.148 /// @}
1.149
1.150 /// \name Dual solution
1.151 - /// Functions for get the dual solution.
1.152 + /// Functions to get the dual solution.
1.153
1.154 /// @{
1.155
1.156 @@ -1898,17 +1897,17 @@
1.157 return _blossom_potential[k].value;
1.158 }
1.159
1.160 - /// \brief Lemon iterator for get the items of the blossom.
1.161 + /// \brief Iterator for obtaining the nodes of the blossom.
1.162 ///
1.163 - /// Lemon iterator for get the nodes of the blossom. This class
1.164 - /// provides a common style lemon iterator which gives back a
1.165 + /// Iterator for obtaining the nodes of the blossom. This class
1.166 + /// provides a common lemon style iterator for listing a
1.167 /// subset of the nodes.
1.168 class BlossomIt {
1.169 public:
1.170
1.171 /// \brief Constructor.
1.172 ///
1.173 - /// Constructor for get the nodes of the variable.
1.174 + /// Constructor to get the nodes of the variable.
1.175 BlossomIt(const MaxWeightedMatching& algorithm, int variable)
1.176 : _algorithm(&algorithm)
1.177 {
1.178 @@ -2817,7 +2816,7 @@
1.179 }
1.180
1.181 /// \name Execution control
1.182 - /// The simplest way to execute the algorithm is to use the member
1.183 + /// The simplest way to execute the algorithm is to use the
1.184 /// \c run() member function.
1.185
1.186 ///@{
1.187 @@ -2955,7 +2954,7 @@
1.188 /// @}
1.189
1.190 /// \name Primal solution
1.191 - /// Functions for get the primal solution, ie. the matching.
1.192 + /// Functions to get the primal solution, ie. the matching.
1.193
1.194 /// @{
1.195
1.196 @@ -2996,7 +2995,7 @@
1.197 /// @}
1.198
1.199 /// \name Dual solution
1.200 - /// Functions for get the dual solution.
1.201 + /// Functions to get the dual solution.
1.202
1.203 /// @{
1.204
1.205 @@ -3046,17 +3045,17 @@
1.206 return _blossom_potential[k].value;
1.207 }
1.208
1.209 - /// \brief Lemon iterator for get the items of the blossom.
1.210 + /// \brief Iterator for obtaining the nodes of the blossom.
1.211 ///
1.212 - /// Lemon iterator for get the nodes of the blossom. This class
1.213 - /// provides a common style lemon iterator which gives back a
1.214 + /// Iterator for obtaining the nodes of the blossom. This class
1.215 + /// provides a common lemon style iterator for listing a
1.216 /// subset of the nodes.
1.217 class BlossomIt {
1.218 public:
1.219
1.220 /// \brief Constructor.
1.221 ///
1.222 - /// Constructor for get the nodes of the variable.
1.223 + /// Constructor to get the nodes of the variable.
1.224 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
1.225 : _algorithm(&algorithm)
1.226 {