author Peter Kovacs Wed, 15 Apr 2009 12:01:14 +0200 changeset 637 b61354458b59 parent 636 630c4898c548 child 640 7ac52d6a268e
Imporvements for the matching algorithms (#264)
 doc/groups.dox file | annotate | diff | comparison | revisions lemon/max_matching.h file | annotate | diff | comparison | revisions test/max_matching_test.cc file | annotate | diff | comparison | revisions
     1.1 --- a/doc/groups.dox	Wed Apr 15 07:13:30 2009 +0100
1.2 +++ b/doc/groups.dox	Wed Apr 15 12:01:14 2009 +0200
1.3 @@ -435,9 +435,10 @@
1.4  @ingroup algs
1.5  \brief Algorithms for finding matchings in graphs and bipartite graphs.
1.6
1.7 -This group contains algorithm objects and functions to calculate
1.8 +This group contains the algorithms for calculating
1.9  matchings in graphs and bipartite graphs. The general matching problem is
1.10 -finding a subset of the arcs which does not shares common endpoints.
1.11 +finding a subset of the edges for which each node has at most one incident
1.12 +edge.
1.13
1.14  There are several different algorithms for calculate matchings in
1.15  graphs.  The matching problems in bipartite graphs are generally

     2.1 --- a/lemon/max_matching.h	Wed Apr 15 07:13:30 2009 +0100
2.2 +++ b/lemon/max_matching.h	Wed Apr 15 12:01:14 2009 +0200
2.3 @@ -37,42 +37,51 @@
2.4
2.5    /// \ingroup matching
2.6    ///
2.7 -  /// \brief Edmonds' alternating forest maximum matching algorithm.
2.8 +  /// \brief Maximum cardinality matching in general graphs
2.9    ///
2.10 -  /// This class implements Edmonds' alternating forest matching
2.11 -  /// algorithm. The algorithm can be started from an arbitrary initial
2.12 -  /// matching (the default is the empty one)
2.13 +  /// This class implements Edmonds' alternating forest matching algorithm
2.14 +  /// for finding a maximum cardinality matching in a general graph.
2.15 +  /// It can be started from an arbitrary initial matching
2.16 +  /// (the default is the empty one).
2.17    ///
2.18    /// The dual solution of the problem is a map of the nodes to
2.19 -  /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
2.20 -  /// MATCHED/C showing the Gallai-Edmonds decomposition of the
2.21 -  /// graph. The nodes in \c EVEN/D induce a graph with
2.22 -  /// factor-critical components, the nodes in \c ODD/A form the
2.23 -  /// barrier, and the nodes in \c MATCHED/C induce a graph having a
2.24 -  /// perfect matching. The number of the factor-critical components
2.25 +  /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D),
2.26 +  /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds
2.27 +  /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph
2.28 +  /// with factor-critical components, the nodes in \c ODD/A form the
2.29 +  /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having
2.30 +  /// a perfect matching. The number of the factor-critical components
2.31    /// minus the number of barrier nodes is a lower bound on the
2.32    /// unmatched nodes, and the matching is optimal if and only if this bound is
2.33 -  /// tight. This decomposition can be attained by calling \c
2.34 +  /// tight. This decomposition can be obtained by calling \c
2.35    /// decomposition() after running the algorithm.
2.36    ///
2.37 -  /// \param GR The graph type the algorithm runs on.
2.38 +  /// \tparam GR The graph type the algorithm runs on.
2.39    template <typename GR>
2.40    class MaxMatching {
2.41    public:
2.42
2.43 +    /// The graph type of the algorithm
2.44      typedef GR Graph;
2.45      typedef typename Graph::template NodeMap<typename Graph::Arc>
2.46      MatchingMap;
2.47
2.48 -    ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
2.49 +    ///\brief Status constants for Gallai-Edmonds decomposition.
2.50      ///
2.51 -    ///Indicates the Gallai-Edmonds decomposition of the graph. The
2.52 -    ///nodes with Status \c EVEN/D induce a graph with factor-critical
2.53 -    ///components, the nodes in \c ODD/A form the canonical barrier,
2.54 -    ///and the nodes in \c MATCHED/C induce a graph having a perfect
2.55 -    ///matching.
2.56 +    ///These constants are used for indicating the Gallai-Edmonds
2.57 +    ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
2.58 +    ///induce a subgraph with factor-critical components, the nodes with
2.59 +    ///status \c ODD (or \c A) form the canonical barrier, and the nodes
2.60 +    ///with status \c MATCHED (or \c C) induce a subgraph having a
2.61 +    ///perfect matching.
2.62      enum Status {
2.63 -      EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2
2.64 +      EVEN = 1,       ///< = 1. (\c D is an alias for \c EVEN.)
2.65 +      D = 1,
2.66 +      MATCHED = 0,    ///< = 0. (\c C is an alias for \c MATCHED.)
2.67 +      C = 0,
2.68 +      ODD = -1,       ///< = -1. (\c A is an alias for \c ODD.)
2.69 +      A = -1,
2.70 +      UNMATCHED = -2  ///< = -2.
2.71      };
2.72
2.73      typedef typename Graph::template NodeMap<Status> StatusMap;
2.74 @@ -338,8 +347,6 @@
2.75        (*_blossom_rep)[_blossom_set->find(nca)] = nca;
2.76      }
2.77
2.78 -
2.79 -
2.80      void extendOnArc(const Arc& a) {
2.81        Node base = _graph.source(a);
2.82        Node odd = _graph.target(a);
2.83 @@ -408,22 +415,19 @@
2.84        destroyStructures();
2.85      }
2.86
2.87 -    /// \name Execution control
2.88 +    /// \name Execution Control
2.89      /// The simplest way to execute the algorithm is to use the
2.90 -    /// \c run() member function.
2.91 -    /// \n
2.92 -
2.93 -    /// If you need better control on the execution, you must call
2.94 -    /// \ref init(), \ref greedyInit() or \ref matchingInit()
2.95 -    /// functions first, then you can start the algorithm with the \ref
2.96 -    /// startSparse() or startDense() functions.
2.97 +    /// \c run() member function.\n
2.98 +    /// If you need better control on the execution, you have to call
2.99 +    /// one of the functions \ref init(), \ref greedyInit() or
2.100 +    /// \ref matchingInit() first, then you can start the algorithm with
2.101 +    /// \ref startSparse() or \ref startDense().
2.102
2.103      ///@{
2.104
2.105 -    /// \brief Sets the actual matching to the empty matching.
2.106 +    /// \brief Set the initial matching to the empty matching.
2.107      ///
2.108 -    /// Sets the actual matching to the empty matching.
2.109 -    ///
2.110 +    /// This function sets the initial matching to the empty matching.
2.111      void init() {
2.112        createStructures();
2.113        for(NodeIt n(_graph); n != INVALID; ++n) {
2.114 @@ -432,9 +436,9 @@
2.115        }
2.116      }
2.117
2.118 -    ///\brief Finds an initial matching in a greedy way
2.119 +    /// \brief Find an initial matching in a greedy way.
2.120      ///
2.121 -    ///It finds an initial matching in a greedy way.
2.122 +    /// This function finds an initial matching in a greedy way.
2.123      void greedyInit() {
2.124        createStructures();
2.125        for (NodeIt n(_graph); n != INVALID; ++n) {
2.126 @@ -458,11 +462,11 @@
2.127      }
2.128
2.129
2.130 -    /// \brief Initialize the matching from a map containing.
2.131 +    /// \brief Initialize the matching from a map.
2.132      ///
2.133 -    /// Initialize the matching from a \c bool valued \c Edge map. This
2.134 -    /// map must have the property that there are no two incident edges
2.135 -    /// with true value, ie. it contains a matching.
2.136 +    /// This function initializes the matching from a \c bool valued edge
2.137 +    /// map. This map should have the property that there are no two incident
2.138 +    /// edges with \c true value, i.e. it really contains a matching.
2.139      /// \return \c true if the map contains a matching.
2.140      template <typename MatchingMap>
2.141      bool matchingInit(const MatchingMap& matching) {
2.142 @@ -489,9 +493,12 @@
2.143        return true;
2.144      }
2.145
2.146 -    /// \brief Starts Edmonds' algorithm
2.147 +    /// \brief Start Edmonds' algorithm
2.148      ///
2.149 -    /// If runs the original Edmonds' algorithm.
2.150 +    /// This function runs the original Edmonds' algorithm.
2.151 +    ///
2.152 +    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
2.153 +    /// called before using this function.
2.154      void startSparse() {
2.155        for(NodeIt n(_graph); n != INVALID; ++n) {
2.156          if ((*_status)[n] == UNMATCHED) {
2.157 @@ -503,10 +510,14 @@
2.158        }
2.159      }
2.160
2.161 -    /// \brief Starts Edmonds' algorithm.
2.162 +    /// \brief Start Edmonds' algorithm with a heuristic improvement
2.163 +    /// for dense graphs
2.164      ///
2.165 -    /// It runs Edmonds' algorithm with a heuristic of postponing
2.166 +    /// This function runs Edmonds' algorithm with a heuristic of postponing
2.167      /// shrinks, therefore resulting in a faster algorithm for dense graphs.
2.168 +    ///
2.169 +    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
2.170 +    /// called before using this function.
2.171      void startDense() {
2.172        for(NodeIt n(_graph); n != INVALID; ++n) {
2.173          if ((*_status)[n] == UNMATCHED) {
2.174 @@ -519,11 +530,11 @@
2.175      }
2.176
2.177
2.178 -    /// \brief Runs Edmonds' algorithm
2.179 +    /// \brief Run Edmonds' algorithm
2.180      ///
2.181 -    /// Runs Edmonds' algorithm for sparse graphs (<tt>m<2*n</tt>)
2.182 -    /// or Edmonds' algorithm with a heuristic of
2.183 -    /// postponing shrinks for dense graphs.
2.184 +    /// This function runs Edmonds' algorithm. An additional heuristic of
2.185 +    /// postponing shrinks is used for relatively dense graphs
2.186 +    /// (for which <tt>m>=2*n</tt> holds).
2.187      void run() {
2.188        if (countEdges(_graph) < 2 * countNodes(_graph)) {
2.189          greedyInit();
2.190 @@ -536,15 +547,15 @@
2.191
2.192      /// @}
2.193
2.194 -    /// \name Primal solution
2.195 -    /// Functions to get the primal solution, ie. the matching.
2.196 +    /// \name Primal Solution
2.197 +    /// Functions to get the primal solution, i.e. the maximum matching.
2.198
2.199      /// @{
2.200
2.201 -    ///\brief Returns the size of the current matching.
2.202 +    /// \brief Return the size (cardinality) of the matching.
2.203      ///
2.204 -    ///Returns the size of the current matching. After \ref
2.205 -    ///run() it returns the size of the maximum matching in the graph.
2.206 +    /// This function returns the size (cardinality) of the current matching.
2.207 +    /// After run() it returns the size of the maximum matching in the graph.
2.208      int matchingSize() const {
2.209        int size = 0;
2.210        for (NodeIt n(_graph); n != INVALID; ++n) {
2.211 @@ -555,25 +566,27 @@
2.212        return size / 2;
2.213      }
2.214
2.215 -    /// \brief Returns true when the edge is in the matching.
2.216 +    /// \brief Return \c true if the given edge is in the matching.
2.217      ///
2.218 -    /// Returns true when the edge is in the matching.
2.219 +    /// This function returns \c true if the given edge is in the current
2.220 +    /// matching.
2.221      bool matching(const Edge& edge) const {
2.222        return edge == (*_matching)[_graph.u(edge)];
2.223      }
2.224
2.225 -    /// \brief Returns the matching edge incident to the given node.
2.226 +    /// \brief Return the matching arc (or edge) incident to the given node.
2.227      ///
2.228 -    /// Returns the matching edge of a \c node in the actual matching or
2.229 -    /// INVALID if the \c node is not covered by the actual matching.
2.230 +    /// This function returns the matching arc (or edge) incident to the
2.231 +    /// given node in the current matching or \c INVALID if the node is
2.232 +    /// not covered by the matching.
2.233      Arc matching(const Node& n) const {
2.234        return (*_matching)[n];
2.235      }
2.236
2.237 -    ///\brief Returns the mate of a node in the actual matching.
2.238 +    /// \brief Return the mate of the given node.
2.239      ///
2.240 -    ///Returns the mate of a \c node in the actual matching or
2.241 -    ///INVALID if the \c node is not covered by the actual matching.
2.242 +    /// This function returns the mate of the given node in the current
2.243 +    /// matching or \c INVALID if the node is not covered by the matching.
2.244      Node mate(const Node& n) const {
2.245        return (*_matching)[n] != INVALID ?
2.246          _graph.target((*_matching)[n]) : INVALID;
2.247 @@ -581,23 +594,24 @@
2.248
2.249      /// @}
2.250
2.251 -    /// \name Dual solution
2.252 -    /// Functions to get the dual solution, ie. the decomposition.
2.253 +    /// \name Dual Solution
2.254 +    /// Functions to get the dual solution, i.e. the Gallai-Edmonds
2.255 +    /// decomposition.
2.256
2.257      /// @{
2.258
2.259 -    /// \brief Returns the class of the node in the Edmonds-Gallai
2.260 +    /// \brief Return the status of the given node in the Edmonds-Gallai
2.261      /// decomposition.
2.262      ///
2.263 -    /// Returns the class of the node in the Edmonds-Gallai
2.264 -    /// decomposition.
2.265 +    /// This function returns the \ref Status "status" of the given node
2.266 +    /// in the Edmonds-Gallai decomposition.
2.267      Status decomposition(const Node& n) const {
2.268        return (*_status)[n];
2.269      }
2.270
2.271 -    /// \brief Returns true when the node is in the barrier.
2.272 +    /// \brief Return \c true if the given node is in the barrier.
2.273      ///
2.274 -    /// Returns true when the node is in the barrier.
2.275 +    /// This function returns \c true if the given node is in the barrier.
2.276      bool barrier(const Node& n) const {
2.277        return (*_status)[n] == ODD;
2.278      }
2.279 @@ -615,10 +629,10 @@
2.280    /// on extensive use of priority queues and provides
2.281    /// \f$O(nm\log n)\f$ time complexity.
2.282    ///
2.283 -  /// The maximum weighted matching problem is to find undirected
2.284 -  /// edges in the graph with maximum overall weight and no two of
2.285 -  /// them shares their ends. The problem can be formulated with the
2.286 -  /// following linear program.
2.287 +  /// The maximum weighted matching problem is to find a subset of the
2.288 +  /// edges in an undirected graph with maximum overall weight for which
2.289 +  /// each node has at most one incident edge.
2.290 +  /// It can be formulated with the following linear program.
2.291    /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
2.292    /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
2.293        \quad \forall B\in\mathcal{O}\f] */
2.294 @@ -632,6 +646,7 @@
2.295    /// The algorithm calculates an optimal matching and a proof of the
2.296    /// optimality. The solution of the dual problem can be used to check
2.297    /// the result of the algorithm. The dual linear problem is the
2.298 +  /// following.
2.299    /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}
2.300        z_B \ge w_{uv} \quad \forall uv\in E\f] */
2.301    /// \f[y_u \ge 0 \quad \forall u \in V\f]
2.302 @@ -639,36 +654,43 @@
2.303    /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
2.304        \frac{\vert B \vert - 1}{2}z_B\f] */
2.305    ///
2.306 -  /// The algorithm can be executed with \c run() or the \c init() and
2.307 -  /// then the \c start() member functions. After it the matching can
2.308 -  /// be asked with \c matching() or mate() functions. The dual
2.309 -  /// solution can be get with \c nodeValue(), \c blossomNum() and \c
2.310 -  /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
2.311 -  /// "BlossomIt" nested class, which is able to iterate on the nodes
2.312 -  /// of a blossom. If the value type is integral then the dual
2.313 -  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
2.314 +  /// The algorithm can be executed with the run() function.
2.315 +  /// After it the matching (the primal solution) and the dual solution
2.316 +  /// can be obtained using the query functions and the
2.317 +  /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
2.318 +  /// which is able to iterate on the nodes of a blossom.
2.319 +  /// If the value type is integer, then the dual solution is multiplied
2.320 +  /// by \ref MaxWeightedMatching::dualScale "4".
2.321 +  ///
2.322 +  /// \tparam GR The graph type the algorithm runs on.
2.323 +  /// \tparam WM The type edge weight map. The default type is
2.324 +  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
2.325 +#ifdef DOXYGEN
2.326 +  template <typename GR, typename WM>
2.327 +#else
2.328    template <typename GR,
2.329              typename WM = typename GR::template EdgeMap<int> >
2.330 +#endif
2.331    class MaxWeightedMatching {
2.332    public:
2.333
2.334 -    ///\e
2.335 +    /// The graph type of the algorithm
2.336      typedef GR Graph;
2.337 -    ///\e
2.338 +    /// The type of the edge weight map
2.339      typedef WM WeightMap;
2.340 -    ///\e
2.341 +    /// The value type of the edge weights
2.342      typedef typename WeightMap::Value Value;
2.343
2.344 +    typedef typename Graph::template NodeMap<typename Graph::Arc>
2.345 +    MatchingMap;
2.346 +
2.347      /// \brief Scaling factor for dual solution
2.348      ///
2.349 -    /// Scaling factor for dual solution, it is equal to 4 or 1
2.350 +    /// Scaling factor for dual solution. It is equal to 4 or 1
2.351      /// according to the value type.
2.352      static const int dualScale =
2.353        std::numeric_limits<Value>::is_integer ? 4 : 1;
2.354
2.355 -    typedef typename Graph::template NodeMap<typename Graph::Arc>
2.356 -    MatchingMap;
2.357 -
2.358    private:
2.359
2.360      TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.361 @@ -1631,15 +1653,15 @@
2.362        destroyStructures();
2.363      }
2.364
2.365 -    /// \name Execution control
2.366 +    /// \name Execution Control
2.367      /// The simplest way to execute the algorithm is to use the
2.368 -    /// \c run() member function.
2.369 +    /// \ref run() member function.
2.370
2.371      ///@{
2.372
2.373      /// \brief Initialize the algorithm
2.374      ///
2.375 -    /// Initialize the algorithm
2.376 +    /// This function initializes the algorithm.
2.377      void init() {
2.378        createStructures();
2.379
2.380 @@ -1691,9 +1713,11 @@
2.381        }
2.382      }
2.383
2.384 -    /// \brief Starts the algorithm
2.385 +    /// \brief Start the algorithm
2.386      ///
2.387 -    /// Starts the algorithm
2.388 +    /// This function starts the algorithm.
2.389 +    ///
2.390 +    /// \pre \ref init() must be called before using this function.
2.391      void start() {
2.392        enum OpType {
2.393          D1, D2, D3, D4
2.394 @@ -1776,9 +1800,9 @@
2.395        extractMatching();
2.396      }
2.397
2.398 -    /// \brief Runs %MaxWeightedMatching algorithm.
2.399 +    /// \brief Run the algorithm.
2.400      ///
2.401 -    /// This method runs the %MaxWeightedMatching algorithm.
2.402 +    /// This method runs the \c %MaxWeightedMatching algorithm.
2.403      ///
2.404      /// \note mwm.run() is just a shortcut of the following code.
2.405      /// \code
2.406 @@ -1792,14 +1816,19 @@
2.407
2.408      /// @}
2.409
2.410 -    /// \name Primal solution
2.411 -    /// Functions to get the primal solution, ie. the matching.
2.412 +    /// \name Primal Solution
2.413 +    /// Functions to get the primal solution, i.e. the maximum weighted
2.414 +    /// matching.\n
2.415 +    /// Either \ref run() or \ref start() function should be called before
2.416 +    /// using them.
2.417
2.418      /// @{
2.419
2.420 -    /// \brief Returns the weight of the matching.
2.421 +    /// \brief Return the weight of the matching.
2.422      ///
2.423 -    /// Returns the weight of the matching.
2.424 +    /// This function returns the weight of the found matching.
2.425 +    ///
2.426 +    /// \pre Either run() or start() must be called before using this function.
2.427      Value matchingValue() const {
2.428        Value sum = 0;
2.429        for (NodeIt n(_graph); n != INVALID; ++n) {
2.430 @@ -1810,9 +1839,11 @@
2.431        return sum /= 2;
2.432      }
2.433
2.434 -    /// \brief Returns the cardinality of the matching.
2.435 +    /// \brief Return the size (cardinality) of the matching.
2.436      ///
2.437 -    /// Returns the cardinality of the matching.
2.438 +    /// This function returns the size (cardinality) of the found matching.
2.439 +    ///
2.440 +    /// \pre Either run() or start() must be called before using this function.
2.441      int matchingSize() const {
2.442        int num = 0;
2.443        for (NodeIt n(_graph); n != INVALID; ++n) {
2.444 @@ -1823,25 +1854,33 @@
2.445        return num /= 2;
2.446      }
2.447
2.448 -    /// \brief Returns true when the edge is in the matching.
2.449 +    /// \brief Return \c true if the given edge is in the matching.
2.450      ///
2.451 -    /// Returns true when the edge is in the matching.
2.452 +    /// This function returns \c true if the given edge is in the found
2.453 +    /// matching.
2.454 +    ///
2.455 +    /// \pre Either run() or start() must be called before using this function.
2.456      bool matching(const Edge& edge) const {
2.457        return edge == (*_matching)[_graph.u(edge)];
2.458      }
2.459
2.460 -    /// \brief Returns the incident matching arc.
2.461 +    /// \brief Return the matching arc (or edge) incident to the given node.
2.462      ///
2.463 -    /// Returns the incident matching arc from given node. If the
2.464 -    /// node is not matched then it gives back \c INVALID.
2.465 +    /// This function returns the matching arc (or edge) incident to the
2.466 +    /// given node in the found matching or \c INVALID if the node is
2.467 +    /// not covered by the matching.
2.468 +    ///
2.469 +    /// \pre Either run() or start() must be called before using this function.
2.470      Arc matching(const Node& node) const {
2.471        return (*_matching)[node];
2.472      }
2.473
2.474 -    /// \brief Returns the mate of the node.
2.475 +    /// \brief Return the mate of the given node.
2.476      ///
2.477 -    /// Returns the adjancent node in a mathcing arc. If the node is
2.478 -    /// not matched then it gives back \c INVALID.
2.479 +    /// This function returns the mate of the given node in the found
2.480 +    /// matching or \c INVALID if the node is not covered by the matching.
2.481 +    ///
2.482 +    /// \pre Either run() or start() must be called before using this function.
2.483      Node mate(const Node& node) const {
2.484        return (*_matching)[node] != INVALID ?
2.485          _graph.target((*_matching)[node]) : INVALID;
2.486 @@ -1849,15 +1888,20 @@
2.487
2.488      /// @}
2.489
2.490 -    /// \name Dual solution
2.491 -    /// Functions to get the dual solution.
2.492 +    /// \name Dual Solution
2.493 +    /// Functions to get the dual solution.\n
2.494 +    /// Either \ref run() or \ref start() function should be called before
2.495 +    /// using them.
2.496
2.497      /// @{
2.498
2.499 -    /// \brief Returns the value of the dual solution.
2.500 +    /// \brief Return the value of the dual solution.
2.501      ///
2.502 -    /// Returns the value of the dual solution. It should be equal to
2.503 -    /// the primal value scaled by \ref dualScale "dual scale".
2.504 +    /// This function returns the value of the dual solution.
2.505 +    /// It should be equal to the primal value scaled by \ref dualScale
2.506 +    /// "dual scale".
2.507 +    ///
2.508 +    /// \pre Either run() or start() must be called before using this function.
2.509      Value dualValue() const {
2.510        Value sum = 0;
2.511        for (NodeIt n(_graph); n != INVALID; ++n) {
2.512 @@ -1869,48 +1913,60 @@
2.513        return sum;
2.514      }
2.515
2.516 -    /// \brief Returns the value of the node.
2.517 +    /// \brief Return the dual value (potential) of the given node.
2.518      ///
2.519 -    /// Returns the the value of the node.
2.520 +    /// This function returns the dual value (potential) of the given node.
2.521 +    ///
2.522 +    /// \pre Either run() or start() must be called before using this function.
2.523      Value nodeValue(const Node& n) const {
2.524        return (*_node_potential)[n];
2.525      }
2.526
2.527 -    /// \brief Returns the number of the blossoms in the basis.
2.528 +    /// \brief Return the number of the blossoms in the basis.
2.529      ///
2.530 -    /// Returns the number of the blossoms in the basis.
2.531 +    /// This function returns the number of the blossoms in the basis.
2.532 +    ///
2.533 +    /// \pre Either run() or start() must be called before using this function.
2.534      /// \see BlossomIt
2.535      int blossomNum() const {
2.536        return _blossom_potential.size();
2.537      }
2.538
2.539 -
2.540 -    /// \brief Returns the number of the nodes in the blossom.
2.541 +    /// \brief Return the number of the nodes in the given blossom.
2.542      ///
2.543 -    /// Returns the number of the nodes in the blossom.
2.544 +    /// This function returns the number of the nodes in the given blossom.
2.545 +    ///
2.546 +    /// \pre Either run() or start() must be called before using this function.
2.547 +    /// \see BlossomIt
2.548      int blossomSize(int k) const {
2.549        return _blossom_potential[k].end - _blossom_potential[k].begin;
2.550      }
2.551
2.552 -    /// \brief Returns the value of the blossom.
2.553 +    /// \brief Return the dual value (ptential) of the given blossom.
2.554      ///
2.555 -    /// Returns the the value of the blossom.
2.556 -    /// \see BlossomIt
2.557 +    /// This function returns the dual value (ptential) of the given blossom.
2.558 +    ///
2.559 +    /// \pre Either run() or start() must be called before using this function.
2.560      Value blossomValue(int k) const {
2.561        return _blossom_potential[k].value;
2.562      }
2.563
2.564 -    /// \brief Iterator for obtaining the nodes of the blossom.
2.565 +    /// \brief Iterator for obtaining the nodes of a blossom.
2.566      ///
2.567 -    /// Iterator for obtaining the nodes of the blossom. This class
2.568 -    /// provides a common lemon style iterator for listing a
2.569 -    /// subset of the nodes.
2.570 +    /// This class provides an iterator for obtaining the nodes of the
2.571 +    /// given blossom. It lists a subset of the nodes.
2.572 +    /// Before using this iterator, you must allocate a
2.573 +    /// MaxWeightedMatching class and execute it.
2.574      class BlossomIt {
2.575      public:
2.576
2.577        /// \brief Constructor.
2.578        ///
2.579 -      /// Constructor to get the nodes of the variable.
2.580 +      /// Constructor to get the nodes of the given variable.
2.581 +      ///
2.582 +      /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
2.583 +      /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
2.584 +      /// called before initializing this iterator.
2.585        BlossomIt(const MaxWeightedMatching& algorithm, int variable)
2.586          : _algorithm(&algorithm)
2.587        {
2.588 @@ -1918,9 +1974,9 @@
2.589          _last = _algorithm->_blossom_potential[variable].end;
2.590        }
2.591
2.592 -      /// \brief Conversion to node.
2.593 +      /// \brief Conversion to \c Node.
2.594        ///
2.595 -      /// Conversion to node.
2.596 +      /// Conversion to \c Node.
2.597        operator Node() const {
2.598          return _algorithm->_blossom_node_list[_index];
2.599        }
2.600 @@ -1962,10 +2018,10 @@
2.601    /// is based on extensive use of priority queues and provides
2.602    /// \f$O(nm\log n)\f$ time complexity.
2.603    ///
2.604 -  /// The maximum weighted matching problem is to find undirected
2.605 -  /// edges in the graph with maximum overall weight and no two of
2.606 -  /// them shares their ends and covers all nodes. The problem can be
2.607 -  /// formulated with the following linear program.
2.608 +  /// The maximum weighted perfect matching problem is to find a subset of
2.609 +  /// the edges in an undirected graph with maximum overall weight for which
2.610 +  /// each node has exactly one incident edge.
2.611 +  /// It can be formulated with the following linear program.
2.612    /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]
2.613    /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
2.614        \quad \forall B\in\mathcal{O}\f] */
2.615 @@ -1979,27 +2035,38 @@
2.616    /// The algorithm calculates an optimal matching and a proof of the
2.617    /// optimality. The solution of the dual problem can be used to check
2.618    /// the result of the algorithm. The dual linear problem is the
2.619 +  /// following.
2.620    /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge
2.621        w_{uv} \quad \forall uv\in E\f] */
2.622    /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
2.623    /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
2.624        \frac{\vert B \vert - 1}{2}z_B\f] */
2.625    ///
2.626 -  /// The algorithm can be executed with \c run() or the \c init() and
2.627 -  /// then the \c start() member functions. After it the matching can
2.628 -  /// be asked with \c matching() or mate() functions. The dual
2.629 -  /// solution can be get with \c nodeValue(), \c blossomNum() and \c
2.630 -  /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
2.631 -  /// "BlossomIt" nested class which is able to iterate on the nodes
2.632 -  /// of a blossom. If the value type is integral then the dual
2.633 -  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
2.634 +  /// The algorithm can be executed with the run() function.
2.635 +  /// After it the matching (the primal solution) and the dual solution
2.636 +  /// can be obtained using the query functions and the
2.637 +  /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
2.638 +  /// which is able to iterate on the nodes of a blossom.
2.639 +  /// If the value type is integer, then the dual solution is multiplied
2.640 +  /// by \ref MaxWeightedMatching::dualScale "4".
2.641 +  ///
2.642 +  /// \tparam GR The graph type the algorithm runs on.
2.643 +  /// \tparam WM The type edge weight map. The default type is
2.644 +  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
2.645 +#ifdef DOXYGEN
2.646 +  template <typename GR, typename WM>
2.647 +#else
2.648    template <typename GR,
2.649              typename WM = typename GR::template EdgeMap<int> >
2.650 +#endif
2.651    class MaxWeightedPerfectMatching {
2.652    public:
2.653
2.654 +    /// The graph type of the algorithm
2.655      typedef GR Graph;
2.656 +    /// The type of the edge weight map
2.657      typedef WM WeightMap;
2.658 +    /// The value type of the edge weights
2.659      typedef typename WeightMap::Value Value;
2.660
2.661      /// \brief Scaling factor for dual solution
2.662 @@ -2818,15 +2885,15 @@
2.663        destroyStructures();
2.664      }
2.665
2.666 -    /// \name Execution control
2.667 +    /// \name Execution Control
2.668      /// The simplest way to execute the algorithm is to use the
2.669 -    /// \c run() member function.
2.670 +    /// \ref run() member function.
2.671
2.672      ///@{
2.673
2.674      /// \brief Initialize the algorithm
2.675      ///
2.676 -    /// Initialize the algorithm
2.677 +    /// This function initializes the algorithm.
2.678      void init() {
2.679        createStructures();
2.680
2.681 @@ -2874,9 +2941,11 @@
2.682        }
2.683      }
2.684
2.685 -    /// \brief Starts the algorithm
2.686 +    /// \brief Start the algorithm
2.687      ///
2.688 -    /// Starts the algorithm
2.689 +    /// This function starts the algorithm.
2.690 +    ///
2.691 +    /// \pre \ref init() must be called before using this function.
2.692      bool start() {
2.693        enum OpType {
2.694          D2, D3, D4
2.695 @@ -2940,14 +3009,14 @@
2.696        return true;
2.697      }
2.698
2.699 -    /// \brief Runs %MaxWeightedPerfectMatching algorithm.
2.700 +    /// \brief Run the algorithm.
2.701      ///
2.702 -    /// This method runs the %MaxWeightedPerfectMatching algorithm.
2.703 +    /// This method runs the \c %MaxWeightedPerfectMatching algorithm.
2.704      ///
2.705 -    /// \note mwm.run() is just a shortcut of the following code.
2.706 +    /// \note mwpm.run() is just a shortcut of the following code.
2.707      /// \code
2.708 -    ///   mwm.init();
2.709 -    ///   mwm.start();
2.710 +    ///   mwpm.init();
2.711 +    ///   mwpm.start();
2.712      /// \endcode
2.713      bool run() {
2.714        init();
2.715 @@ -2956,14 +3025,19 @@
2.716
2.717      /// @}
2.718
2.719 -    /// \name Primal solution
2.720 -    /// Functions to get the primal solution, ie. the matching.
2.721 +    /// \name Primal Solution
2.722 +    /// Functions to get the primal solution, i.e. the maximum weighted
2.723 +    /// perfect matching.\n
2.724 +    /// Either \ref run() or \ref start() function should be called before
2.725 +    /// using them.
2.726
2.727      /// @{
2.728
2.729 -    /// \brief Returns the matching value.
2.730 +    /// \brief Return the weight of the matching.
2.731      ///
2.732 -    /// Returns the matching value.
2.733 +    /// This function returns the weight of the found matching.
2.734 +    ///
2.735 +    /// \pre Either run() or start() must be called before using this function.
2.736      Value matchingValue() const {
2.737        Value sum = 0;
2.738        for (NodeIt n(_graph); n != INVALID; ++n) {
2.739 @@ -2974,38 +3048,53 @@
2.740        return sum /= 2;
2.741      }
2.742
2.743 -    /// \brief Returns true when the edge is in the matching.
2.744 +    /// \brief Return \c true if the given edge is in the matching.
2.745      ///
2.746 -    /// Returns true when the edge is in the matching.
2.747 +    /// This function returns \c true if the given edge is in the found
2.748 +    /// matching.
2.749 +    ///
2.750 +    /// \pre Either run() or start() must be called before using this function.
2.751      bool matching(const Edge& edge) const {
2.752        return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge;
2.753      }
2.754
2.755 -    /// \brief Returns the incident matching edge.
2.756 +    /// \brief Return the matching arc (or edge) incident to the given node.
2.757      ///
2.758 -    /// Returns the incident matching arc from given edge.
2.759 +    /// This function returns the matching arc (or edge) incident to the
2.760 +    /// given node in the found matching or \c INVALID if the node is
2.761 +    /// not covered by the matching.
2.762 +    ///
2.763 +    /// \pre Either run() or start() must be called before using this function.
2.764      Arc matching(const Node& node) const {
2.765        return (*_matching)[node];
2.766      }
2.767
2.768 -    /// \brief Returns the mate of the node.
2.769 +    /// \brief Return the mate of the given node.
2.770      ///
2.771 -    /// Returns the adjancent node in a mathcing arc.
2.772 +    /// This function returns the mate of the given node in the found
2.773 +    /// matching or \c INVALID if the node is not covered by the matching.
2.774 +    ///
2.775 +    /// \pre Either run() or start() must be called before using this function.
2.776      Node mate(const Node& node) const {
2.777        return _graph.target((*_matching)[node]);
2.778      }
2.779
2.780      /// @}
2.781
2.782 -    /// \name Dual solution
2.783 -    /// Functions to get the dual solution.
2.784 +    /// \name Dual Solution
2.785 +    /// Functions to get the dual solution.\n
2.786 +    /// Either \ref run() or \ref start() function should be called before
2.787 +    /// using them.
2.788
2.789      /// @{
2.790
2.791 -    /// \brief Returns the value of the dual solution.
2.792 +    /// \brief Return the value of the dual solution.
2.793      ///
2.794 -    /// Returns the value of the dual solution. It should be equal to
2.795 -    /// the primal value scaled by \ref dualScale "dual scale".
2.796 +    /// This function returns the value of the dual solution.
2.797 +    /// It should be equal to the primal value scaled by \ref dualScale
2.798 +    /// "dual scale".
2.799 +    ///
2.800 +    /// \pre Either run() or start() must be called before using this function.
2.801      Value dualValue() const {
2.802        Value sum = 0;
2.803        for (NodeIt n(_graph); n != INVALID; ++n) {
2.804 @@ -3017,48 +3106,60 @@
2.805        return sum;
2.806      }
2.807
2.808 -    /// \brief Returns the value of the node.
2.809 +    /// \brief Return the dual value (potential) of the given node.
2.810      ///
2.811 -    /// Returns the the value of the node.
2.812 +    /// This function returns the dual value (potential) of the given node.
2.813 +    ///
2.814 +    /// \pre Either run() or start() must be called before using this function.
2.815      Value nodeValue(const Node& n) const {
2.816        return (*_node_potential)[n];
2.817      }
2.818
2.819 -    /// \brief Returns the number of the blossoms in the basis.
2.820 +    /// \brief Return the number of the blossoms in the basis.
2.821      ///
2.822 -    /// Returns the number of the blossoms in the basis.
2.823 +    /// This function returns the number of the blossoms in the basis.
2.824 +    ///
2.825 +    /// \pre Either run() or start() must be called before using this function.
2.826      /// \see BlossomIt
2.827      int blossomNum() const {
2.828        return _blossom_potential.size();
2.829      }
2.830
2.831 -
2.832 -    /// \brief Returns the number of the nodes in the blossom.
2.833 +    /// \brief Return the number of the nodes in the given blossom.
2.834      ///
2.835 -    /// Returns the number of the nodes in the blossom.
2.836 +    /// This function returns the number of the nodes in the given blossom.
2.837 +    ///
2.838 +    /// \pre Either run() or start() must be called before using this function.
2.839 +    /// \see BlossomIt
2.840      int blossomSize(int k) const {
2.841        return _blossom_potential[k].end - _blossom_potential[k].begin;
2.842      }
2.843
2.844 -    /// \brief Returns the value of the blossom.
2.845 +    /// \brief Return the dual value (ptential) of the given blossom.
2.846      ///
2.847 -    /// Returns the the value of the blossom.
2.848 -    /// \see BlossomIt
2.849 +    /// This function returns the dual value (ptential) of the given blossom.
2.850 +    ///
2.851 +    /// \pre Either run() or start() must be called before using this function.
2.852      Value blossomValue(int k) const {
2.853        return _blossom_potential[k].value;
2.854      }
2.855
2.856 -    /// \brief Iterator for obtaining the nodes of the blossom.
2.857 +    /// \brief Iterator for obtaining the nodes of a blossom.
2.858      ///
2.859 -    /// Iterator for obtaining the nodes of the blossom. This class
2.860 -    /// provides a common lemon style iterator for listing a
2.861 -    /// subset of the nodes.
2.862 +    /// This class provides an iterator for obtaining the nodes of the
2.863 +    /// given blossom. It lists a subset of the nodes.
2.864 +    /// Before using this iterator, you must allocate a
2.865 +    /// MaxWeightedPerfectMatching class and execute it.
2.866      class BlossomIt {
2.867      public:
2.868
2.869        /// \brief Constructor.
2.870        ///
2.871 -      /// Constructor to get the nodes of the variable.
2.872 +      /// Constructor to get the nodes of the given variable.
2.873 +      ///
2.874 +      /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
2.875 +      /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
2.876 +      /// must be called before initializing this iterator.
2.877        BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
2.878          : _algorithm(&algorithm)
2.879        {
2.880 @@ -3066,9 +3167,9 @@
2.881          _last = _algorithm->_blossom_potential[variable].end;
2.882        }
2.883
2.884 -      /// \brief Conversion to node.
2.885 +      /// \brief Conversion to \c Node.
2.886        ///
2.887 -      /// Conversion to node.
2.888 +      /// Conversion to \c Node.
2.889        operator Node() const {
2.890          return _algorithm->_blossom_node_list[_index];
2.891        }
2.892 @@ -3083,12 +3184,12 @@
2.893
2.894        /// \brief Validity checking
2.895        ///
2.896 -      /// Checks whether the iterator is invalid.
2.897 +      /// This function checks whether the iterator is invalid.
2.898        bool operator==(Invalid) const { return _index == _last; }
2.899
2.900        /// \brief Validity checking
2.901        ///
2.902 -      /// Checks whether the iterator is valid.
2.903 +      /// This function checks whether the iterator is valid.
2.904        bool operator!=(Invalid) const { return _index != _last; }
2.905
2.906      private:
2.907 @@ -3101,7 +3202,6 @@
2.908
2.909    };
2.910
2.911 -
2.912  } //END OF NAMESPACE LEMON
2.913
2.914  #endif //LEMON_MAX_MATCHING_H

     3.1 --- a/test/max_matching_test.cc	Wed Apr 15 07:13:30 2009 +0100
3.2 +++ b/test/max_matching_test.cc	Wed Apr 15 12:01:14 2009 +0200
3.3 @@ -20,12 +20,14 @@
3.4  #include <sstream>
3.5  #include <vector>
3.6  #include <queue>
3.7 -#include <lemon/math.h>
3.8  #include <cstdlib>
3.9
3.10  #include <lemon/max_matching.h>
3.11  #include <lemon/smart_graph.h>
3.12 +#include <lemon/concepts/graph.h>
3.13 +#include <lemon/concepts/maps.h>
3.15 +#include <lemon/math.h>
3.16
3.17  #include "test_tools.h"
3.18
3.19 @@ -110,6 +112,108 @@
3.20    "5 2  6      539\n",
3.21  };
3.22
3.23 +void checkMaxMatchingCompile()
3.24 +{
3.25 +  typedef concepts::Graph Graph;
3.26 +  typedef Graph::Node Node;
3.27 +  typedef Graph::Edge Edge;
3.28 +  typedef Graph::EdgeMap<bool> MatMap;
3.29 +
3.30 +  Graph g;
3.31 +  Node n;
3.32 +  Edge e;
3.33 +  MatMap mat(g);
3.34 +
3.35 +  MaxMatching<Graph> mat_test(g);
3.36 +  const MaxMatching<Graph>&
3.37 +    const_mat_test = mat_test;
3.38 +
3.39 +  mat_test.init();
3.40 +  mat_test.greedyInit();
3.41 +  mat_test.matchingInit(mat);
3.42 +  mat_test.startSparse();
3.43 +  mat_test.startDense();
3.44 +  mat_test.run();
3.45 +
3.46 +  const_mat_test.matchingSize();
3.47 +  const_mat_test.matching(e);
3.48 +  const_mat_test.matching(n);
3.49 +  const_mat_test.mate(n);
3.50 +
3.51 +  MaxMatching<Graph>::Status stat =
3.52 +    const_mat_test.decomposition(n);
3.53 +  const_mat_test.barrier(n);
3.54 +
3.55 +  ignore_unused_variable_warning(stat);
3.56 +}
3.57 +
3.58 +void checkMaxWeightedMatchingCompile()
3.59 +{
3.60 +  typedef concepts::Graph Graph;
3.61 +  typedef Graph::Node Node;
3.62 +  typedef Graph::Edge Edge;
3.63 +  typedef Graph::EdgeMap<int> WeightMap;
3.64 +
3.65 +  Graph g;
3.66 +  Node n;
3.67 +  Edge e;
3.68 +  WeightMap w(g);
3.69 +
3.70 +  MaxWeightedMatching<Graph> mat_test(g, w);
3.71 +  const MaxWeightedMatching<Graph>&
3.72 +    const_mat_test = mat_test;
3.73 +
3.74 +  mat_test.init();
3.75 +  mat_test.start();
3.76 +  mat_test.run();
3.77 +
3.78 +  const_mat_test.matchingValue();
3.79 +  const_mat_test.matchingSize();
3.80 +  const_mat_test.matching(e);
3.81 +  const_mat_test.matching(n);
3.82 +  const_mat_test.mate(n);
3.83 +
3.84 +  int k = 0;
3.85 +  const_mat_test.dualValue();
3.86 +  const_mat_test.nodeValue(n);
3.87 +  const_mat_test.blossomNum();
3.88 +  const_mat_test.blossomSize(k);
3.89 +  const_mat_test.blossomValue(k);
3.90 +}
3.91 +
3.92 +void checkMaxWeightedPerfectMatchingCompile()
3.93 +{
3.94 +  typedef concepts::Graph Graph;
3.95 +  typedef Graph::Node Node;
3.96 +  typedef Graph::Edge Edge;
3.97 +  typedef Graph::EdgeMap<int> WeightMap;
3.98 +
3.99 +  Graph g;
3.100 +  Node n;
3.101 +  Edge e;
3.102 +  WeightMap w(g);
3.103 +
3.104 +  MaxWeightedPerfectMatching<Graph> mat_test(g, w);
3.105 +  const MaxWeightedPerfectMatching<Graph>&
3.106 +    const_mat_test = mat_test;
3.107 +
3.108 +  mat_test.init();
3.109 +  mat_test.start();
3.110 +  mat_test.run();
3.111 +
3.112 +  const_mat_test.matchingValue();
3.113 +  const_mat_test.matching(e);
3.114 +  const_mat_test.matching(n);
3.115 +  const_mat_test.mate(n);
3.116 +
3.117 +  int k = 0;
3.118 +  const_mat_test.dualValue();
3.119 +  const_mat_test.nodeValue(n);
3.120 +  const_mat_test.blossomNum();
3.121 +  const_mat_test.blossomSize(k);
3.122 +  const_mat_test.blossomValue(k);
3.123 +}
3.124 +
3.125  void checkMatching(const SmartGraph& graph,
3.126                     const MaxMatching<SmartGraph>& mm) {
3.127    int num = 0;