| changeset 2609 | c36f00f19f2b |
| parent 2553 | bfced05fa852 |
| child 2618 | 6aa6fcaeaea5 |
| 10:84fb800377a1 | 11:ec5f4ae4efd8 |
|---|---|
36 using namespace lemon; |
36 using namespace lemon; |
37 |
37 |
38 typedef SmartBpUGraph Graph; |
38 typedef SmartBpUGraph Graph; |
39 BPUGRAPH_TYPEDEFS(Graph); |
39 BPUGRAPH_TYPEDEFS(Graph); |
40 |
40 |
41 const int N = 10; |
41 const int NN = 10; |
42 const int M = 10; |
42 const int MM = 10; |
43 const int E = 52; |
43 const int EE = 52; |
44 const int C = 100; |
44 const int CC = 100; |
45 |
45 |
46 const int sa[E] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5, |
46 const int sa[EE] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5, |
47 2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8, |
47 2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8, |
48 4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8, |
48 4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8, |
49 8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4}; |
49 8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4}; |
50 |
50 |
51 const int ta[E] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6, |
51 const int ta[EE] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6, |
52 3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0, |
52 3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0, |
53 6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1, |
53 6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1, |
54 4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6}; |
54 4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6}; |
55 |
55 |
56 const int wa[E] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95, |
56 const int wa[EE] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95, |
57 13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43, |
57 13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43, |
58 54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91, |
58 54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91, |
59 60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47}; |
59 60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47}; |
60 |
60 |
61 |
61 |
69 int max_cardinality; |
69 int max_cardinality; |
70 int max_weight; |
70 int max_weight; |
71 int max_cardinality_max_weight; |
71 int max_cardinality_max_weight; |
72 int min_cost_matching; |
72 int min_cost_matching; |
73 |
73 |
74 for (int i = 0; i < N; ++i) { |
74 for (int i = 0; i < NN; ++i) { |
75 Node node = graph.addANode(); |
75 Node node = graph.addANode(); |
76 aNodes.push_back(node); |
76 aNodes.push_back(node); |
77 } |
77 } |
78 for (int i = 0; i < M; ++i) { |
78 for (int i = 0; i < MM; ++i) { |
79 Node node = graph.addBNode(); |
79 Node node = graph.addBNode(); |
80 bNodes.push_back(node); |
80 bNodes.push_back(node); |
81 } |
81 } |
82 for (int i = 0; i < E; ++i) { |
82 for (int i = 0; i < EE; ++i) { |
83 Node aNode = aNodes[sa[i]]; |
83 Node aNode = aNodes[sa[i]]; |
84 Node bNode = bNodes[ta[i]]; |
84 Node bNode = bNodes[ta[i]]; |
85 UEdge uedge = graph.addEdge(aNode, bNode); |
85 UEdge uedge = graph.addEdge(aNode, bNode); |
86 weight[uedge] = wa[i]; |
86 weight[uedge] = wa[i]; |
87 } |
87 } |
346 check(num <= 1, "INVALID PRIMAL"); |
346 check(num <= 1, "INVALID PRIMAL"); |
347 } |
347 } |
348 } |
348 } |
349 |
349 |
350 Graph::UEdgeMap<int> cost(graph); |
350 Graph::UEdgeMap<int> cost(graph); |
351 cost = subMap(constMap<UEdge>(C), weight); |
351 cost = subMap(constMap<UEdge>(CC), weight); |
352 { |
352 { |
353 |
353 |
354 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost); |
354 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost); |
355 |
355 |
356 bpmatch.run(); |
356 bpmatch.run(); |
361 bpmatch.matching(mm); |
361 bpmatch.matching(mm); |
362 bpmatch.potential(pm); |
362 bpmatch.potential(pm); |
363 |
363 |
364 min_cost_matching = bpmatch.matchingCost(); |
364 min_cost_matching = bpmatch.matchingCost(); |
365 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
365 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
366 check(max_cardinality * C - max_cardinality_max_weight |
366 check(max_cardinality * CC - max_cardinality_max_weight |
367 == bpmatch.matchingCost(), "WRONG SIZE"); |
367 == bpmatch.matchingCost(), "WRONG SIZE"); |
368 |
368 |
369 for (UEdgeIt it(graph); it != INVALID; ++it) { |
369 for (UEdgeIt it(graph); it != INVALID; ++it) { |
370 if (mm[it]) { |
370 if (mm[it]) { |
371 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0, |
371 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0, |
384 check(num <= 1, "INVALID PRIMAL"); |
384 check(num <= 1, "INVALID PRIMAL"); |
385 } |
385 } |
386 |
386 |
387 min_cost_matching = bpmatch.matchingCost(); |
387 min_cost_matching = bpmatch.matchingCost(); |
388 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
388 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
389 check(max_cardinality * C - max_cardinality_max_weight |
389 check(max_cardinality * CC - max_cardinality_max_weight |
390 == bpmatch.matchingCost(), "WRONG SIZE"); |
390 == bpmatch.matchingCost(), "WRONG SIZE"); |
391 |
391 |
392 } |
392 } |
393 |
393 |
394 { |
394 { |