equal
deleted
inserted
replaced
21 |
21 |
22 int main(int argc, const char *argv[]) { |
22 int main(int argc, const char *argv[]) { |
23 Graph graph; |
23 Graph graph; |
24 vector<Node> aNodes; |
24 vector<Node> aNodes; |
25 vector<Node> bNodes; |
25 vector<Node> bNodes; |
26 int n = argc > 1 ? atoi(argv[1]) : 100; |
26 int n = argc > 1 ? atoi(argv[1]) : 10; |
27 int m = argc > 2 ? atoi(argv[2]) : 100; |
27 int m = argc > 2 ? atoi(argv[2]) : 10; |
28 int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m)); |
28 int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m)); |
29 int c = argc > 4 ? atoi(argv[4]) : 100; |
29 int c = argc > 4 ? atoi(argv[4]) : 100; |
30 |
30 |
31 Graph::UEdgeMap<int> weight(graph); |
31 Graph::UEdgeMap<int> weight(graph); |
32 |
32 |
33 int max_cardinality; |
33 int max_cardinality; |
34 int max_weight; |
34 int max_weight; |
35 int max_cardinality_max_weight; |
35 int max_cardinality_max_weight; |
|
36 int min_cost_matching; |
36 |
37 |
37 for (int i = 0; i < n; ++i) { |
38 for (int i = 0; i < n; ++i) { |
38 Node node = graph.addANode(); |
39 Node node = graph.addANode(); |
39 aNodes.push_back(node); |
40 aNodes.push_back(node); |
40 } |
41 } |
69 if (mm[jt]) ++num; |
70 if (mm[jt]) ++num; |
70 } |
71 } |
71 check(num <= 1, "INVALID PRIMAL"); |
72 check(num <= 1, "INVALID PRIMAL"); |
72 } |
73 } |
73 max_cardinality = bpmatch.matchingSize(); |
74 max_cardinality = bpmatch.matchingSize(); |
|
75 } |
|
76 |
|
77 { |
|
78 Graph::UEdgeMap<bool> mm(graph); |
|
79 |
|
80 check(max_cardinality == maxBipartiteMatching(graph, mm), |
|
81 "WRONG MATCHING"); |
|
82 |
|
83 for (ANodeIt it(graph); it != INVALID; ++it) { |
|
84 int num = 0; |
|
85 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { |
|
86 if (mm[jt]) ++num; |
|
87 } |
|
88 check(num <= 1, "INVALID PRIMAL"); |
|
89 } |
74 } |
90 } |
75 |
91 |
76 { |
92 { |
77 MaxBipartiteMatching<Graph> bpmatch(graph); |
93 MaxBipartiteMatching<Graph> bpmatch(graph); |
78 |
94 |
135 bpmatch.matching(mm); |
151 bpmatch.matching(mm); |
136 bpmatch.potential(pm); |
152 bpmatch.potential(pm); |
137 |
153 |
138 for (UEdgeIt it(graph); it != INVALID; ++it) { |
154 for (UEdgeIt it(graph); it != INVALID; ++it) { |
139 if (mm[it]) { |
155 if (mm[it]) { |
140 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0, |
156 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, |
141 "INVALID DUAL"); |
157 "INVALID DUAL"); |
142 } else { |
158 } else { |
143 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0, |
159 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, |
144 "INVALID DUAL"); |
160 "INVALID DUAL"); |
145 } |
161 } |
146 } |
162 } |
147 |
163 |
148 for (ANodeIt it(graph); it != INVALID; ++it) { |
164 for (ANodeIt it(graph); it != INVALID; ++it) { |
157 } |
173 } |
158 } |
174 } |
159 } |
175 } |
160 |
176 |
161 { |
177 { |
|
178 Graph::UEdgeMap<bool> mm(graph); |
|
179 |
|
180 check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm), |
|
181 "WRONG MATCHING"); |
|
182 |
|
183 for (ANodeIt it(graph); it != INVALID; ++it) { |
|
184 int num = 0; |
|
185 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { |
|
186 if (mm[jt]) ++num; |
|
187 } |
|
188 check(num <= 1, "INVALID PRIMAL"); |
|
189 } |
|
190 } |
|
191 |
|
192 { |
162 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight); |
193 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight); |
163 |
194 |
164 bpmatch.run(); |
195 bpmatch.run(); |
165 |
196 |
166 Graph::UEdgeMap<bool> mm(graph); |
197 Graph::UEdgeMap<bool> mm(graph); |
169 bpmatch.matching(mm); |
200 bpmatch.matching(mm); |
170 bpmatch.potential(pm); |
201 bpmatch.potential(pm); |
171 |
202 |
172 for (UEdgeIt it(graph); it != INVALID; ++it) { |
203 for (UEdgeIt it(graph); it != INVALID; ++it) { |
173 if (mm[it]) { |
204 if (mm[it]) { |
174 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0, |
205 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, |
175 "INVALID DUAL"); |
206 "INVALID DUAL"); |
176 } else { |
207 } else { |
177 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0, |
208 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, |
178 "INVALID DUAL"); |
209 "INVALID DUAL"); |
179 } |
210 } |
180 } |
211 } |
181 |
212 |
182 for (ANodeIt it(graph); it != INVALID; ++it) { |
213 for (ANodeIt it(graph); it != INVALID; ++it) { |
200 bpmatch.matching(mm); |
231 bpmatch.matching(mm); |
201 bpmatch.potential(pm); |
232 bpmatch.potential(pm); |
202 |
233 |
203 for (UEdgeIt it(graph); it != INVALID; ++it) { |
234 for (UEdgeIt it(graph); it != INVALID; ++it) { |
204 if (mm[it]) { |
235 if (mm[it]) { |
205 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0, |
236 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, |
206 "INVALID DUAL"); |
237 "INVALID DUAL"); |
207 } else { |
238 } else { |
208 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0, |
239 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, |
209 "INVALID DUAL"); |
240 "INVALID DUAL"); |
210 } |
241 } |
211 } |
242 } |
212 |
243 |
213 for (ANodeIt it(graph); it != INVALID; ++it) { |
244 for (ANodeIt it(graph); it != INVALID; ++it) { |
221 max_cardinality_max_weight = bpmatch.matchingValue(); |
252 max_cardinality_max_weight = bpmatch.matchingValue(); |
222 |
253 |
223 } |
254 } |
224 |
255 |
225 { |
256 { |
226 Graph::UEdgeMap<int> cost(graph); |
257 Graph::UEdgeMap<bool> mm(graph); |
227 |
258 |
228 cost = subMap(constMap<UEdge>(c), weight); |
259 check(max_cardinality_max_weight == |
|
260 maxWeightedMaxBipartiteMatching(graph, weight, mm), |
|
261 "WRONG MATCHING"); |
|
262 |
|
263 for (ANodeIt it(graph); it != INVALID; ++it) { |
|
264 int num = 0; |
|
265 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { |
|
266 if (mm[jt]) ++num; |
|
267 } |
|
268 check(num <= 1, "INVALID PRIMAL"); |
|
269 } |
|
270 } |
|
271 |
|
272 Graph::UEdgeMap<int> cost(graph); |
|
273 cost = subMap(constMap<UEdge>(c), weight); |
|
274 |
|
275 { |
229 |
276 |
230 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost); |
277 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost); |
231 |
278 |
232 bpmatch.run(); |
279 bpmatch.run(); |
233 |
280 |
253 if (mm[jt]) ++num; |
300 if (mm[jt]) ++num; |
254 } |
301 } |
255 check(num <= 1, "INVALID PRIMAL"); |
302 check(num <= 1, "INVALID PRIMAL"); |
256 } |
303 } |
257 |
304 |
|
305 min_cost_matching = bpmatch.matchingCost(); |
258 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
306 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); |
259 check(max_cardinality * c - max_cardinality_max_weight |
307 check(max_cardinality * c - max_cardinality_max_weight |
260 == bpmatch.matchingCost(), "WRONG SIZE"); |
308 == bpmatch.matchingCost(), "WRONG SIZE"); |
261 |
309 |
262 } |
310 } |
263 |
311 |
|
312 { |
|
313 Graph::UEdgeMap<bool> mm(graph); |
|
314 |
|
315 check(min_cost_matching == |
|
316 minCostMaxBipartiteMatching(graph, cost, mm), |
|
317 "WRONG MATCHING"); |
|
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 |
264 return 0; |
328 return 0; |
265 } |
329 } |