Also install .gif files.
5 #include <lemon/list_graph.h>
7 #include <lemon/bpugraph_adaptor.h>
8 #include <lemon/bipartite_matching.h>
10 #include <lemon/graph_utils.h>
12 #include <lemon/maps.h>
14 #include "test_tools.h"
17 using namespace lemon;
19 typedef ListBpUGraph Graph;
20 BPUGRAPH_TYPEDEFS(Graph);
22 int main(int argc, const char *argv[]) {
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;
31 Graph::UEdgeMap<int> weight(graph);
35 int max_cardinality_max_weight;
36 int min_cost_matching;
38 for (int i = 0; i < n; ++i) {
39 Node node = graph.addANode();
40 aNodes.push_back(node);
42 for (int i = 0; i < m; ++i) {
43 Node node = graph.addBNode();
44 bNodes.push_back(node);
46 for (int i = 0; i < e; ++i) {
47 Node aNode = aNodes[urandom(n)];
48 Node bNode = bNodes[urandom(m)];
49 UEdge uedge = graph.addEdge(aNode, bNode);
50 weight[uedge] = urandom(c);
54 MaxBipartiteMatching<Graph> bpmatch(graph);
58 Graph::UEdgeMap<bool> mm(graph);
59 Graph::NodeMap<bool> cs(graph);
61 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
63 for (UEdgeIt it(graph); it != INVALID; ++it) {
64 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
67 for (ANodeIt it(graph); it != INVALID; ++it) {
69 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
72 check(num <= 1, "INVALID PRIMAL");
74 max_cardinality = bpmatch.matchingSize();
78 Graph::UEdgeMap<bool> mm(graph);
80 check(max_cardinality == maxBipartiteMatching(graph, mm),
83 for (ANodeIt it(graph); it != INVALID; ++it) {
85 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
88 check(num <= 1, "INVALID PRIMAL");
93 MaxBipartiteMatching<Graph> bpmatch(graph);
98 Graph::UEdgeMap<bool> mm(graph);
99 Graph::NodeMap<bool> cs(graph);
101 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
103 for (UEdgeIt it(graph); it != INVALID; ++it) {
104 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
107 for (ANodeIt it(graph); it != INVALID; ++it) {
109 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
112 check(num <= 1, "INVALID PRIMAL");
117 MaxBipartiteMatching<Graph> bpmatch(graph);
119 bpmatch.greedyInit();
120 while (bpmatch.simpleAugment());
122 Graph::UEdgeMap<bool> mm(graph);
123 Graph::NodeMap<bool> cs(graph);
125 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
127 for (UEdgeIt it(graph); it != INVALID; ++it) {
128 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
131 for (ANodeIt it(graph); it != INVALID; ++it) {
133 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
136 check(num <= 1, "INVALID PRIMAL");
141 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
146 while (bpmatch.augment(true)) {
148 Graph::UEdgeMap<bool> mm(graph);
149 Graph::NodeMap<int> pm(graph);
151 bpmatch.matching(mm);
152 bpmatch.potential(pm);
154 for (UEdgeIt it(graph); it != INVALID; ++it) {
156 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
159 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
164 for (ANodeIt it(graph); it != INVALID; ++it) {
166 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
169 check(num <= 1, "INVALID PRIMAL");
171 if (bpmatch.matchingValue() > max_weight) {
172 max_weight = bpmatch.matchingValue();
178 Graph::UEdgeMap<bool> mm(graph);
180 check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
183 for (ANodeIt it(graph); it != INVALID; ++it) {
185 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
188 check(num <= 1, "INVALID PRIMAL");
193 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
197 Graph::UEdgeMap<bool> mm(graph);
198 Graph::NodeMap<int> pm(graph);
200 bpmatch.matching(mm);
201 bpmatch.potential(pm);
203 for (UEdgeIt it(graph); it != INVALID; ++it) {
205 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
208 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
213 for (ANodeIt it(graph); it != INVALID; ++it) {
215 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
218 check(num <= 1, "INVALID PRIMAL");
220 check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
224 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
228 Graph::UEdgeMap<bool> mm(graph);
229 Graph::NodeMap<int> pm(graph);
231 bpmatch.matching(mm);
232 bpmatch.potential(pm);
234 for (UEdgeIt it(graph); it != INVALID; ++it) {
236 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
239 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
244 for (ANodeIt it(graph); it != INVALID; ++it) {
246 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
249 check(num <= 1, "INVALID PRIMAL");
251 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
252 max_cardinality_max_weight = bpmatch.matchingValue();
257 Graph::UEdgeMap<bool> mm(graph);
259 check(max_cardinality_max_weight ==
260 maxWeightedMaxBipartiteMatching(graph, weight, mm),
263 for (ANodeIt it(graph); it != INVALID; ++it) {
265 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
268 check(num <= 1, "INVALID PRIMAL");
272 Graph::UEdgeMap<int> cost(graph);
273 cost = subMap(constMap<UEdge>(c), weight);
277 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
281 Graph::UEdgeMap<bool> mm(graph);
282 Graph::NodeMap<int> pm(graph);
284 bpmatch.matching(mm);
285 bpmatch.potential(pm);
287 for (UEdgeIt it(graph); it != INVALID; ++it) {
289 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
292 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
297 for (ANodeIt it(graph); it != INVALID; ++it) {
299 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
302 check(num <= 1, "INVALID PRIMAL");
305 min_cost_matching = bpmatch.matchingCost();
306 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
307 check(max_cardinality * c - max_cardinality_max_weight
308 == bpmatch.matchingCost(), "WRONG SIZE");
313 Graph::UEdgeMap<bool> mm(graph);
315 check(min_cost_matching ==
316 minCostMaxBipartiteMatching(graph, cost, mm),
319 for (ANodeIt it(graph); it != INVALID; ++it) {
321 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
324 check(num <= 1, "INVALID PRIMAL");