1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2009 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <iostream> |
|
20 #include <sstream> |
|
21 #include <vector> |
|
22 #include <queue> |
|
23 #include <cstdlib> |
|
24 |
|
25 #include <lemon/max_matching.h> |
|
26 #include <lemon/smart_graph.h> |
|
27 #include <lemon/concepts/graph.h> |
|
28 #include <lemon/concepts/maps.h> |
|
29 #include <lemon/lgf_reader.h> |
|
30 #include <lemon/math.h> |
|
31 |
|
32 #include "test_tools.h" |
|
33 |
|
34 using namespace std; |
|
35 using namespace lemon; |
|
36 |
|
37 GRAPH_TYPEDEFS(SmartGraph); |
|
38 |
|
39 |
|
40 const int lgfn = 3; |
|
41 const std::string lgf[lgfn] = { |
|
42 "@nodes\n" |
|
43 "label\n" |
|
44 "0\n" |
|
45 "1\n" |
|
46 "2\n" |
|
47 "3\n" |
|
48 "4\n" |
|
49 "5\n" |
|
50 "6\n" |
|
51 "7\n" |
|
52 "@edges\n" |
|
53 " label weight\n" |
|
54 "7 4 0 984\n" |
|
55 "0 7 1 73\n" |
|
56 "7 1 2 204\n" |
|
57 "2 3 3 583\n" |
|
58 "2 7 4 565\n" |
|
59 "2 1 5 582\n" |
|
60 "0 4 6 551\n" |
|
61 "2 5 7 385\n" |
|
62 "1 5 8 561\n" |
|
63 "5 3 9 484\n" |
|
64 "7 5 10 904\n" |
|
65 "3 6 11 47\n" |
|
66 "7 6 12 888\n" |
|
67 "3 0 13 747\n" |
|
68 "6 1 14 310\n", |
|
69 |
|
70 "@nodes\n" |
|
71 "label\n" |
|
72 "0\n" |
|
73 "1\n" |
|
74 "2\n" |
|
75 "3\n" |
|
76 "4\n" |
|
77 "5\n" |
|
78 "6\n" |
|
79 "7\n" |
|
80 "@edges\n" |
|
81 " label weight\n" |
|
82 "2 5 0 710\n" |
|
83 "0 5 1 241\n" |
|
84 "2 4 2 856\n" |
|
85 "2 6 3 762\n" |
|
86 "4 1 4 747\n" |
|
87 "6 1 5 962\n" |
|
88 "4 7 6 723\n" |
|
89 "1 7 7 661\n" |
|
90 "2 3 8 376\n" |
|
91 "1 0 9 416\n" |
|
92 "6 7 10 391\n", |
|
93 |
|
94 "@nodes\n" |
|
95 "label\n" |
|
96 "0\n" |
|
97 "1\n" |
|
98 "2\n" |
|
99 "3\n" |
|
100 "4\n" |
|
101 "5\n" |
|
102 "6\n" |
|
103 "7\n" |
|
104 "@edges\n" |
|
105 " label weight\n" |
|
106 "6 2 0 553\n" |
|
107 "0 7 1 653\n" |
|
108 "6 3 2 22\n" |
|
109 "4 7 3 846\n" |
|
110 "7 2 4 981\n" |
|
111 "7 6 5 250\n" |
|
112 "5 2 6 539\n", |
|
113 }; |
|
114 |
|
115 void checkMaxMatchingCompile() |
|
116 { |
|
117 typedef concepts::Graph Graph; |
|
118 typedef Graph::Node Node; |
|
119 typedef Graph::Edge Edge; |
|
120 typedef Graph::EdgeMap<bool> MatMap; |
|
121 |
|
122 Graph g; |
|
123 Node n; |
|
124 Edge e; |
|
125 MatMap mat(g); |
|
126 |
|
127 MaxMatching<Graph> mat_test(g); |
|
128 const MaxMatching<Graph>& |
|
129 const_mat_test = mat_test; |
|
130 |
|
131 mat_test.init(); |
|
132 mat_test.greedyInit(); |
|
133 mat_test.matchingInit(mat); |
|
134 mat_test.startSparse(); |
|
135 mat_test.startDense(); |
|
136 mat_test.run(); |
|
137 |
|
138 const_mat_test.matchingSize(); |
|
139 const_mat_test.matching(e); |
|
140 const_mat_test.matching(n); |
|
141 const MaxMatching<Graph>::MatchingMap& mmap = |
|
142 const_mat_test.matchingMap(); |
|
143 e = mmap[n]; |
|
144 const_mat_test.mate(n); |
|
145 |
|
146 MaxMatching<Graph>::Status stat = |
|
147 const_mat_test.status(n); |
|
148 const MaxMatching<Graph>::StatusMap& smap = |
|
149 const_mat_test.statusMap(); |
|
150 stat = smap[n]; |
|
151 const_mat_test.barrier(n); |
|
152 } |
|
153 |
|
154 void checkMaxWeightedMatchingCompile() |
|
155 { |
|
156 typedef concepts::Graph Graph; |
|
157 typedef Graph::Node Node; |
|
158 typedef Graph::Edge Edge; |
|
159 typedef Graph::EdgeMap<int> WeightMap; |
|
160 |
|
161 Graph g; |
|
162 Node n; |
|
163 Edge e; |
|
164 WeightMap w(g); |
|
165 |
|
166 MaxWeightedMatching<Graph> mat_test(g, w); |
|
167 const MaxWeightedMatching<Graph>& |
|
168 const_mat_test = mat_test; |
|
169 |
|
170 mat_test.init(); |
|
171 mat_test.start(); |
|
172 mat_test.run(); |
|
173 |
|
174 const_mat_test.matchingWeight(); |
|
175 const_mat_test.matchingSize(); |
|
176 const_mat_test.matching(e); |
|
177 const_mat_test.matching(n); |
|
178 const MaxWeightedMatching<Graph>::MatchingMap& mmap = |
|
179 const_mat_test.matchingMap(); |
|
180 e = mmap[n]; |
|
181 const_mat_test.mate(n); |
|
182 |
|
183 int k = 0; |
|
184 const_mat_test.dualValue(); |
|
185 const_mat_test.nodeValue(n); |
|
186 const_mat_test.blossomNum(); |
|
187 const_mat_test.blossomSize(k); |
|
188 const_mat_test.blossomValue(k); |
|
189 } |
|
190 |
|
191 void checkMaxWeightedPerfectMatchingCompile() |
|
192 { |
|
193 typedef concepts::Graph Graph; |
|
194 typedef Graph::Node Node; |
|
195 typedef Graph::Edge Edge; |
|
196 typedef Graph::EdgeMap<int> WeightMap; |
|
197 |
|
198 Graph g; |
|
199 Node n; |
|
200 Edge e; |
|
201 WeightMap w(g); |
|
202 |
|
203 MaxWeightedPerfectMatching<Graph> mat_test(g, w); |
|
204 const MaxWeightedPerfectMatching<Graph>& |
|
205 const_mat_test = mat_test; |
|
206 |
|
207 mat_test.init(); |
|
208 mat_test.start(); |
|
209 mat_test.run(); |
|
210 |
|
211 const_mat_test.matchingWeight(); |
|
212 const_mat_test.matching(e); |
|
213 const_mat_test.matching(n); |
|
214 const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap = |
|
215 const_mat_test.matchingMap(); |
|
216 e = mmap[n]; |
|
217 const_mat_test.mate(n); |
|
218 |
|
219 int k = 0; |
|
220 const_mat_test.dualValue(); |
|
221 const_mat_test.nodeValue(n); |
|
222 const_mat_test.blossomNum(); |
|
223 const_mat_test.blossomSize(k); |
|
224 const_mat_test.blossomValue(k); |
|
225 } |
|
226 |
|
227 void checkMatching(const SmartGraph& graph, |
|
228 const MaxMatching<SmartGraph>& mm) { |
|
229 int num = 0; |
|
230 |
|
231 IntNodeMap comp_index(graph); |
|
232 UnionFind<IntNodeMap> comp(comp_index); |
|
233 |
|
234 int barrier_num = 0; |
|
235 |
|
236 for (NodeIt n(graph); n != INVALID; ++n) { |
|
237 check(mm.status(n) == MaxMatching<SmartGraph>::EVEN || |
|
238 mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); |
|
239 if (mm.status(n) == MaxMatching<SmartGraph>::ODD) { |
|
240 ++barrier_num; |
|
241 } else { |
|
242 comp.insert(n); |
|
243 } |
|
244 } |
|
245 |
|
246 for (EdgeIt e(graph); e != INVALID; ++e) { |
|
247 if (mm.matching(e)) { |
|
248 check(e == mm.matching(graph.u(e)), "Wrong matching"); |
|
249 check(e == mm.matching(graph.v(e)), "Wrong matching"); |
|
250 ++num; |
|
251 } |
|
252 check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN || |
|
253 mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
254 "Wrong Gallai-Edmonds decomposition"); |
|
255 |
|
256 check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN || |
|
257 mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, |
|
258 "Wrong Gallai-Edmonds decomposition"); |
|
259 |
|
260 if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD && |
|
261 mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) { |
|
262 comp.join(graph.u(e), graph.v(e)); |
|
263 } |
|
264 } |
|
265 |
|
266 std::set<int> comp_root; |
|
267 int odd_comp_num = 0; |
|
268 for (NodeIt n(graph); n != INVALID; ++n) { |
|
269 if (mm.status(n) != MaxMatching<SmartGraph>::ODD) { |
|
270 int root = comp.find(n); |
|
271 if (comp_root.find(root) == comp_root.end()) { |
|
272 comp_root.insert(root); |
|
273 if (comp.size(n) % 2 == 1) { |
|
274 ++odd_comp_num; |
|
275 } |
|
276 } |
|
277 } |
|
278 } |
|
279 |
|
280 check(mm.matchingSize() == num, "Wrong matching"); |
|
281 check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num), |
|
282 "Wrong matching"); |
|
283 return; |
|
284 } |
|
285 |
|
286 void checkWeightedMatching(const SmartGraph& graph, |
|
287 const SmartGraph::EdgeMap<int>& weight, |
|
288 const MaxWeightedMatching<SmartGraph>& mwm) { |
|
289 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
|
290 if (graph.u(e) == graph.v(e)) continue; |
|
291 int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e)); |
|
292 |
|
293 for (int i = 0; i < mwm.blossomNum(); ++i) { |
|
294 bool s = false, t = false; |
|
295 for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i); |
|
296 n != INVALID; ++n) { |
|
297 if (graph.u(e) == n) s = true; |
|
298 if (graph.v(e) == n) t = true; |
|
299 } |
|
300 if (s == true && t == true) { |
|
301 rw += mwm.blossomValue(i); |
|
302 } |
|
303 } |
|
304 rw -= weight[e] * mwm.dualScale; |
|
305 |
|
306 check(rw >= 0, "Negative reduced weight"); |
|
307 check(rw == 0 || !mwm.matching(e), |
|
308 "Non-zero reduced weight on matching edge"); |
|
309 } |
|
310 |
|
311 int pv = 0; |
|
312 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
313 if (mwm.matching(n) != INVALID) { |
|
314 check(mwm.nodeValue(n) >= 0, "Invalid node value"); |
|
315 pv += weight[mwm.matching(n)]; |
|
316 SmartGraph::Node o = graph.target(mwm.matching(n)); |
|
317 check(mwm.mate(n) == o, "Invalid matching"); |
|
318 check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)), |
|
319 "Invalid matching"); |
|
320 } else { |
|
321 check(mwm.mate(n) == INVALID, "Invalid matching"); |
|
322 check(mwm.nodeValue(n) == 0, "Invalid matching"); |
|
323 } |
|
324 } |
|
325 |
|
326 int dv = 0; |
|
327 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
328 dv += mwm.nodeValue(n); |
|
329 } |
|
330 |
|
331 for (int i = 0; i < mwm.blossomNum(); ++i) { |
|
332 check(mwm.blossomValue(i) >= 0, "Invalid blossom value"); |
|
333 check(mwm.blossomSize(i) % 2 == 1, "Even blossom size"); |
|
334 dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2); |
|
335 } |
|
336 |
|
337 check(pv * mwm.dualScale == dv * 2, "Wrong duality"); |
|
338 |
|
339 return; |
|
340 } |
|
341 |
|
342 void checkWeightedPerfectMatching(const SmartGraph& graph, |
|
343 const SmartGraph::EdgeMap<int>& weight, |
|
344 const MaxWeightedPerfectMatching<SmartGraph>& mwpm) { |
|
345 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
|
346 if (graph.u(e) == graph.v(e)) continue; |
|
347 int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e)); |
|
348 |
|
349 for (int i = 0; i < mwpm.blossomNum(); ++i) { |
|
350 bool s = false, t = false; |
|
351 for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i); |
|
352 n != INVALID; ++n) { |
|
353 if (graph.u(e) == n) s = true; |
|
354 if (graph.v(e) == n) t = true; |
|
355 } |
|
356 if (s == true && t == true) { |
|
357 rw += mwpm.blossomValue(i); |
|
358 } |
|
359 } |
|
360 rw -= weight[e] * mwpm.dualScale; |
|
361 |
|
362 check(rw >= 0, "Negative reduced weight"); |
|
363 check(rw == 0 || !mwpm.matching(e), |
|
364 "Non-zero reduced weight on matching edge"); |
|
365 } |
|
366 |
|
367 int pv = 0; |
|
368 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
369 check(mwpm.matching(n) != INVALID, "Non perfect"); |
|
370 pv += weight[mwpm.matching(n)]; |
|
371 SmartGraph::Node o = graph.target(mwpm.matching(n)); |
|
372 check(mwpm.mate(n) == o, "Invalid matching"); |
|
373 check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)), |
|
374 "Invalid matching"); |
|
375 } |
|
376 |
|
377 int dv = 0; |
|
378 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
|
379 dv += mwpm.nodeValue(n); |
|
380 } |
|
381 |
|
382 for (int i = 0; i < mwpm.blossomNum(); ++i) { |
|
383 check(mwpm.blossomValue(i) >= 0, "Invalid blossom value"); |
|
384 check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size"); |
|
385 dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2); |
|
386 } |
|
387 |
|
388 check(pv * mwpm.dualScale == dv * 2, "Wrong duality"); |
|
389 |
|
390 return; |
|
391 } |
|
392 |
|
393 |
|
394 int main() { |
|
395 |
|
396 for (int i = 0; i < lgfn; ++i) { |
|
397 SmartGraph graph; |
|
398 SmartGraph::EdgeMap<int> weight(graph); |
|
399 |
|
400 istringstream lgfs(lgf[i]); |
|
401 graphReader(graph, lgfs). |
|
402 edgeMap("weight", weight).run(); |
|
403 |
|
404 MaxMatching<SmartGraph> mm(graph); |
|
405 mm.run(); |
|
406 checkMatching(graph, mm); |
|
407 |
|
408 MaxWeightedMatching<SmartGraph> mwm(graph, weight); |
|
409 mwm.run(); |
|
410 checkWeightedMatching(graph, weight, mwm); |
|
411 |
|
412 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight); |
|
413 bool perfect = mwpm.run(); |
|
414 |
|
415 check(perfect == (mm.matchingSize() * 2 == countNodes(graph)), |
|
416 "Perfect matching found"); |
|
417 |
|
418 if (perfect) { |
|
419 checkWeightedPerfectMatching(graph, weight, mwpm); |
|
420 } |
|
421 } |
|
422 |
|
423 return 0; |
|
424 } |
|