1.1 --- a/lemon/max_matching.h Wed Apr 15 07:13:30 2009 +0100
1.2 +++ b/lemon/max_matching.h Wed Apr 15 12:01:14 2009 +0200
1.3 @@ -37,42 +37,51 @@
1.4
1.5 /// \ingroup matching
1.6 ///
1.7 - /// \brief Edmonds' alternating forest maximum matching algorithm.
1.8 + /// \brief Maximum cardinality matching in general graphs
1.9 ///
1.10 - /// This class implements Edmonds' alternating forest matching
1.11 - /// algorithm. The algorithm can be started from an arbitrary initial
1.12 - /// matching (the default is the empty one)
1.13 + /// This class implements Edmonds' alternating forest matching algorithm
1.14 + /// for finding a maximum cardinality matching in a general graph.
1.15 + /// It can be started from an arbitrary initial matching
1.16 + /// (the default is the empty one).
1.17 ///
1.18 /// The dual solution of the problem is a map of the nodes to
1.19 - /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
1.20 - /// MATCHED/C showing the Gallai-Edmonds decomposition of the
1.21 - /// graph. The nodes in \c EVEN/D induce a graph with
1.22 - /// factor-critical components, the nodes in \c ODD/A form the
1.23 - /// barrier, and the nodes in \c MATCHED/C induce a graph having a
1.24 - /// perfect matching. The number of the factor-critical components
1.25 + /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D),
1.26 + /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds
1.27 + /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph
1.28 + /// with factor-critical components, the nodes in \c ODD/A form the
1.29 + /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having
1.30 + /// a perfect matching. The number of the factor-critical components
1.31 /// minus the number of barrier nodes is a lower bound on the
1.32 /// unmatched nodes, and the matching is optimal if and only if this bound is
1.33 - /// tight. This decomposition can be attained by calling \c
1.34 + /// tight. This decomposition can be obtained by calling \c
1.35 /// decomposition() after running the algorithm.
1.36 ///
1.37 - /// \param GR The graph type the algorithm runs on.
1.38 + /// \tparam GR The graph type the algorithm runs on.
1.39 template <typename GR>
1.40 class MaxMatching {
1.41 public:
1.42
1.43 + /// The graph type of the algorithm
1.44 typedef GR Graph;
1.45 typedef typename Graph::template NodeMap<typename Graph::Arc>
1.46 MatchingMap;
1.47
1.48 - ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
1.49 + ///\brief Status constants for Gallai-Edmonds decomposition.
1.50 ///
1.51 - ///Indicates the Gallai-Edmonds decomposition of the graph. The
1.52 - ///nodes with Status \c EVEN/D induce a graph with factor-critical
1.53 - ///components, the nodes in \c ODD/A form the canonical barrier,
1.54 - ///and the nodes in \c MATCHED/C induce a graph having a perfect
1.55 - ///matching.
1.56 + ///These constants are used for indicating the Gallai-Edmonds
1.57 + ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
1.58 + ///induce a subgraph with factor-critical components, the nodes with
1.59 + ///status \c ODD (or \c A) form the canonical barrier, and the nodes
1.60 + ///with status \c MATCHED (or \c C) induce a subgraph having a
1.61 + ///perfect matching.
1.62 enum Status {
1.63 - EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2
1.64 + EVEN = 1, ///< = 1. (\c D is an alias for \c EVEN.)
1.65 + D = 1,
1.66 + MATCHED = 0, ///< = 0. (\c C is an alias for \c MATCHED.)
1.67 + C = 0,
1.68 + ODD = -1, ///< = -1. (\c A is an alias for \c ODD.)
1.69 + A = -1,
1.70 + UNMATCHED = -2 ///< = -2.
1.71 };
1.72
1.73 typedef typename Graph::template NodeMap<Status> StatusMap;
1.74 @@ -338,8 +347,6 @@
1.75 (*_blossom_rep)[_blossom_set->find(nca)] = nca;
1.76 }
1.77
1.78 -
1.79 -
1.80 void extendOnArc(const Arc& a) {
1.81 Node base = _graph.source(a);
1.82 Node odd = _graph.target(a);
1.83 @@ -408,22 +415,19 @@
1.84 destroyStructures();
1.85 }
1.86
1.87 - /// \name Execution control
1.88 + /// \name Execution Control
1.89 /// The simplest way to execute the algorithm is to use the
1.90 - /// \c run() member function.
1.91 - /// \n
1.92 -
1.93 - /// If you need better control on the execution, you must call
1.94 - /// \ref init(), \ref greedyInit() or \ref matchingInit()
1.95 - /// functions first, then you can start the algorithm with the \ref
1.96 - /// startSparse() or startDense() functions.
1.97 + /// \c run() member function.\n
1.98 + /// If you need better control on the execution, you have to call
1.99 + /// one of the functions \ref init(), \ref greedyInit() or
1.100 + /// \ref matchingInit() first, then you can start the algorithm with
1.101 + /// \ref startSparse() or \ref startDense().
1.102
1.103 ///@{
1.104
1.105 - /// \brief Sets the actual matching to the empty matching.
1.106 + /// \brief Set the initial matching to the empty matching.
1.107 ///
1.108 - /// Sets the actual matching to the empty matching.
1.109 - ///
1.110 + /// This function sets the initial matching to the empty matching.
1.111 void init() {
1.112 createStructures();
1.113 for(NodeIt n(_graph); n != INVALID; ++n) {
1.114 @@ -432,9 +436,9 @@
1.115 }
1.116 }
1.117
1.118 - ///\brief Finds an initial matching in a greedy way
1.119 + /// \brief Find an initial matching in a greedy way.
1.120 ///
1.121 - ///It finds an initial matching in a greedy way.
1.122 + /// This function finds an initial matching in a greedy way.
1.123 void greedyInit() {
1.124 createStructures();
1.125 for (NodeIt n(_graph); n != INVALID; ++n) {
1.126 @@ -458,11 +462,11 @@
1.127 }
1.128
1.129
1.130 - /// \brief Initialize the matching from a map containing.
1.131 + /// \brief Initialize the matching from a map.
1.132 ///
1.133 - /// Initialize the matching from a \c bool valued \c Edge map. This
1.134 - /// map must have the property that there are no two incident edges
1.135 - /// with true value, ie. it contains a matching.
1.136 + /// This function initializes the matching from a \c bool valued edge
1.137 + /// map. This map should have the property that there are no two incident
1.138 + /// edges with \c true value, i.e. it really contains a matching.
1.139 /// \return \c true if the map contains a matching.
1.140 template <typename MatchingMap>
1.141 bool matchingInit(const MatchingMap& matching) {
1.142 @@ -489,9 +493,12 @@
1.143 return true;
1.144 }
1.145
1.146 - /// \brief Starts Edmonds' algorithm
1.147 + /// \brief Start Edmonds' algorithm
1.148 ///
1.149 - /// If runs the original Edmonds' algorithm.
1.150 + /// This function runs the original Edmonds' algorithm.
1.151 + ///
1.152 + /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
1.153 + /// called before using this function.
1.154 void startSparse() {
1.155 for(NodeIt n(_graph); n != INVALID; ++n) {
1.156 if ((*_status)[n] == UNMATCHED) {
1.157 @@ -503,10 +510,14 @@
1.158 }
1.159 }
1.160
1.161 - /// \brief Starts Edmonds' algorithm.
1.162 + /// \brief Start Edmonds' algorithm with a heuristic improvement
1.163 + /// for dense graphs
1.164 ///
1.165 - /// It runs Edmonds' algorithm with a heuristic of postponing
1.166 + /// This function runs Edmonds' algorithm with a heuristic of postponing
1.167 /// shrinks, therefore resulting in a faster algorithm for dense graphs.
1.168 + ///
1.169 + /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
1.170 + /// called before using this function.
1.171 void startDense() {
1.172 for(NodeIt n(_graph); n != INVALID; ++n) {
1.173 if ((*_status)[n] == UNMATCHED) {
1.174 @@ -519,11 +530,11 @@
1.175 }
1.176
1.177
1.178 - /// \brief Runs Edmonds' algorithm
1.179 + /// \brief Run Edmonds' algorithm
1.180 ///
1.181 - /// Runs Edmonds' algorithm for sparse graphs (<tt>m<2*n</tt>)
1.182 - /// or Edmonds' algorithm with a heuristic of
1.183 - /// postponing shrinks for dense graphs.
1.184 + /// This function runs Edmonds' algorithm. An additional heuristic of
1.185 + /// postponing shrinks is used for relatively dense graphs
1.186 + /// (for which <tt>m>=2*n</tt> holds).
1.187 void run() {
1.188 if (countEdges(_graph) < 2 * countNodes(_graph)) {
1.189 greedyInit();
1.190 @@ -536,15 +547,15 @@
1.191
1.192 /// @}
1.193
1.194 - /// \name Primal solution
1.195 - /// Functions to get the primal solution, ie. the matching.
1.196 + /// \name Primal Solution
1.197 + /// Functions to get the primal solution, i.e. the maximum matching.
1.198
1.199 /// @{
1.200
1.201 - ///\brief Returns the size of the current matching.
1.202 + /// \brief Return the size (cardinality) of the matching.
1.203 ///
1.204 - ///Returns the size of the current matching. After \ref
1.205 - ///run() it returns the size of the maximum matching in the graph.
1.206 + /// This function returns the size (cardinality) of the current matching.
1.207 + /// After run() it returns the size of the maximum matching in the graph.
1.208 int matchingSize() const {
1.209 int size = 0;
1.210 for (NodeIt n(_graph); n != INVALID; ++n) {
1.211 @@ -555,25 +566,27 @@
1.212 return size / 2;
1.213 }
1.214
1.215 - /// \brief Returns true when the edge is in the matching.
1.216 + /// \brief Return \c true if the given edge is in the matching.
1.217 ///
1.218 - /// Returns true when the edge is in the matching.
1.219 + /// This function returns \c true if the given edge is in the current
1.220 + /// matching.
1.221 bool matching(const Edge& edge) const {
1.222 return edge == (*_matching)[_graph.u(edge)];
1.223 }
1.224
1.225 - /// \brief Returns the matching edge incident to the given node.
1.226 + /// \brief Return the matching arc (or edge) incident to the given node.
1.227 ///
1.228 - /// Returns the matching edge of a \c node in the actual matching or
1.229 - /// INVALID if the \c node is not covered by the actual matching.
1.230 + /// This function returns the matching arc (or edge) incident to the
1.231 + /// given node in the current matching or \c INVALID if the node is
1.232 + /// not covered by the matching.
1.233 Arc matching(const Node& n) const {
1.234 return (*_matching)[n];
1.235 }
1.236
1.237 - ///\brief Returns the mate of a node in the actual matching.
1.238 + /// \brief Return the mate of the given node.
1.239 ///
1.240 - ///Returns the mate of a \c node in the actual matching or
1.241 - ///INVALID if the \c node is not covered by the actual matching.
1.242 + /// This function returns the mate of the given node in the current
1.243 + /// matching or \c INVALID if the node is not covered by the matching.
1.244 Node mate(const Node& n) const {
1.245 return (*_matching)[n] != INVALID ?
1.246 _graph.target((*_matching)[n]) : INVALID;
1.247 @@ -581,23 +594,24 @@
1.248
1.249 /// @}
1.250
1.251 - /// \name Dual solution
1.252 - /// Functions to get the dual solution, ie. the decomposition.
1.253 + /// \name Dual Solution
1.254 + /// Functions to get the dual solution, i.e. the Gallai-Edmonds
1.255 + /// decomposition.
1.256
1.257 /// @{
1.258
1.259 - /// \brief Returns the class of the node in the Edmonds-Gallai
1.260 + /// \brief Return the status of the given node in the Edmonds-Gallai
1.261 /// decomposition.
1.262 ///
1.263 - /// Returns the class of the node in the Edmonds-Gallai
1.264 - /// decomposition.
1.265 + /// This function returns the \ref Status "status" of the given node
1.266 + /// in the Edmonds-Gallai decomposition.
1.267 Status decomposition(const Node& n) const {
1.268 return (*_status)[n];
1.269 }
1.270
1.271 - /// \brief Returns true when the node is in the barrier.
1.272 + /// \brief Return \c true if the given node is in the barrier.
1.273 ///
1.274 - /// Returns true when the node is in the barrier.
1.275 + /// This function returns \c true if the given node is in the barrier.
1.276 bool barrier(const Node& n) const {
1.277 return (*_status)[n] == ODD;
1.278 }
1.279 @@ -615,10 +629,10 @@
1.280 /// on extensive use of priority queues and provides
1.281 /// \f$O(nm\log n)\f$ time complexity.
1.282 ///
1.283 - /// The maximum weighted matching problem is to find undirected
1.284 - /// edges in the graph with maximum overall weight and no two of
1.285 - /// them shares their ends. The problem can be formulated with the
1.286 - /// following linear program.
1.287 + /// The maximum weighted matching problem is to find a subset of the
1.288 + /// edges in an undirected graph with maximum overall weight for which
1.289 + /// each node has at most one incident edge.
1.290 + /// It can be formulated with the following linear program.
1.291 /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
1.292 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
1.293 \quad \forall B\in\mathcal{O}\f] */
1.294 @@ -632,6 +646,7 @@
1.295 /// The algorithm calculates an optimal matching and a proof of the
1.296 /// optimality. The solution of the dual problem can be used to check
1.297 /// the result of the algorithm. The dual linear problem is the
1.298 + /// following.
1.299 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}
1.300 z_B \ge w_{uv} \quad \forall uv\in E\f] */
1.301 /// \f[y_u \ge 0 \quad \forall u \in V\f]
1.302 @@ -639,36 +654,43 @@
1.303 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
1.304 \frac{\vert B \vert - 1}{2}z_B\f] */
1.305 ///
1.306 - /// The algorithm can be executed with \c run() or the \c init() and
1.307 - /// then the \c start() member functions. After it the matching can
1.308 - /// be asked with \c matching() or mate() functions. The dual
1.309 - /// solution can be get with \c nodeValue(), \c blossomNum() and \c
1.310 - /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
1.311 - /// "BlossomIt" nested class, which is able to iterate on the nodes
1.312 - /// of a blossom. If the value type is integral then the dual
1.313 - /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
1.314 + /// The algorithm can be executed with the run() function.
1.315 + /// After it the matching (the primal solution) and the dual solution
1.316 + /// can be obtained using the query functions and the
1.317 + /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
1.318 + /// which is able to iterate on the nodes of a blossom.
1.319 + /// If the value type is integer, then the dual solution is multiplied
1.320 + /// by \ref MaxWeightedMatching::dualScale "4".
1.321 + ///
1.322 + /// \tparam GR The graph type the algorithm runs on.
1.323 + /// \tparam WM The type edge weight map. The default type is
1.324 + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
1.325 +#ifdef DOXYGEN
1.326 + template <typename GR, typename WM>
1.327 +#else
1.328 template <typename GR,
1.329 typename WM = typename GR::template EdgeMap<int> >
1.330 +#endif
1.331 class MaxWeightedMatching {
1.332 public:
1.333
1.334 - ///\e
1.335 + /// The graph type of the algorithm
1.336 typedef GR Graph;
1.337 - ///\e
1.338 + /// The type of the edge weight map
1.339 typedef WM WeightMap;
1.340 - ///\e
1.341 + /// The value type of the edge weights
1.342 typedef typename WeightMap::Value Value;
1.343
1.344 + typedef typename Graph::template NodeMap<typename Graph::Arc>
1.345 + MatchingMap;
1.346 +
1.347 /// \brief Scaling factor for dual solution
1.348 ///
1.349 - /// Scaling factor for dual solution, it is equal to 4 or 1
1.350 + /// Scaling factor for dual solution. It is equal to 4 or 1
1.351 /// according to the value type.
1.352 static const int dualScale =
1.353 std::numeric_limits<Value>::is_integer ? 4 : 1;
1.354
1.355 - typedef typename Graph::template NodeMap<typename Graph::Arc>
1.356 - MatchingMap;
1.357 -
1.358 private:
1.359
1.360 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.361 @@ -1631,15 +1653,15 @@
1.362 destroyStructures();
1.363 }
1.364
1.365 - /// \name Execution control
1.366 + /// \name Execution Control
1.367 /// The simplest way to execute the algorithm is to use the
1.368 - /// \c run() member function.
1.369 + /// \ref run() member function.
1.370
1.371 ///@{
1.372
1.373 /// \brief Initialize the algorithm
1.374 ///
1.375 - /// Initialize the algorithm
1.376 + /// This function initializes the algorithm.
1.377 void init() {
1.378 createStructures();
1.379
1.380 @@ -1691,9 +1713,11 @@
1.381 }
1.382 }
1.383
1.384 - /// \brief Starts the algorithm
1.385 + /// \brief Start the algorithm
1.386 ///
1.387 - /// Starts the algorithm
1.388 + /// This function starts the algorithm.
1.389 + ///
1.390 + /// \pre \ref init() must be called before using this function.
1.391 void start() {
1.392 enum OpType {
1.393 D1, D2, D3, D4
1.394 @@ -1776,9 +1800,9 @@
1.395 extractMatching();
1.396 }
1.397
1.398 - /// \brief Runs %MaxWeightedMatching algorithm.
1.399 + /// \brief Run the algorithm.
1.400 ///
1.401 - /// This method runs the %MaxWeightedMatching algorithm.
1.402 + /// This method runs the \c %MaxWeightedMatching algorithm.
1.403 ///
1.404 /// \note mwm.run() is just a shortcut of the following code.
1.405 /// \code
1.406 @@ -1792,14 +1816,19 @@
1.407
1.408 /// @}
1.409
1.410 - /// \name Primal solution
1.411 - /// Functions to get the primal solution, ie. the matching.
1.412 + /// \name Primal Solution
1.413 + /// Functions to get the primal solution, i.e. the maximum weighted
1.414 + /// matching.\n
1.415 + /// Either \ref run() or \ref start() function should be called before
1.416 + /// using them.
1.417
1.418 /// @{
1.419
1.420 - /// \brief Returns the weight of the matching.
1.421 + /// \brief Return the weight of the matching.
1.422 ///
1.423 - /// Returns the weight of the matching.
1.424 + /// This function returns the weight of the found matching.
1.425 + ///
1.426 + /// \pre Either run() or start() must be called before using this function.
1.427 Value matchingValue() const {
1.428 Value sum = 0;
1.429 for (NodeIt n(_graph); n != INVALID; ++n) {
1.430 @@ -1810,9 +1839,11 @@
1.431 return sum /= 2;
1.432 }
1.433
1.434 - /// \brief Returns the cardinality of the matching.
1.435 + /// \brief Return the size (cardinality) of the matching.
1.436 ///
1.437 - /// Returns the cardinality of the matching.
1.438 + /// This function returns the size (cardinality) of the found matching.
1.439 + ///
1.440 + /// \pre Either run() or start() must be called before using this function.
1.441 int matchingSize() const {
1.442 int num = 0;
1.443 for (NodeIt n(_graph); n != INVALID; ++n) {
1.444 @@ -1823,25 +1854,33 @@
1.445 return num /= 2;
1.446 }
1.447
1.448 - /// \brief Returns true when the edge is in the matching.
1.449 + /// \brief Return \c true if the given edge is in the matching.
1.450 ///
1.451 - /// Returns true when the edge is in the matching.
1.452 + /// This function returns \c true if the given edge is in the found
1.453 + /// matching.
1.454 + ///
1.455 + /// \pre Either run() or start() must be called before using this function.
1.456 bool matching(const Edge& edge) const {
1.457 return edge == (*_matching)[_graph.u(edge)];
1.458 }
1.459
1.460 - /// \brief Returns the incident matching arc.
1.461 + /// \brief Return the matching arc (or edge) incident to the given node.
1.462 ///
1.463 - /// Returns the incident matching arc from given node. If the
1.464 - /// node is not matched then it gives back \c INVALID.
1.465 + /// This function returns the matching arc (or edge) incident to the
1.466 + /// given node in the found matching or \c INVALID if the node is
1.467 + /// not covered by the matching.
1.468 + ///
1.469 + /// \pre Either run() or start() must be called before using this function.
1.470 Arc matching(const Node& node) const {
1.471 return (*_matching)[node];
1.472 }
1.473
1.474 - /// \brief Returns the mate of the node.
1.475 + /// \brief Return the mate of the given node.
1.476 ///
1.477 - /// Returns the adjancent node in a mathcing arc. If the node is
1.478 - /// not matched then it gives back \c INVALID.
1.479 + /// This function returns the mate of the given node in the found
1.480 + /// matching or \c INVALID if the node is not covered by the matching.
1.481 + ///
1.482 + /// \pre Either run() or start() must be called before using this function.
1.483 Node mate(const Node& node) const {
1.484 return (*_matching)[node] != INVALID ?
1.485 _graph.target((*_matching)[node]) : INVALID;
1.486 @@ -1849,15 +1888,20 @@
1.487
1.488 /// @}
1.489
1.490 - /// \name Dual solution
1.491 - /// Functions to get the dual solution.
1.492 + /// \name Dual Solution
1.493 + /// Functions to get the dual solution.\n
1.494 + /// Either \ref run() or \ref start() function should be called before
1.495 + /// using them.
1.496
1.497 /// @{
1.498
1.499 - /// \brief Returns the value of the dual solution.
1.500 + /// \brief Return the value of the dual solution.
1.501 ///
1.502 - /// Returns the value of the dual solution. It should be equal to
1.503 - /// the primal value scaled by \ref dualScale "dual scale".
1.504 + /// This function returns the value of the dual solution.
1.505 + /// It should be equal to the primal value scaled by \ref dualScale
1.506 + /// "dual scale".
1.507 + ///
1.508 + /// \pre Either run() or start() must be called before using this function.
1.509 Value dualValue() const {
1.510 Value sum = 0;
1.511 for (NodeIt n(_graph); n != INVALID; ++n) {
1.512 @@ -1869,48 +1913,60 @@
1.513 return sum;
1.514 }
1.515
1.516 - /// \brief Returns the value of the node.
1.517 + /// \brief Return the dual value (potential) of the given node.
1.518 ///
1.519 - /// Returns the the value of the node.
1.520 + /// This function returns the dual value (potential) of the given node.
1.521 + ///
1.522 + /// \pre Either run() or start() must be called before using this function.
1.523 Value nodeValue(const Node& n) const {
1.524 return (*_node_potential)[n];
1.525 }
1.526
1.527 - /// \brief Returns the number of the blossoms in the basis.
1.528 + /// \brief Return the number of the blossoms in the basis.
1.529 ///
1.530 - /// Returns the number of the blossoms in the basis.
1.531 + /// This function returns the number of the blossoms in the basis.
1.532 + ///
1.533 + /// \pre Either run() or start() must be called before using this function.
1.534 /// \see BlossomIt
1.535 int blossomNum() const {
1.536 return _blossom_potential.size();
1.537 }
1.538
1.539 -
1.540 - /// \brief Returns the number of the nodes in the blossom.
1.541 + /// \brief Return the number of the nodes in the given blossom.
1.542 ///
1.543 - /// Returns the number of the nodes in the blossom.
1.544 + /// This function returns the number of the nodes in the given blossom.
1.545 + ///
1.546 + /// \pre Either run() or start() must be called before using this function.
1.547 + /// \see BlossomIt
1.548 int blossomSize(int k) const {
1.549 return _blossom_potential[k].end - _blossom_potential[k].begin;
1.550 }
1.551
1.552 - /// \brief Returns the value of the blossom.
1.553 + /// \brief Return the dual value (ptential) of the given blossom.
1.554 ///
1.555 - /// Returns the the value of the blossom.
1.556 - /// \see BlossomIt
1.557 + /// This function returns the dual value (ptential) of the given blossom.
1.558 + ///
1.559 + /// \pre Either run() or start() must be called before using this function.
1.560 Value blossomValue(int k) const {
1.561 return _blossom_potential[k].value;
1.562 }
1.563
1.564 - /// \brief Iterator for obtaining the nodes of the blossom.
1.565 + /// \brief Iterator for obtaining the nodes of a blossom.
1.566 ///
1.567 - /// Iterator for obtaining the nodes of the blossom. This class
1.568 - /// provides a common lemon style iterator for listing a
1.569 - /// subset of the nodes.
1.570 + /// This class provides an iterator for obtaining the nodes of the
1.571 + /// given blossom. It lists a subset of the nodes.
1.572 + /// Before using this iterator, you must allocate a
1.573 + /// MaxWeightedMatching class and execute it.
1.574 class BlossomIt {
1.575 public:
1.576
1.577 /// \brief Constructor.
1.578 ///
1.579 - /// Constructor to get the nodes of the variable.
1.580 + /// Constructor to get the nodes of the given variable.
1.581 + ///
1.582 + /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
1.583 + /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
1.584 + /// called before initializing this iterator.
1.585 BlossomIt(const MaxWeightedMatching& algorithm, int variable)
1.586 : _algorithm(&algorithm)
1.587 {
1.588 @@ -1918,9 +1974,9 @@
1.589 _last = _algorithm->_blossom_potential[variable].end;
1.590 }
1.591
1.592 - /// \brief Conversion to node.
1.593 + /// \brief Conversion to \c Node.
1.594 ///
1.595 - /// Conversion to node.
1.596 + /// Conversion to \c Node.
1.597 operator Node() const {
1.598 return _algorithm->_blossom_node_list[_index];
1.599 }
1.600 @@ -1962,10 +2018,10 @@
1.601 /// is based on extensive use of priority queues and provides
1.602 /// \f$O(nm\log n)\f$ time complexity.
1.603 ///
1.604 - /// The maximum weighted matching problem is to find undirected
1.605 - /// edges in the graph with maximum overall weight and no two of
1.606 - /// them shares their ends and covers all nodes. The problem can be
1.607 - /// formulated with the following linear program.
1.608 + /// The maximum weighted perfect matching problem is to find a subset of
1.609 + /// the edges in an undirected graph with maximum overall weight for which
1.610 + /// each node has exactly one incident edge.
1.611 + /// It can be formulated with the following linear program.
1.612 /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]
1.613 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
1.614 \quad \forall B\in\mathcal{O}\f] */
1.615 @@ -1979,27 +2035,38 @@
1.616 /// The algorithm calculates an optimal matching and a proof of the
1.617 /// optimality. The solution of the dual problem can be used to check
1.618 /// the result of the algorithm. The dual linear problem is the
1.619 + /// following.
1.620 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge
1.621 w_{uv} \quad \forall uv\in E\f] */
1.622 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
1.623 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
1.624 \frac{\vert B \vert - 1}{2}z_B\f] */
1.625 ///
1.626 - /// The algorithm can be executed with \c run() or the \c init() and
1.627 - /// then the \c start() member functions. After it the matching can
1.628 - /// be asked with \c matching() or mate() functions. The dual
1.629 - /// solution can be get with \c nodeValue(), \c blossomNum() and \c
1.630 - /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
1.631 - /// "BlossomIt" nested class which is able to iterate on the nodes
1.632 - /// of a blossom. If the value type is integral then the dual
1.633 - /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
1.634 + /// The algorithm can be executed with the run() function.
1.635 + /// After it the matching (the primal solution) and the dual solution
1.636 + /// can be obtained using the query functions and the
1.637 + /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
1.638 + /// which is able to iterate on the nodes of a blossom.
1.639 + /// If the value type is integer, then the dual solution is multiplied
1.640 + /// by \ref MaxWeightedMatching::dualScale "4".
1.641 + ///
1.642 + /// \tparam GR The graph type the algorithm runs on.
1.643 + /// \tparam WM The type edge weight map. The default type is
1.644 + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
1.645 +#ifdef DOXYGEN
1.646 + template <typename GR, typename WM>
1.647 +#else
1.648 template <typename GR,
1.649 typename WM = typename GR::template EdgeMap<int> >
1.650 +#endif
1.651 class MaxWeightedPerfectMatching {
1.652 public:
1.653
1.654 + /// The graph type of the algorithm
1.655 typedef GR Graph;
1.656 + /// The type of the edge weight map
1.657 typedef WM WeightMap;
1.658 + /// The value type of the edge weights
1.659 typedef typename WeightMap::Value Value;
1.660
1.661 /// \brief Scaling factor for dual solution
1.662 @@ -2818,15 +2885,15 @@
1.663 destroyStructures();
1.664 }
1.665
1.666 - /// \name Execution control
1.667 + /// \name Execution Control
1.668 /// The simplest way to execute the algorithm is to use the
1.669 - /// \c run() member function.
1.670 + /// \ref run() member function.
1.671
1.672 ///@{
1.673
1.674 /// \brief Initialize the algorithm
1.675 ///
1.676 - /// Initialize the algorithm
1.677 + /// This function initializes the algorithm.
1.678 void init() {
1.679 createStructures();
1.680
1.681 @@ -2874,9 +2941,11 @@
1.682 }
1.683 }
1.684
1.685 - /// \brief Starts the algorithm
1.686 + /// \brief Start the algorithm
1.687 ///
1.688 - /// Starts the algorithm
1.689 + /// This function starts the algorithm.
1.690 + ///
1.691 + /// \pre \ref init() must be called before using this function.
1.692 bool start() {
1.693 enum OpType {
1.694 D2, D3, D4
1.695 @@ -2940,14 +3009,14 @@
1.696 return true;
1.697 }
1.698
1.699 - /// \brief Runs %MaxWeightedPerfectMatching algorithm.
1.700 + /// \brief Run the algorithm.
1.701 ///
1.702 - /// This method runs the %MaxWeightedPerfectMatching algorithm.
1.703 + /// This method runs the \c %MaxWeightedPerfectMatching algorithm.
1.704 ///
1.705 - /// \note mwm.run() is just a shortcut of the following code.
1.706 + /// \note mwpm.run() is just a shortcut of the following code.
1.707 /// \code
1.708 - /// mwm.init();
1.709 - /// mwm.start();
1.710 + /// mwpm.init();
1.711 + /// mwpm.start();
1.712 /// \endcode
1.713 bool run() {
1.714 init();
1.715 @@ -2956,14 +3025,19 @@
1.716
1.717 /// @}
1.718
1.719 - /// \name Primal solution
1.720 - /// Functions to get the primal solution, ie. the matching.
1.721 + /// \name Primal Solution
1.722 + /// Functions to get the primal solution, i.e. the maximum weighted
1.723 + /// perfect matching.\n
1.724 + /// Either \ref run() or \ref start() function should be called before
1.725 + /// using them.
1.726
1.727 /// @{
1.728
1.729 - /// \brief Returns the matching value.
1.730 + /// \brief Return the weight of the matching.
1.731 ///
1.732 - /// Returns the matching value.
1.733 + /// This function returns the weight of the found matching.
1.734 + ///
1.735 + /// \pre Either run() or start() must be called before using this function.
1.736 Value matchingValue() const {
1.737 Value sum = 0;
1.738 for (NodeIt n(_graph); n != INVALID; ++n) {
1.739 @@ -2974,38 +3048,53 @@
1.740 return sum /= 2;
1.741 }
1.742
1.743 - /// \brief Returns true when the edge is in the matching.
1.744 + /// \brief Return \c true if the given edge is in the matching.
1.745 ///
1.746 - /// Returns true when the edge is in the matching.
1.747 + /// This function returns \c true if the given edge is in the found
1.748 + /// matching.
1.749 + ///
1.750 + /// \pre Either run() or start() must be called before using this function.
1.751 bool matching(const Edge& edge) const {
1.752 return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge;
1.753 }
1.754
1.755 - /// \brief Returns the incident matching edge.
1.756 + /// \brief Return the matching arc (or edge) incident to the given node.
1.757 ///
1.758 - /// Returns the incident matching arc from given edge.
1.759 + /// This function returns the matching arc (or edge) incident to the
1.760 + /// given node in the found matching or \c INVALID if the node is
1.761 + /// not covered by the matching.
1.762 + ///
1.763 + /// \pre Either run() or start() must be called before using this function.
1.764 Arc matching(const Node& node) const {
1.765 return (*_matching)[node];
1.766 }
1.767
1.768 - /// \brief Returns the mate of the node.
1.769 + /// \brief Return the mate of the given node.
1.770 ///
1.771 - /// Returns the adjancent node in a mathcing arc.
1.772 + /// This function returns the mate of the given node in the found
1.773 + /// matching or \c INVALID if the node is not covered by the matching.
1.774 + ///
1.775 + /// \pre Either run() or start() must be called before using this function.
1.776 Node mate(const Node& node) const {
1.777 return _graph.target((*_matching)[node]);
1.778 }
1.779
1.780 /// @}
1.781
1.782 - /// \name Dual solution
1.783 - /// Functions to get the dual solution.
1.784 + /// \name Dual Solution
1.785 + /// Functions to get the dual solution.\n
1.786 + /// Either \ref run() or \ref start() function should be called before
1.787 + /// using them.
1.788
1.789 /// @{
1.790
1.791 - /// \brief Returns the value of the dual solution.
1.792 + /// \brief Return the value of the dual solution.
1.793 ///
1.794 - /// Returns the value of the dual solution. It should be equal to
1.795 - /// the primal value scaled by \ref dualScale "dual scale".
1.796 + /// This function returns the value of the dual solution.
1.797 + /// It should be equal to the primal value scaled by \ref dualScale
1.798 + /// "dual scale".
1.799 + ///
1.800 + /// \pre Either run() or start() must be called before using this function.
1.801 Value dualValue() const {
1.802 Value sum = 0;
1.803 for (NodeIt n(_graph); n != INVALID; ++n) {
1.804 @@ -3017,48 +3106,60 @@
1.805 return sum;
1.806 }
1.807
1.808 - /// \brief Returns the value of the node.
1.809 + /// \brief Return the dual value (potential) of the given node.
1.810 ///
1.811 - /// Returns the the value of the node.
1.812 + /// This function returns the dual value (potential) of the given node.
1.813 + ///
1.814 + /// \pre Either run() or start() must be called before using this function.
1.815 Value nodeValue(const Node& n) const {
1.816 return (*_node_potential)[n];
1.817 }
1.818
1.819 - /// \brief Returns the number of the blossoms in the basis.
1.820 + /// \brief Return the number of the blossoms in the basis.
1.821 ///
1.822 - /// Returns the number of the blossoms in the basis.
1.823 + /// This function returns the number of the blossoms in the basis.
1.824 + ///
1.825 + /// \pre Either run() or start() must be called before using this function.
1.826 /// \see BlossomIt
1.827 int blossomNum() const {
1.828 return _blossom_potential.size();
1.829 }
1.830
1.831 -
1.832 - /// \brief Returns the number of the nodes in the blossom.
1.833 + /// \brief Return the number of the nodes in the given blossom.
1.834 ///
1.835 - /// Returns the number of the nodes in the blossom.
1.836 + /// This function returns the number of the nodes in the given blossom.
1.837 + ///
1.838 + /// \pre Either run() or start() must be called before using this function.
1.839 + /// \see BlossomIt
1.840 int blossomSize(int k) const {
1.841 return _blossom_potential[k].end - _blossom_potential[k].begin;
1.842 }
1.843
1.844 - /// \brief Returns the value of the blossom.
1.845 + /// \brief Return the dual value (ptential) of the given blossom.
1.846 ///
1.847 - /// Returns the the value of the blossom.
1.848 - /// \see BlossomIt
1.849 + /// This function returns the dual value (ptential) of the given blossom.
1.850 + ///
1.851 + /// \pre Either run() or start() must be called before using this function.
1.852 Value blossomValue(int k) const {
1.853 return _blossom_potential[k].value;
1.854 }
1.855
1.856 - /// \brief Iterator for obtaining the nodes of the blossom.
1.857 + /// \brief Iterator for obtaining the nodes of a blossom.
1.858 ///
1.859 - /// Iterator for obtaining the nodes of the blossom. This class
1.860 - /// provides a common lemon style iterator for listing a
1.861 - /// subset of the nodes.
1.862 + /// This class provides an iterator for obtaining the nodes of the
1.863 + /// given blossom. It lists a subset of the nodes.
1.864 + /// Before using this iterator, you must allocate a
1.865 + /// MaxWeightedPerfectMatching class and execute it.
1.866 class BlossomIt {
1.867 public:
1.868
1.869 /// \brief Constructor.
1.870 ///
1.871 - /// Constructor to get the nodes of the variable.
1.872 + /// Constructor to get the nodes of the given variable.
1.873 + ///
1.874 + /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
1.875 + /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
1.876 + /// must be called before initializing this iterator.
1.877 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
1.878 : _algorithm(&algorithm)
1.879 {
1.880 @@ -3066,9 +3167,9 @@
1.881 _last = _algorithm->_blossom_potential[variable].end;
1.882 }
1.883
1.884 - /// \brief Conversion to node.
1.885 + /// \brief Conversion to \c Node.
1.886 ///
1.887 - /// Conversion to node.
1.888 + /// Conversion to \c Node.
1.889 operator Node() const {
1.890 return _algorithm->_blossom_node_list[_index];
1.891 }
1.892 @@ -3083,12 +3184,12 @@
1.893
1.894 /// \brief Validity checking
1.895 ///
1.896 - /// Checks whether the iterator is invalid.
1.897 + /// This function checks whether the iterator is invalid.
1.898 bool operator==(Invalid) const { return _index == _last; }
1.899
1.900 /// \brief Validity checking
1.901 ///
1.902 - /// Checks whether the iterator is valid.
1.903 + /// This function checks whether the iterator is valid.
1.904 bool operator!=(Invalid) const { return _index != _last; }
1.905
1.906 private:
1.907 @@ -3101,7 +3202,6 @@
1.908
1.909 };
1.910
1.911 -
1.912 } //END OF NAMESPACE LEMON
1.913
1.914 #endif //LEMON_MAX_MATCHING_H