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