Avoid map copy in MinCostMaxFlow.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
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>
27 #include <lemon/pr_bipartite_matching.h>
29 #include <lemon/graph_utils.h>
31 #include <lemon/maps.h>
33 #include "test_tools.h"
36 using namespace lemon;
38 typedef SmartBpUGraph Graph;
39 BPUGRAPH_TYPEDEFS(Graph);
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,
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};
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,
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};
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,
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};
67 Graph::UEdgeMap<int> weight(graph);
71 int max_cardinality_max_weight;
72 int min_cost_matching;
74 for (int i = 0; i < NN; ++i) {
75 Node node = graph.addANode();
76 aNodes.push_back(node);
78 for (int i = 0; i < MM; ++i) {
79 Node node = graph.addBNode();
80 bNodes.push_back(node);
82 for (int i = 0; i < EE; ++i) {
83 Node aNode = aNodes[sa[i]];
84 Node bNode = bNodes[ta[i]];
85 UEdge uedge = graph.addEdge(aNode, bNode);
86 weight[uedge] = wa[i];
91 MaxBipartiteMatching<Graph> bpmatch(graph);
95 Graph::UEdgeMap<bool> mm(graph);
96 Graph::NodeMap<bool> cs(graph);
98 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
100 for (UEdgeIt it(graph); it != INVALID; ++it) {
101 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
104 for (ANodeIt it(graph); it != INVALID; ++it) {
106 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
109 check(num <= 1, "INVALID PRIMAL");
111 max_cardinality = bpmatch.matchingSize();
115 PrBipartiteMatching<Graph> bpmatch(graph);
119 Graph::UEdgeMap<bool> mm(graph);
120 Graph::NodeMap<bool> cs(graph);
122 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
124 for (UEdgeIt it(graph); it != INVALID; ++it) {
125 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
128 for (ANodeIt it(graph); it != INVALID; ++it) {
130 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
133 check(num <= 1, "INVALID PRIMAL");
135 max_cardinality = bpmatch.matchingSize();
139 Graph::ANodeMap<UEdge> mm(graph);
141 check(max_cardinality == maxBipartiteMatching(graph, mm),
144 for (BNodeIt it(graph); it != INVALID; ++it) {
147 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
148 if (mm[graph.aNode(jt)] == jt) ++num;
150 check(num <= 1, "INVALID PRIMAL");
155 Graph::ANodeMap<UEdge> mm(graph);
157 check(max_cardinality == prBipartiteMatching(graph, mm),
160 for (BNodeIt it(graph); it != INVALID; ++it) {
163 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
164 if (mm[graph.aNode(jt)] == jt) ++num;
166 check(num <= 1, "INVALID PRIMAL");
171 MaxBipartiteMatching<Graph> bpmatch(graph);
173 bpmatch.greedyInit();
176 Graph::UEdgeMap<bool> mm(graph);
177 Graph::NodeMap<bool> cs(graph);
179 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
181 for (UEdgeIt it(graph); it != INVALID; ++it) {
182 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
185 for (ANodeIt it(graph); it != INVALID; ++it) {
187 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
190 check(num <= 1, "INVALID PRIMAL");
195 MaxBipartiteMatching<Graph> bpmatch(graph);
197 bpmatch.greedyInit();
198 while (bpmatch.simpleAugment());
200 Graph::UEdgeMap<bool> mm(graph);
201 Graph::NodeMap<bool> cs(graph);
203 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
205 for (UEdgeIt it(graph); it != INVALID; ++it) {
206 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
209 for (ANodeIt it(graph); it != INVALID; ++it) {
211 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
214 check(num <= 1, "INVALID PRIMAL");
219 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
224 while (bpmatch.augment(true)) {
226 Graph::UEdgeMap<bool> mm(graph);
227 Graph::NodeMap<int> pm(graph);
229 bpmatch.matching(mm);
230 bpmatch.potential(pm);
232 for (UEdgeIt it(graph); it != INVALID; ++it) {
234 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
237 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
242 for (ANodeIt it(graph); it != INVALID; ++it) {
244 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
247 check(num <= 1, "INVALID PRIMAL");
249 if (bpmatch.matchingValue() > max_weight) {
250 max_weight = bpmatch.matchingValue();
256 Graph::UEdgeMap<bool> mm(graph);
258 check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
261 for (ANodeIt it(graph); it != INVALID; ++it) {
263 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
266 check(num <= 1, "INVALID PRIMAL");
271 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
275 Graph::UEdgeMap<bool> mm(graph);
276 Graph::NodeMap<int> pm(graph);
278 bpmatch.matching(mm);
279 bpmatch.potential(pm);
281 for (UEdgeIt it(graph); it != INVALID; ++it) {
283 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
286 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
291 for (ANodeIt it(graph); it != INVALID; ++it) {
293 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
296 check(num <= 1, "INVALID PRIMAL");
298 check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
302 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
306 Graph::UEdgeMap<bool> mm(graph);
307 Graph::NodeMap<int> pm(graph);
309 bpmatch.matching(mm);
310 bpmatch.potential(pm);
312 for (UEdgeIt it(graph); it != INVALID; ++it) {
314 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
317 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
322 for (ANodeIt it(graph); it != INVALID; ++it) {
324 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
327 check(num <= 1, "INVALID PRIMAL");
329 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
330 max_cardinality_max_weight = bpmatch.matchingValue();
335 Graph::UEdgeMap<bool> mm(graph);
337 check(max_cardinality_max_weight ==
338 maxWeightedMaxBipartiteMatching(graph, weight, mm),
341 for (ANodeIt it(graph); it != INVALID; ++it) {
343 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
346 check(num <= 1, "INVALID PRIMAL");
350 Graph::UEdgeMap<int> cost(graph);
351 cost = subMap(constMap<UEdge>(CC), weight);
354 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
358 Graph::UEdgeMap<bool> mm(graph);
359 Graph::NodeMap<int> pm(graph);
361 bpmatch.matching(mm);
362 bpmatch.potential(pm);
364 min_cost_matching = bpmatch.matchingCost();
365 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
366 check(max_cardinality * CC - max_cardinality_max_weight
367 == bpmatch.matchingCost(), "WRONG SIZE");
369 for (UEdgeIt it(graph); it != INVALID; ++it) {
371 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
374 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
379 for (ANodeIt it(graph); it != INVALID; ++it) {
381 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
384 check(num <= 1, "INVALID PRIMAL");
387 min_cost_matching = bpmatch.matchingCost();
388 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
389 check(max_cardinality * CC - max_cardinality_max_weight
390 == bpmatch.matchingCost(), "WRONG SIZE");
395 Graph::UEdgeMap<bool> mm(graph);
397 check(min_cost_matching ==
398 minCostMaxBipartiteMatching(graph, cost, mm),
401 for (ANodeIt it(graph); it != INVALID; ++it) {
403 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
406 check(num <= 1, "INVALID PRIMAL");