r640:7ac52d6a268e
Fri, 17 Apr 2009 09:54:14
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -40,7 +40,7 @@ |
| 40 | 40 |
/// \brief Maximum cardinality matching in general graphs |
| 41 | 41 |
/// |
| 42 | 42 |
/// This class implements Edmonds' alternating forest matching algorithm |
| 43 |
/// for finding a maximum cardinality matching in a general graph. |
|
| 43 |
/// for finding a maximum cardinality matching in a general undirected graph. |
|
| 44 | 44 |
/// It can be started from an arbitrary initial matching |
| 45 | 45 |
/// (the default is the empty one). |
| 46 | 46 |
/// |
| ... | ... |
@@ -53,16 +53,17 @@ |
| 53 | 53 |
/// a perfect matching. The number of the factor-critical components |
| 54 | 54 |
/// minus the number of barrier nodes is a lower bound on the |
| 55 | 55 |
/// unmatched nodes, and the matching is optimal if and only if this bound is |
| 56 |
/// tight. This decomposition can be obtained by calling \c |
|
| 57 |
/// decomposition() after running the algorithm. |
|
| 56 |
/// tight. This decomposition can be obtained using \ref status() or |
|
| 57 |
/// \ref statusMap() after running the algorithm. |
|
| 58 | 58 |
/// |
| 59 |
/// \tparam GR The graph type the algorithm runs on. |
|
| 59 |
/// \tparam GR The undirected graph type the algorithm runs on. |
|
| 60 | 60 |
template <typename GR> |
| 61 | 61 |
class MaxMatching {
|
| 62 | 62 |
public: |
| 63 | 63 |
|
| 64 | 64 |
/// The graph type of the algorithm |
| 65 | 65 |
typedef GR Graph; |
| 66 |
/// The type of the matching map |
|
| 66 | 67 |
typedef typename Graph::template NodeMap<typename Graph::Arc> |
| 67 | 68 |
MatchingMap; |
| 68 | 69 |
|
| ... | ... |
@@ -84,6 +85,7 @@ |
| 84 | 85 |
UNMATCHED = -2 ///< = -2. |
| 85 | 86 |
}; |
| 86 | 87 |
|
| 88 |
/// The type of the status map |
|
| 87 | 89 |
typedef typename Graph::template NodeMap<Status> StatusMap; |
| 88 | 90 |
|
| 89 | 91 |
private: |
| ... | ... |
@@ -583,6 +585,14 @@ |
| 583 | 585 |
return (*_matching)[n]; |
| 584 | 586 |
} |
| 585 | 587 |
|
| 588 |
/// \brief Return a const reference to the matching map. |
|
| 589 |
/// |
|
| 590 |
/// This function returns a const reference to a node map that stores |
|
| 591 |
/// the matching arc (or edge) incident to each node. |
|
| 592 |
const MatchingMap& matchingMap() const {
|
|
| 593 |
return *_matching; |
|
| 594 |
} |
|
| 595 |
|
|
| 586 | 596 |
/// \brief Return the mate of the given node. |
| 587 | 597 |
/// |
| 588 | 598 |
/// This function returns the mate of the given node in the current |
| ... | ... |
@@ -605,10 +615,19 @@ |
| 605 | 615 |
/// |
| 606 | 616 |
/// This function returns the \ref Status "status" of the given node |
| 607 | 617 |
/// in the Edmonds-Gallai decomposition. |
| 608 |
Status |
|
| 618 |
Status status(const Node& n) const {
|
|
| 609 | 619 |
return (*_status)[n]; |
| 610 | 620 |
} |
| 611 | 621 |
|
| 622 |
/// \brief Return a const reference to the status map, which stores |
|
| 623 |
/// the Edmonds-Gallai decomposition. |
|
| 624 |
/// |
|
| 625 |
/// This function returns a const reference to a node map that stores the |
|
| 626 |
/// \ref Status "status" of each node in the Edmonds-Gallai decomposition. |
|
| 627 |
const StatusMap& statusMap() const {
|
|
| 628 |
return *_status; |
|
| 629 |
} |
|
| 630 |
|
|
| 612 | 631 |
/// \brief Return \c true if the given node is in the barrier. |
| 613 | 632 |
/// |
| 614 | 633 |
/// This function returns \c true if the given node is in the barrier. |
| ... | ... |
@@ -662,7 +681,7 @@ |
| 662 | 681 |
/// If the value type is integer, then the dual solution is multiplied |
| 663 | 682 |
/// by \ref MaxWeightedMatching::dualScale "4". |
| 664 | 683 |
/// |
| 665 |
/// \tparam GR The graph type the algorithm runs on. |
|
| 684 |
/// \tparam GR The undirected graph type the algorithm runs on. |
|
| 666 | 685 |
/// \tparam WM The type edge weight map. The default type is |
| 667 | 686 |
/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
| 668 | 687 |
#ifdef DOXYGEN |
| ... | ... |
@@ -681,6 +700,7 @@ |
| 681 | 700 |
/// The value type of the edge weights |
| 682 | 701 |
typedef typename WeightMap::Value Value; |
| 683 | 702 |
|
| 703 |
/// The type of the matching map |
|
| 684 | 704 |
typedef typename Graph::template NodeMap<typename Graph::Arc> |
| 685 | 705 |
MatchingMap; |
| 686 | 706 |
|
| ... | ... |
@@ -1829,7 +1849,7 @@ |
| 1829 | 1849 |
/// This function returns the weight of the found matching. |
| 1830 | 1850 |
/// |
| 1831 | 1851 |
/// \pre Either run() or start() must be called before using this function. |
| 1832 |
Value |
|
| 1852 |
Value matchingWeight() const {
|
|
| 1833 | 1853 |
Value sum = 0; |
| 1834 | 1854 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1835 | 1855 |
if ((*_matching)[n] != INVALID) {
|
| ... | ... |
@@ -1875,6 +1895,14 @@ |
| 1875 | 1895 |
return (*_matching)[node]; |
| 1876 | 1896 |
} |
| 1877 | 1897 |
|
| 1898 |
/// \brief Return a const reference to the matching map. |
|
| 1899 |
/// |
|
| 1900 |
/// This function returns a const reference to a node map that stores |
|
| 1901 |
/// the matching arc (or edge) incident to each node. |
|
| 1902 |
const MatchingMap& matchingMap() const {
|
|
| 1903 |
return *_matching; |
|
| 1904 |
} |
|
| 1905 |
|
|
| 1878 | 1906 |
/// \brief Return the mate of the given node. |
| 1879 | 1907 |
/// |
| 1880 | 1908 |
/// This function returns the mate of the given node in the found |
| ... | ... |
@@ -2050,7 +2078,7 @@ |
| 2050 | 2078 |
/// If the value type is integer, then the dual solution is multiplied |
| 2051 | 2079 |
/// by \ref MaxWeightedMatching::dualScale "4". |
| 2052 | 2080 |
/// |
| 2053 |
/// \tparam GR The graph type the algorithm runs on. |
|
| 2081 |
/// \tparam GR The undirected graph type the algorithm runs on. |
|
| 2054 | 2082 |
/// \tparam WM The type edge weight map. The default type is |
| 2055 | 2083 |
/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
| 2056 | 2084 |
#ifdef DOXYGEN |
| ... | ... |
@@ -2076,6 +2104,7 @@ |
| 2076 | 2104 |
static const int dualScale = |
| 2077 | 2105 |
std::numeric_limits<Value>::is_integer ? 4 : 1; |
| 2078 | 2106 |
|
| 2107 |
/// The type of the matching map |
|
| 2079 | 2108 |
typedef typename Graph::template NodeMap<typename Graph::Arc> |
| 2080 | 2109 |
MatchingMap; |
| 2081 | 2110 |
|
| ... | ... |
@@ -3038,7 +3067,7 @@ |
| 3038 | 3067 |
/// This function returns the weight of the found matching. |
| 3039 | 3068 |
/// |
| 3040 | 3069 |
/// \pre Either run() or start() must be called before using this function. |
| 3041 |
Value |
|
| 3070 |
Value matchingWeight() const {
|
|
| 3042 | 3071 |
Value sum = 0; |
| 3043 | 3072 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 3044 | 3073 |
if ((*_matching)[n] != INVALID) {
|
| ... | ... |
@@ -3069,6 +3098,14 @@ |
| 3069 | 3098 |
return (*_matching)[node]; |
| 3070 | 3099 |
} |
| 3071 | 3100 |
|
| 3101 |
/// \brief Return a const reference to the matching map. |
|
| 3102 |
/// |
|
| 3103 |
/// This function returns a const reference to a node map that stores |
|
| 3104 |
/// the matching arc (or edge) incident to each node. |
|
| 3105 |
const MatchingMap& matchingMap() const {
|
|
| 3106 |
return *_matching; |
|
| 3107 |
} |
|
| 3108 |
|
|
| 3072 | 3109 |
/// \brief Return the mate of the given node. |
| 3073 | 3110 |
/// |
| 3074 | 3111 |
/// This function returns the mate of the given node in the found |
| ... | ... |
@@ -138,13 +138,17 @@ |
| 138 | 138 |
const_mat_test.matchingSize(); |
| 139 | 139 |
const_mat_test.matching(e); |
| 140 | 140 |
const_mat_test.matching(n); |
| 141 |
const MaxMatching<Graph>::MatchingMap& mmap = |
|
| 142 |
const_mat_test.matchingMap(); |
|
| 143 |
e = mmap[n]; |
|
| 141 | 144 |
const_mat_test.mate(n); |
| 142 | 145 |
|
| 143 | 146 |
MaxMatching<Graph>::Status stat = |
| 144 |
const_mat_test. |
|
| 147 |
const_mat_test.status(n); |
|
| 148 |
const MaxMatching<Graph>::StatusMap& smap = |
|
| 149 |
const_mat_test.statusMap(); |
|
| 150 |
stat = smap[n]; |
|
| 145 | 151 |
const_mat_test.barrier(n); |
| 146 |
|
|
| 147 |
ignore_unused_variable_warning(stat); |
|
| 148 | 152 |
} |
| 149 | 153 |
|
| 150 | 154 |
void checkMaxWeightedMatchingCompile() |
| ... | ... |
@@ -167,10 +171,13 @@ |
| 167 | 171 |
mat_test.start(); |
| 168 | 172 |
mat_test.run(); |
| 169 | 173 |
|
| 170 |
const_mat_test. |
|
| 174 |
const_mat_test.matchingWeight(); |
|
| 171 | 175 |
const_mat_test.matchingSize(); |
| 172 | 176 |
const_mat_test.matching(e); |
| 173 | 177 |
const_mat_test.matching(n); |
| 178 |
const MaxWeightedMatching<Graph>::MatchingMap& mmap = |
|
| 179 |
const_mat_test.matchingMap(); |
|
| 180 |
e = mmap[n]; |
|
| 174 | 181 |
const_mat_test.mate(n); |
| 175 | 182 |
|
| 176 | 183 |
int k = 0; |
| ... | ... |
@@ -201,9 +208,12 @@ |
| 201 | 208 |
mat_test.start(); |
| 202 | 209 |
mat_test.run(); |
| 203 | 210 |
|
| 204 |
const_mat_test. |
|
| 211 |
const_mat_test.matchingWeight(); |
|
| 205 | 212 |
const_mat_test.matching(e); |
| 206 | 213 |
const_mat_test.matching(n); |
| 214 |
const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap = |
|
| 215 |
const_mat_test.matchingMap(); |
|
| 216 |
e = mmap[n]; |
|
| 207 | 217 |
const_mat_test.mate(n); |
| 208 | 218 |
|
| 209 | 219 |
int k = 0; |
| ... | ... |
@@ -224,9 +234,9 @@ |
| 224 | 234 |
int barrier_num = 0; |
| 225 | 235 |
|
| 226 | 236 |
for (NodeIt n(graph); n != INVALID; ++n) {
|
| 227 |
check(mm. |
|
| 237 |
check(mm.status(n) == MaxMatching<SmartGraph>::EVEN || |
|
| 228 | 238 |
mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); |
| 229 |
if (mm. |
|
| 239 |
if (mm.status(n) == MaxMatching<SmartGraph>::ODD) {
|
|
| 230 | 240 |
++barrier_num; |
| 231 | 241 |
} else {
|
| 232 | 242 |
comp.insert(n); |
| ... | ... |
@@ -239,16 +249,16 @@ |
| 239 | 249 |
check(e == mm.matching(graph.v(e)), "Wrong matching"); |
| 240 | 250 |
++num; |
| 241 | 251 |
} |
| 242 |
check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN || |
|
| 243 |
mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
| 252 |
check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN || |
|
| 253 |
mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
| 244 | 254 |
"Wrong Gallai-Edmonds decomposition"); |
| 245 | 255 |
|
| 246 |
check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN || |
|
| 247 |
mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
| 256 |
check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN || |
|
| 257 |
mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
| 248 | 258 |
"Wrong Gallai-Edmonds decomposition"); |
| 249 | 259 |
|
| 250 |
if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD && |
|
| 251 |
mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
|
|
| 260 |
if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD && |
|
| 261 |
mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
|
|
| 252 | 262 |
comp.join(graph.u(e), graph.v(e)); |
| 253 | 263 |
} |
| 254 | 264 |
} |
| ... | ... |
@@ -256,7 +266,7 @@ |
| 256 | 266 |
std::set<int> comp_root; |
| 257 | 267 |
int odd_comp_num = 0; |
| 258 | 268 |
for (NodeIt n(graph); n != INVALID; ++n) {
|
| 259 |
if (mm. |
|
| 269 |
if (mm.status(n) != MaxMatching<SmartGraph>::ODD) {
|
|
| 260 | 270 |
int root = comp.find(n); |
| 261 | 271 |
if (comp_root.find(root) == comp_root.end()) {
|
| 262 | 272 |
comp_root.insert(root); |
0 comments (0 inline)