1.1 --- a/lemon/matching.h Fri Aug 05 09:33:42 2011 +0200
1.2 +++ b/lemon/matching.h Mon Aug 08 12:36:16 2011 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2011
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -41,7 +41,7 @@
1.13 ///
1.14 /// This class implements Edmonds' alternating forest matching algorithm
1.15 /// for finding a maximum cardinality matching in a general undirected graph.
1.16 - /// It can be started from an arbitrary initial matching
1.17 + /// It can be started from an arbitrary initial matching
1.18 /// (the default is the empty one).
1.19 ///
1.20 /// The dual solution of the problem is a map of the nodes to
1.21 @@ -69,11 +69,11 @@
1.22
1.23 ///\brief Status constants for Gallai-Edmonds decomposition.
1.24 ///
1.25 - ///These constants are used for indicating the Gallai-Edmonds
1.26 + ///These constants are used for indicating the Gallai-Edmonds
1.27 ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
1.28 ///induce a subgraph with factor-critical components, the nodes with
1.29 ///status \c ODD (or \c A) form the canonical barrier, and the nodes
1.30 - ///with status \c MATCHED (or \c C) induce a subgraph having a
1.31 + ///with status \c MATCHED (or \c C) induce a subgraph having a
1.32 ///perfect matching.
1.33 enum Status {
1.34 EVEN = 1, ///< = 1. (\c D is an alias for \c EVEN.)
1.35 @@ -512,7 +512,7 @@
1.36 }
1.37 }
1.38
1.39 - /// \brief Start Edmonds' algorithm with a heuristic improvement
1.40 + /// \brief Start Edmonds' algorithm with a heuristic improvement
1.41 /// for dense graphs
1.42 ///
1.43 /// This function runs Edmonds' algorithm with a heuristic of postponing
1.44 @@ -534,8 +534,8 @@
1.45
1.46 /// \brief Run Edmonds' algorithm
1.47 ///
1.48 - /// This function runs Edmonds' algorithm. An additional heuristic of
1.49 - /// postponing shrinks is used for relatively dense graphs
1.50 + /// This function runs Edmonds' algorithm. An additional heuristic of
1.51 + /// postponing shrinks is used for relatively dense graphs
1.52 /// (for which <tt>m>=2*n</tt> holds).
1.53 void run() {
1.54 if (countEdges(_graph) < 2 * countNodes(_graph)) {
1.55 @@ -556,7 +556,7 @@
1.56
1.57 /// \brief Return the size (cardinality) of the matching.
1.58 ///
1.59 - /// This function returns the size (cardinality) of the current matching.
1.60 + /// This function returns the size (cardinality) of the current matching.
1.61 /// After run() it returns the size of the maximum matching in the graph.
1.62 int matchingSize() const {
1.63 int size = 0;
1.64 @@ -570,7 +570,7 @@
1.65
1.66 /// \brief Return \c true if the given edge is in the matching.
1.67 ///
1.68 - /// This function returns \c true if the given edge is in the current
1.69 + /// This function returns \c true if the given edge is in the current
1.70 /// matching.
1.71 bool matching(const Edge& edge) const {
1.72 return edge == (*_matching)[_graph.u(edge)];
1.73 @@ -579,7 +579,7 @@
1.74 /// \brief Return the matching arc (or edge) incident to the given node.
1.75 ///
1.76 /// This function returns the matching arc (or edge) incident to the
1.77 - /// given node in the current matching or \c INVALID if the node is
1.78 + /// given node in the current matching or \c INVALID if the node is
1.79 /// not covered by the matching.
1.80 Arc matching(const Node& n) const {
1.81 return (*_matching)[n];
1.82 @@ -595,7 +595,7 @@
1.83
1.84 /// \brief Return the mate of the given node.
1.85 ///
1.86 - /// This function returns the mate of the given node in the current
1.87 + /// This function returns the mate of the given node in the current
1.88 /// matching or \c INVALID if the node is not covered by the matching.
1.89 Node mate(const Node& n) const {
1.90 return (*_matching)[n] != INVALID ?
1.91 @@ -605,7 +605,7 @@
1.92 /// @}
1.93
1.94 /// \name Dual Solution
1.95 - /// Functions to get the dual solution, i.e. the Gallai-Edmonds
1.96 + /// Functions to get the dual solution, i.e. the Gallai-Edmonds
1.97 /// decomposition.
1.98
1.99 /// @{
1.100 @@ -648,8 +648,8 @@
1.101 /// on extensive use of priority queues and provides
1.102 /// \f$O(nm\log n)\f$ time complexity.
1.103 ///
1.104 - /// The maximum weighted matching problem is to find a subset of the
1.105 - /// edges in an undirected graph with maximum overall weight for which
1.106 + /// The maximum weighted matching problem is to find a subset of the
1.107 + /// edges in an undirected graph with maximum overall weight for which
1.108 /// each node has at most one incident edge.
1.109 /// It can be formulated with the following linear program.
1.110 /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
1.111 @@ -673,16 +673,16 @@
1.112 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
1.113 \frac{\vert B \vert - 1}{2}z_B\f] */
1.114 ///
1.115 - /// The algorithm can be executed with the run() function.
1.116 + /// The algorithm can be executed with the run() function.
1.117 /// After it the matching (the primal solution) and the dual solution
1.118 - /// can be obtained using the query functions and the
1.119 - /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
1.120 - /// which is able to iterate on the nodes of a blossom.
1.121 + /// can be obtained using the query functions and the
1.122 + /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
1.123 + /// which is able to iterate on the nodes of a blossom.
1.124 /// If the value type is integer, then the dual solution is multiplied
1.125 /// by \ref MaxWeightedMatching::dualScale "4".
1.126 ///
1.127 /// \tparam GR The undirected graph type the algorithm runs on.
1.128 - /// \tparam WM The type edge weight map. The default type is
1.129 + /// \tparam WM The type edge weight map. The default type is
1.130 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
1.131 #ifdef DOXYGEN
1.132 template <typename GR, typename WM>
1.133 @@ -1720,7 +1720,7 @@
1.134 (*_delta2_index)[i] = _delta2->PRE_HEAP;
1.135 (*_delta4_index)[i] = _delta4->PRE_HEAP;
1.136 }
1.137 -
1.138 +
1.139 _delta1->clear();
1.140 _delta2->clear();
1.141 _delta3->clear();
1.142 @@ -1868,7 +1868,7 @@
1.143 /// @}
1.144
1.145 /// \name Primal Solution
1.146 - /// Functions to get the primal solution, i.e. the maximum weighted
1.147 + /// Functions to get the primal solution, i.e. the maximum weighted
1.148 /// matching.\n
1.149 /// Either \ref run() or \ref start() function should be called before
1.150 /// using them.
1.151 @@ -1907,7 +1907,7 @@
1.152
1.153 /// \brief Return \c true if the given edge is in the matching.
1.154 ///
1.155 - /// This function returns \c true if the given edge is in the found
1.156 + /// This function returns \c true if the given edge is in the found
1.157 /// matching.
1.158 ///
1.159 /// \pre Either run() or start() must be called before using this function.
1.160 @@ -1918,7 +1918,7 @@
1.161 /// \brief Return the matching arc (or edge) incident to the given node.
1.162 ///
1.163 /// This function returns the matching arc (or edge) incident to the
1.164 - /// given node in the found matching or \c INVALID if the node is
1.165 + /// given node in the found matching or \c INVALID if the node is
1.166 /// not covered by the matching.
1.167 ///
1.168 /// \pre Either run() or start() must be called before using this function.
1.169 @@ -1936,7 +1936,7 @@
1.170
1.171 /// \brief Return the mate of the given node.
1.172 ///
1.173 - /// This function returns the mate of the given node in the found
1.174 + /// This function returns the mate of the given node in the found
1.175 /// matching or \c INVALID if the node is not covered by the matching.
1.176 ///
1.177 /// \pre Either run() or start() must be called before using this function.
1.178 @@ -1956,8 +1956,8 @@
1.179
1.180 /// \brief Return the value of the dual solution.
1.181 ///
1.182 - /// This function returns the value of the dual solution.
1.183 - /// It should be equal to the primal value scaled by \ref dualScale
1.184 + /// This function returns the value of the dual solution.
1.185 + /// It should be equal to the primal value scaled by \ref dualScale
1.186 /// "dual scale".
1.187 ///
1.188 /// \pre Either run() or start() must be called before using this function.
1.189 @@ -2012,9 +2012,9 @@
1.190
1.191 /// \brief Iterator for obtaining the nodes of a blossom.
1.192 ///
1.193 - /// This class provides an iterator for obtaining the nodes of the
1.194 + /// This class provides an iterator for obtaining the nodes of the
1.195 /// given blossom. It lists a subset of the nodes.
1.196 - /// Before using this iterator, you must allocate a
1.197 + /// Before using this iterator, you must allocate a
1.198 /// MaxWeightedMatching class and execute it.
1.199 class BlossomIt {
1.200 public:
1.201 @@ -2023,8 +2023,8 @@
1.202 ///
1.203 /// Constructor to get the nodes of the given variable.
1.204 ///
1.205 - /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
1.206 - /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
1.207 + /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
1.208 + /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
1.209 /// called before initializing this iterator.
1.210 BlossomIt(const MaxWeightedMatching& algorithm, int variable)
1.211 : _algorithm(&algorithm)
1.212 @@ -2077,8 +2077,8 @@
1.213 /// is based on extensive use of priority queues and provides
1.214 /// \f$O(nm\log n)\f$ time complexity.
1.215 ///
1.216 - /// The maximum weighted perfect matching problem is to find a subset of
1.217 - /// the edges in an undirected graph with maximum overall weight for which
1.218 + /// The maximum weighted perfect matching problem is to find a subset of
1.219 + /// the edges in an undirected graph with maximum overall weight for which
1.220 /// each node has exactly one incident edge.
1.221 /// It can be formulated with the following linear program.
1.222 /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]
1.223 @@ -2101,16 +2101,16 @@
1.224 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
1.225 \frac{\vert B \vert - 1}{2}z_B\f] */
1.226 ///
1.227 - /// The algorithm can be executed with the run() function.
1.228 + /// The algorithm can be executed with the run() function.
1.229 /// After it the matching (the primal solution) and the dual solution
1.230 - /// can be obtained using the query functions and the
1.231 - /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
1.232 - /// which is able to iterate on the nodes of a blossom.
1.233 + /// can be obtained using the query functions and the
1.234 + /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
1.235 + /// which is able to iterate on the nodes of a blossom.
1.236 /// If the value type is integer, then the dual solution is multiplied
1.237 /// by \ref MaxWeightedMatching::dualScale "4".
1.238 ///
1.239 /// \tparam GR The undirected graph type the algorithm runs on.
1.240 - /// \tparam WM The type edge weight map. The default type is
1.241 + /// \tparam WM The type edge weight map. The default type is
1.242 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
1.243 #ifdef DOXYGEN
1.244 template <typename GR, typename WM>
1.245 @@ -3115,7 +3115,7 @@
1.246 /// @}
1.247
1.248 /// \name Primal Solution
1.249 - /// Functions to get the primal solution, i.e. the maximum weighted
1.250 + /// Functions to get the primal solution, i.e. the maximum weighted
1.251 /// perfect matching.\n
1.252 /// Either \ref run() or \ref start() function should be called before
1.253 /// using them.
1.254 @@ -3139,7 +3139,7 @@
1.255
1.256 /// \brief Return \c true if the given edge is in the matching.
1.257 ///
1.258 - /// This function returns \c true if the given edge is in the found
1.259 + /// This function returns \c true if the given edge is in the found
1.260 /// matching.
1.261 ///
1.262 /// \pre Either run() or start() must be called before using this function.
1.263 @@ -3150,7 +3150,7 @@
1.264 /// \brief Return the matching arc (or edge) incident to the given node.
1.265 ///
1.266 /// This function returns the matching arc (or edge) incident to the
1.267 - /// given node in the found matching or \c INVALID if the node is
1.268 + /// given node in the found matching or \c INVALID if the node is
1.269 /// not covered by the matching.
1.270 ///
1.271 /// \pre Either run() or start() must be called before using this function.
1.272 @@ -3168,7 +3168,7 @@
1.273
1.274 /// \brief Return the mate of the given node.
1.275 ///
1.276 - /// This function returns the mate of the given node in the found
1.277 + /// This function returns the mate of the given node in the found
1.278 /// matching or \c INVALID if the node is not covered by the matching.
1.279 ///
1.280 /// \pre Either run() or start() must be called before using this function.
1.281 @@ -3187,8 +3187,8 @@
1.282
1.283 /// \brief Return the value of the dual solution.
1.284 ///
1.285 - /// This function returns the value of the dual solution.
1.286 - /// It should be equal to the primal value scaled by \ref dualScale
1.287 + /// This function returns the value of the dual solution.
1.288 + /// It should be equal to the primal value scaled by \ref dualScale
1.289 /// "dual scale".
1.290 ///
1.291 /// \pre Either run() or start() must be called before using this function.
1.292 @@ -3243,9 +3243,9 @@
1.293
1.294 /// \brief Iterator for obtaining the nodes of a blossom.
1.295 ///
1.296 - /// This class provides an iterator for obtaining the nodes of the
1.297 + /// This class provides an iterator for obtaining the nodes of the
1.298 /// given blossom. It lists a subset of the nodes.
1.299 - /// Before using this iterator, you must allocate a
1.300 + /// Before using this iterator, you must allocate a
1.301 /// MaxWeightedPerfectMatching class and execute it.
1.302 class BlossomIt {
1.303 public:
1.304 @@ -3254,8 +3254,8 @@
1.305 ///
1.306 /// Constructor to get the nodes of the given variable.
1.307 ///
1.308 - /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
1.309 - /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
1.310 + /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
1.311 + /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
1.312 /// must be called before initializing this iterator.
1.313 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
1.314 : _algorithm(&algorithm)