14 #include "test_tools.h" |
14 #include "test_tools.h" |
15 |
15 |
16 using namespace std; |
16 using namespace std; |
17 using namespace lemon; |
17 using namespace lemon; |
18 |
18 |
19 typedef ListBpUGraph Graph; |
19 typedef SmartBpUGraph Graph; |
20 BPUGRAPH_TYPEDEFS(Graph); |
20 BPUGRAPH_TYPEDEFS(Graph); |
21 |
21 |
22 int main(int argc, const char *argv[]) { |
22 const int n = 10; |
|
23 const int m = 10; |
|
24 const int e = 52; |
|
25 const int c = 100; |
|
26 |
|
27 const int sa[e] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5, |
|
28 2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8, |
|
29 4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8, |
|
30 8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4}; |
|
31 |
|
32 const int ta[e] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6, |
|
33 3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0, |
|
34 6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1, |
|
35 4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6}; |
|
36 |
|
37 const int wa[e] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95, |
|
38 13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43, |
|
39 54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91, |
|
40 60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47}; |
|
41 |
|
42 |
|
43 int main() { |
23 Graph graph; |
44 Graph graph; |
24 vector<Node> aNodes; |
45 vector<Node> aNodes; |
25 vector<Node> bNodes; |
46 vector<Node> bNodes; |
26 int n = argc > 1 ? atoi(argv[1]) : 10; |
|
27 int m = argc > 2 ? atoi(argv[2]) : 10; |
|
28 int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m)); |
|
29 int c = argc > 4 ? atoi(argv[4]) : 100; |
|
30 |
47 |
31 Graph::UEdgeMap<int> weight(graph); |
48 Graph::UEdgeMap<int> weight(graph); |
32 |
49 |
33 int max_cardinality; |
50 int max_cardinality; |
34 int max_weight; |
51 int max_weight; |
282 Graph::NodeMap<int> pm(graph); |
299 Graph::NodeMap<int> pm(graph); |
283 |
300 |
284 bpmatch.matching(mm); |
301 bpmatch.matching(mm); |
285 bpmatch.potential(pm); |
302 bpmatch.potential(pm); |
286 |
303 |
287 for (UEdgeIt it(graph); it != INVALID; ++it) { |
|
288 if (mm[it]) { |
|
289 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0, |
|
290 "INVALID DUAL"); |
|
291 } else { |
|
292 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0, |
|
293 "INVALID DUAL"); |
|
294 } |
|
295 } |
|
296 |
|
297 for (ANodeIt it(graph); it != INVALID; ++it) { |
|
298 int num = 0; |
|
299 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { |
|
300 if (mm[jt]) ++num; |
|
301 } |
|
302 check(num <= 1, "INVALID PRIMAL"); |
|
303 } |
|
304 |
|
305 min_cost_matching = bpmatch.matchingCost(); |
304 min_cost_matching = bpmatch.matchingCost(); |
306 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
305 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
307 check(max_cardinality * c - max_cardinality_max_weight |
306 check(max_cardinality * c - max_cardinality_max_weight |
308 == bpmatch.matchingCost(), "WRONG SIZE"); |
307 == bpmatch.matchingCost(), "WRONG SIZE"); |
309 |
308 |
|
309 for (UEdgeIt it(graph); it != INVALID; ++it) { |
|
310 if (mm[it]) { |
|
311 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0, |
|
312 "INVALID DUAL"); |
|
313 } else { |
|
314 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0, |
|
315 "INVALID DUAL"); |
|
316 } |
|
317 } |
|
318 |
|
319 for (ANodeIt it(graph); it != INVALID; ++it) { |
|
320 int num = 0; |
|
321 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { |
|
322 if (mm[jt]) ++num; |
|
323 } |
|
324 check(num <= 1, "INVALID PRIMAL"); |
|
325 } |
|
326 |
|
327 min_cost_matching = bpmatch.matchingCost(); |
|
328 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
|
329 check(max_cardinality * c - max_cardinality_max_weight |
|
330 == bpmatch.matchingCost(), "WRONG SIZE"); |
|
331 |
310 } |
332 } |
311 |
333 |
312 { |
334 { |
313 Graph::UEdgeMap<bool> mm(graph); |
335 Graph::UEdgeMap<bool> mm(graph); |
314 |
336 |