136 mat_test.run(); |
136 mat_test.run(); |
137 |
137 |
138 const_mat_test.matchingSize(); |
138 const_mat_test.matchingSize(); |
139 const_mat_test.matching(e); |
139 const_mat_test.matching(e); |
140 const_mat_test.matching(n); |
140 const_mat_test.matching(n); |
|
141 const MaxMatching<Graph>::MatchingMap& mmap = |
|
142 const_mat_test.matchingMap(); |
|
143 e = mmap[n]; |
141 const_mat_test.mate(n); |
144 const_mat_test.mate(n); |
142 |
145 |
143 MaxMatching<Graph>::Status stat = |
146 MaxMatching<Graph>::Status stat = |
144 const_mat_test.decomposition(n); |
147 const_mat_test.status(n); |
|
148 const MaxMatching<Graph>::StatusMap& smap = |
|
149 const_mat_test.statusMap(); |
|
150 stat = smap[n]; |
145 const_mat_test.barrier(n); |
151 const_mat_test.barrier(n); |
146 |
|
147 ignore_unused_variable_warning(stat); |
|
148 } |
152 } |
149 |
153 |
150 void checkMaxWeightedMatchingCompile() |
154 void checkMaxWeightedMatchingCompile() |
151 { |
155 { |
152 typedef concepts::Graph Graph; |
156 typedef concepts::Graph Graph; |
165 |
169 |
166 mat_test.init(); |
170 mat_test.init(); |
167 mat_test.start(); |
171 mat_test.start(); |
168 mat_test.run(); |
172 mat_test.run(); |
169 |
173 |
170 const_mat_test.matchingValue(); |
174 const_mat_test.matchingWeight(); |
171 const_mat_test.matchingSize(); |
175 const_mat_test.matchingSize(); |
172 const_mat_test.matching(e); |
176 const_mat_test.matching(e); |
173 const_mat_test.matching(n); |
177 const_mat_test.matching(n); |
|
178 const MaxWeightedMatching<Graph>::MatchingMap& mmap = |
|
179 const_mat_test.matchingMap(); |
|
180 e = mmap[n]; |
174 const_mat_test.mate(n); |
181 const_mat_test.mate(n); |
175 |
182 |
176 int k = 0; |
183 int k = 0; |
177 const_mat_test.dualValue(); |
184 const_mat_test.dualValue(); |
178 const_mat_test.nodeValue(n); |
185 const_mat_test.nodeValue(n); |
199 |
206 |
200 mat_test.init(); |
207 mat_test.init(); |
201 mat_test.start(); |
208 mat_test.start(); |
202 mat_test.run(); |
209 mat_test.run(); |
203 |
210 |
204 const_mat_test.matchingValue(); |
211 const_mat_test.matchingWeight(); |
205 const_mat_test.matching(e); |
212 const_mat_test.matching(e); |
206 const_mat_test.matching(n); |
213 const_mat_test.matching(n); |
|
214 const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap = |
|
215 const_mat_test.matchingMap(); |
|
216 e = mmap[n]; |
207 const_mat_test.mate(n); |
217 const_mat_test.mate(n); |
208 |
218 |
209 int k = 0; |
219 int k = 0; |
210 const_mat_test.dualValue(); |
220 const_mat_test.dualValue(); |
211 const_mat_test.nodeValue(n); |
221 const_mat_test.nodeValue(n); |
222 UnionFind<IntNodeMap> comp(comp_index); |
232 UnionFind<IntNodeMap> comp(comp_index); |
223 |
233 |
224 int barrier_num = 0; |
234 int barrier_num = 0; |
225 |
235 |
226 for (NodeIt n(graph); n != INVALID; ++n) { |
236 for (NodeIt n(graph); n != INVALID; ++n) { |
227 check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN || |
237 check(mm.status(n) == MaxMatching<SmartGraph>::EVEN || |
228 mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); |
238 mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); |
229 if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) { |
239 if (mm.status(n) == MaxMatching<SmartGraph>::ODD) { |
230 ++barrier_num; |
240 ++barrier_num; |
231 } else { |
241 } else { |
232 comp.insert(n); |
242 comp.insert(n); |
233 } |
243 } |
234 } |
244 } |
237 if (mm.matching(e)) { |
247 if (mm.matching(e)) { |
238 check(e == mm.matching(graph.u(e)), "Wrong matching"); |
248 check(e == mm.matching(graph.u(e)), "Wrong matching"); |
239 check(e == mm.matching(graph.v(e)), "Wrong matching"); |
249 check(e == mm.matching(graph.v(e)), "Wrong matching"); |
240 ++num; |
250 ++num; |
241 } |
251 } |
242 check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN || |
252 check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN || |
243 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, |
253 mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, |
244 "Wrong Gallai-Edmonds decomposition"); |
254 "Wrong Gallai-Edmonds decomposition"); |
245 |
255 |
246 check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN || |
256 check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN || |
247 mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, |
257 mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, |
248 "Wrong Gallai-Edmonds decomposition"); |
258 "Wrong Gallai-Edmonds decomposition"); |
249 |
259 |
250 if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD && |
260 if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD && |
251 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) { |
261 mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) { |
252 comp.join(graph.u(e), graph.v(e)); |
262 comp.join(graph.u(e), graph.v(e)); |
253 } |
263 } |
254 } |
264 } |
255 |
265 |
256 std::set<int> comp_root; |
266 std::set<int> comp_root; |
257 int odd_comp_num = 0; |
267 int odd_comp_num = 0; |
258 for (NodeIt n(graph); n != INVALID; ++n) { |
268 for (NodeIt n(graph); n != INVALID; ++n) { |
259 if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) { |
269 if (mm.status(n) != MaxMatching<SmartGraph>::ODD) { |
260 int root = comp.find(n); |
270 int root = comp.find(n); |
261 if (comp_root.find(root) == comp_root.end()) { |
271 if (comp_root.find(root) == comp_root.end()) { |
262 comp_root.insert(root); |
272 comp_root.insert(root); |
263 if (comp.size(n) % 2 == 1) { |
273 if (comp.size(n) % 2 == 1) { |
264 ++odd_comp_num; |
274 ++odd_comp_num; |