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;