lemon-main: comparison lemon/max

equal deleted inserted replaced

-:8907e8eb252e
+:a95ea2463839
 /// \ingroup matching
 ///
 /// \brief Edmonds' alternating forest maximum matching algorithm.
 ///
-/// This class provides Edmonds' alternating forest matching
+/// This class implements Edmonds' alternating forest matching
-/// algorithm. The starting matching (if any) can be passed to the
+/// algorithm. The algorithm can be started from an arbitrary initial
-/// algorithm using some of init functions.
+/// matching (the default is the empty one)
 ///
-/// The dual side of a matching is a map of the nodes to
+/// The dual solution of the problem is a map of the nodes to
 /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
 /// MATCHED/C showing the Gallai-Edmonds decomposition of the
 /// graph. The nodes in \c EVEN/D induce a graph with
 /// factor-critical components, the nodes in \c ODD/A form the
 /// barrier, and the nodes in \c MATCHED/C induce a graph having a
-/// perfect matching. The number of the fractor critical components
+/// perfect matching. The number of the factor-critical components
 /// minus the number of barrier nodes is a lower bound on the
-/// unmatched nodes, and if the matching is optimal this bound is
+/// unmatched nodes, and the matching is optimal if and only if this bound is
 /// tight. This decomposition can be attained by calling \c
 /// decomposition() after running the algorithm.
 ///
 /// \param _Graph The graph type the algorithm runs on.
 template <typename _Graph>
 typedef typename Graph::template NodeMap<typename Graph::Arc>
 MatchingMap;
 ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
 ///
-///Indicates the Gallai-Edmonds decomposition of the graph, which
+///Indicates the Gallai-Edmonds decomposition of the graph. The
-///shows an upper bound on the size of a maximum matching. The
 ///nodes with Status \c EVEN/D induce a graph with factor-critical
 ///components, the nodes in \c ODD/A form the canonical barrier,
 ///and the nodes in \c MATCHED/C induce a graph having a perfect
 ///matching.
 enum Status {
 ~MaxMatching() {
 destroyStructures();
 }
 /// \name Execution control
-/// The simplest way to execute the algorithm is to use the member
+/// The simplest way to execute the algorithm is to use the
 /// \c run() member function.
 /// \n
-/// If you need more control on the execution, first you must call
+/// If you need better control on the execution, you must call
 /// \ref init(), \ref greedyInit() or \ref matchingInit()
-/// functions, then you can start the algorithm with the \ref
+/// functions first, then you can start the algorithm with the \ref
 /// startParse() or startDense() functions.
 ///@{
 /// \brief Sets the actual matching to the empty matching.
 _matching->set(n, INVALID);
 _status->set(n, UNMATCHED);
 }
 }
-///\brief Finds a greedy matching for initial matching.
+///\brief Finds an initial matching in a greedy way
 ///
-///For initial matchig it finds a maximal greedy matching.
+///It finds an initial matching in a greedy way.
 void greedyInit() {
 createStructures();
 for (NodeIt n(_graph); n != INVALID; ++n) {
 _matching->set(n, INVALID);
 _status->set(n, UNMATCHED);
 }
 }
 }
-/// \brief Initialize the matching from the map containing a matching.
+/// \brief Initialize the matching from a map containing.
 ///
 /// Initialize the matching from a \c bool valued \c Edge map. This
 /// map must have the property that there are no two incident edges
 /// with true value, ie. it contains a matching.
 /// \return %True if the map contains a matching.
 }
 /// \brief Starts Edmonds' algorithm.
 ///
 /// It runs Edmonds' algorithm with a heuristic of postponing
-/// shrinks, giving a faster algorithm for dense graphs.
+/// shrinks, therefore resulting in a faster algorithm for dense graphs.
 void startDense() {
 for(NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_status)[n] == UNMATCHED) {
 (*_blossom_rep)[_blossom_set->insert(n)] = n;
 _tree_set->insert(n);
 }
 /// @}
 /// \name Primal solution
-/// Functions for get the primal solution, ie. the matching.
+/// Functions to get the primal solution, ie. the matching.
 /// @{
-///\brief Returns the size of the actual matching stored.
+///\brief Returns the size of the current matching.
 ///
-///Returns the size of the actual matching stored. After \ref
+///Returns the size of the current matching. After \ref
 ///run() it returns the size of the maximum matching in the graph.
 int matchingSize() const {
 int size = 0;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 }
 /// @}
 /// \name Dual solution
