Imporvements for the matching algorithms (#264)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 12:01:14 +0200
changeset 590b61354458b59
parent 589 630c4898c548
child 593 7ac52d6a268e
Imporvements for the matching algorithms (#264)
doc/groups.dox
lemon/max_matching.h
test/max_matching_test.cc
     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.14  #include <lemon/lgf_reader.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;