Append the svn revision number to the version string automatically.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
23 #include <lemon/smart_graph.h>
25 #include <lemon/bpugraph_adaptor.h>
26 #include <lemon/bipartite_matching.h>
28 #include <lemon/graph_utils.h>
30 #include <lemon/maps.h>
32 #include "test_tools.h"
35 using namespace lemon;
37 typedef SmartBpUGraph Graph;
38 BPUGRAPH_TYPEDEFS(Graph);
45 const int sa[E] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,
46 2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,
47 4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,
48 8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};
50 const int ta[E] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,
51 3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,
52 6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,
53 4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};
55 const int wa[E] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,
56 13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,
57 54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,
58 60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};
66 Graph::UEdgeMap<int> weight(graph);
70 int max_cardinality_max_weight;
71 int min_cost_matching;
73 for (int i = 0; i < N; ++i) {
74 Node node = graph.addANode();
75 aNodes.push_back(node);
77 for (int i = 0; i < M; ++i) {
78 Node node = graph.addBNode();
79 bNodes.push_back(node);
81 for (int i = 0; i < E; ++i) {
82 Node aNode = aNodes[sa[i]];
83 Node bNode = bNodes[ta[i]];
84 UEdge uedge = graph.addEdge(aNode, bNode);
85 weight[uedge] = wa[i];
90 MaxBipartiteMatching<Graph> bpmatch(graph);
94 Graph::UEdgeMap<bool> mm(graph);
95 Graph::NodeMap<bool> cs(graph);
97 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
99 for (UEdgeIt it(graph); it != INVALID; ++it) {
100 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
103 for (ANodeIt it(graph); it != INVALID; ++it) {
105 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
108 check(num <= 1, "INVALID PRIMAL");
110 max_cardinality = bpmatch.matchingSize();
114 Graph::UEdgeMap<bool> mm(graph);
116 check(max_cardinality == maxBipartiteMatching(graph, mm),
119 for (ANodeIt it(graph); it != INVALID; ++it) {
121 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
124 check(num <= 1, "INVALID PRIMAL");
129 MaxBipartiteMatching<Graph> bpmatch(graph);
131 bpmatch.greedyInit();
134 Graph::UEdgeMap<bool> mm(graph);
135 Graph::NodeMap<bool> cs(graph);
137 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
139 for (UEdgeIt it(graph); it != INVALID; ++it) {
140 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
143 for (ANodeIt it(graph); it != INVALID; ++it) {
145 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
148 check(num <= 1, "INVALID PRIMAL");
153 MaxBipartiteMatching<Graph> bpmatch(graph);
155 bpmatch.greedyInit();
156 while (bpmatch.simpleAugment());
158 Graph::UEdgeMap<bool> mm(graph);
159 Graph::NodeMap<bool> cs(graph);
161 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
163 for (UEdgeIt it(graph); it != INVALID; ++it) {
164 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
167 for (ANodeIt it(graph); it != INVALID; ++it) {
169 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
172 check(num <= 1, "INVALID PRIMAL");
177 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
182 while (bpmatch.augment(true)) {
184 Graph::UEdgeMap<bool> mm(graph);
185 Graph::NodeMap<int> pm(graph);
187 bpmatch.matching(mm);
188 bpmatch.potential(pm);
190 for (UEdgeIt it(graph); it != INVALID; ++it) {
192 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
195 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
200 for (ANodeIt it(graph); it != INVALID; ++it) {
202 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
205 check(num <= 1, "INVALID PRIMAL");
207 if (bpmatch.matchingValue() > max_weight) {
208 max_weight = bpmatch.matchingValue();
214 Graph::UEdgeMap<bool> mm(graph);
216 check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
219 for (ANodeIt it(graph); it != INVALID; ++it) {
221 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
224 check(num <= 1, "INVALID PRIMAL");
229 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
233 Graph::UEdgeMap<bool> mm(graph);
234 Graph::NodeMap<int> pm(graph);
236 bpmatch.matching(mm);
237 bpmatch.potential(pm);
239 for (UEdgeIt it(graph); it != INVALID; ++it) {
241 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
244 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
249 for (ANodeIt it(graph); it != INVALID; ++it) {
251 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
254 check(num <= 1, "INVALID PRIMAL");
256 check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
260 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
264 Graph::UEdgeMap<bool> mm(graph);
265 Graph::NodeMap<int> pm(graph);
267 bpmatch.matching(mm);
268 bpmatch.potential(pm);
270 for (UEdgeIt it(graph); it != INVALID; ++it) {
272 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
275 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
280 for (ANodeIt it(graph); it != INVALID; ++it) {
282 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
285 check(num <= 1, "INVALID PRIMAL");
287 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
288 max_cardinality_max_weight = bpmatch.matchingValue();
293 Graph::UEdgeMap<bool> mm(graph);
295 check(max_cardinality_max_weight ==
296 maxWeightedMaxBipartiteMatching(graph, weight, mm),
299 for (ANodeIt it(graph); it != INVALID; ++it) {
301 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
304 check(num <= 1, "INVALID PRIMAL");
308 Graph::UEdgeMap<int> cost(graph);
309 cost = subMap(constMap<UEdge>(C), weight);
312 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
316 Graph::UEdgeMap<bool> mm(graph);
317 Graph::NodeMap<int> pm(graph);
319 bpmatch.matching(mm);
320 bpmatch.potential(pm);
322 min_cost_matching = bpmatch.matchingCost();
323 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
324 check(max_cardinality * C - max_cardinality_max_weight
325 == bpmatch.matchingCost(), "WRONG SIZE");
327 for (UEdgeIt it(graph); it != INVALID; ++it) {
329 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
332 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
337 for (ANodeIt it(graph); it != INVALID; ++it) {
339 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
342 check(num <= 1, "INVALID PRIMAL");
345 min_cost_matching = bpmatch.matchingCost();
346 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
347 check(max_cardinality * C - max_cardinality_max_weight
348 == bpmatch.matchingCost(), "WRONG SIZE");
353 Graph::UEdgeMap<bool> mm(graph);
355 check(min_cost_matching ==
356 minCostMaxBipartiteMatching(graph, cost, mm),
359 for (ANodeIt it(graph); it != INVALID; ++it) {
361 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
364 check(num <= 1, "INVALID PRIMAL");