-/// Functions for get the dual solution, ie. the decomposition.
+/// Functions to get the dual solution, ie. the decomposition.
 /// @{
 /// \brief Returns the class of the node in the Edmonds-Gallai
 /// decomposition.
 /// The algorithm can be executed with \c run() or the \c init() and
 /// then the \c start() member functions. After it the matching can
 /// be asked with \c matching() or mate() functions. The dual
 /// solution can be get with \c nodeValue(), \c blossomNum() and \c
 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
-/// "BlossomIt" nested class which is able to iterate on the nodes
+/// "BlossomIt" nested class, which is able to iterate on the nodes
 /// of a blossom. If the value type is integral then the dual
 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
 template <typename _Graph,
 typename _WeightMap = typename _Graph::template EdgeMap<int> >
 class MaxWeightedMatching {
 ~MaxWeightedMatching() {
 destroyStructures();
 }
 /// \name Execution control
-/// The simplest way to execute the algorithm is to use the member
+/// The simplest way to execute the algorithm is to use the
 /// \c run() member function.
 ///@{
 /// \brief Initialize the algorithm
 }
 /// @}
 /// \name Primal solution
-/// Functions for get the primal solution, ie. the matching.
+/// Functions to get the primal solution, ie. the matching.
 /// @{
-/// \brief Returns the matching value.
+/// \brief Returns the weight of the matching.
 ///
-/// Returns the matching value.
+/// Returns the weight of the matching.
 Value matchingValue() const {
 Value sum = 0;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 sum += _weight[(*_matching)[n]];
 }
 /// @}
 /// \name Dual solution
-/// Functions for get the dual solution.
+/// Functions to get the dual solution.
 /// @{
 /// \brief Returns the value of the dual solution.
 ///
 /// \see BlossomIt
 Value blossomValue(int k) const {
 return _blossom_potential[k].value;
 }
-/// \brief Lemon iterator for get the items of the blossom.
+/// \brief Iterator for obtaining the nodes of the blossom.
 ///
-/// Lemon iterator for get the nodes of the blossom. This class
+/// Iterator for obtaining the nodes of the blossom. This class
-/// provides a common style lemon iterator which gives back a
+/// provides a common lemon style iterator for listing a
 /// subset of the nodes.
 class BlossomIt {
 public:
 /// \brief Constructor.
 ///
-/// Constructor for get the nodes of the variable.
+/// Constructor to get the nodes of the variable.
 BlossomIt(const MaxWeightedMatching& algorithm, int variable)
 : _algorithm(&algorithm)
 {
 _index = _algorithm->_blossom_potential[variable].begin;
 _last = _algorithm->_blossom_potential[variable].end;
 ~MaxWeightedPerfectMatching() {
 destroyStructures();
 }
 /// \name Execution control
-/// The simplest way to execute the algorithm is to use the member
+/// The simplest way to execute the algorithm is to use the
 /// \c run() member function.
 ///@{
 /// \brief Initialize the algorithm
 }
 /// @}
 /// \name Primal solution
-/// Functions for get the primal solution, ie. the matching.
+/// Functions to get the primal solution, ie. the matching.
 /// @{
 /// \brief Returns the matching value.
 ///
 }
 /// @}
 /// \name Dual solution
-/// Functions for get the dual solution.
+/// Functions to get the dual solution.
 /// @{
 /// \brief Returns the value of the dual solution.
 ///
 /// \see BlossomIt
 Value blossomValue(int k) const {
 return _blossom_potential[k].value;
 }
-/// \brief Lemon iterator for get the items of the blossom.
+/// \brief Iterator for obtaining the nodes of the blossom.
 ///
-/// Lemon iterator for get the nodes of the blossom. This class
+/// Iterator for obtaining the nodes of the blossom. This class
-/// provides a common style lemon iterator which gives back a
+/// provides a common lemon style iterator for listing a
 /// subset of the nodes.
 class BlossomIt {
 public:
 /// \brief Constructor.
 ///
-/// Constructor for get the nodes of the variable.
+/// Constructor to get the nodes of the variable.
 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
 : _algorithm(&algorithm)
 {
 _index = _algorithm->_blossom_potential[variable].begin;
 _last = _algorithm->_blossom_potential[variable].end;

changeset 347	85820a499b76
parent 327	91d63b8b1a4c
child 425	cace3206223b