Changeset 2058:0b1fc1566fdb in lemon-0.x for test/bipartite_matching_test.cc
- Timestamp:
- 04/18/06 09:01:55 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2702
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/bipartite_matching_test.cc
r2051 r2058 24 24 vector<Node> aNodes; 25 25 vector<Node> bNodes; 26 int n = argc > 1 ? atoi(argv[1]) : 10 0;27 int m = argc > 2 ? atoi(argv[2]) : 10 0;26 int n = argc > 1 ? atoi(argv[1]) : 10; 27 int m = argc > 2 ? atoi(argv[2]) : 10; 28 28 int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m)); 29 29 int c = argc > 4 ? atoi(argv[4]) : 100; … … 34 34 int max_weight; 35 35 int max_cardinality_max_weight; 36 int min_cost_matching; 36 37 37 38 for (int i = 0; i < n; ++i) { … … 72 73 } 73 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 … … 138 154 for (UEdgeIt it(graph); it != INVALID; ++it) { 139 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 157 "INVALID DUAL"); 142 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 160 "INVALID DUAL"); 145 161 } … … 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 193 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight); 163 194 … … 172 203 for (UEdgeIt it(graph); it != INVALID; ++it) { 173 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 206 "INVALID DUAL"); 176 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 209 "INVALID DUAL"); 179 210 } … … 203 234 for (UEdgeIt it(graph); it != INVALID; ++it) { 204 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 237 "INVALID DUAL"); 207 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 240 "INVALID DUAL"); 210 241 } … … 224 255 225 256 { 226 Graph::UEdgeMap<int> cost(graph); 227 228 cost = subMap(constMap<UEdge>(c), weight); 257 Graph::UEdgeMap<bool> mm(graph); 258 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 277 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost); … … 256 303 } 257 304 305 min_cost_matching = bpmatch.matchingCost(); 258 306 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); 259 307 check(max_cardinality * c - max_cardinality_max_weight … … 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 328 return 0; 265 329 }
Note: See TracChangeset
for help on using the changeset viewer.