Changeset 2137:54043fa66bce in lemon-0.x
- Timestamp:
- 07/14/06 12:25:26 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2851
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/bipartite_matching_test.cc
r2116 r2137 3 3 #include <sstream> 4 4 5 #include <lemon/ list_graph.h>5 #include <lemon/smart_graph.h> 6 6 7 7 #include <lemon/bpugraph_adaptor.h> … … 17 17 using namespace lemon; 18 18 19 typedef ListBpUGraph Graph;19 typedef SmartBpUGraph Graph; 20 20 BPUGRAPH_TYPEDEFS(Graph); 21 21 22 int main(int argc, const char *argv[]) { 22 const int n = 10; 23 const int m = 10; 24 const int e = 52; 25 const int c = 100; 26 27 const int sa[e] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5, 28 2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8, 29 4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8, 30 8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4}; 31 32 const int ta[e] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6, 33 3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0, 34 6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1, 35 4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6}; 36 37 const int wa[e] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95, 38 13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43, 39 54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91, 40 60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47}; 41 42 43 int main() { 23 44 Graph graph; 24 45 vector<Node> aNodes; 25 46 vector<Node> bNodes; 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;30 47 31 48 Graph::UEdgeMap<int> weight(graph); … … 45 62 } 46 63 for (int i = 0; i < e; ++i) { 47 Node aNode = aNodes[ urandom(n)];48 Node bNode = bNodes[ urandom(m)];64 Node aNode = aNodes[sa[i]]; 65 Node bNode = bNodes[ta[i]]; 49 66 UEdge uedge = graph.addEdge(aNode, bNode); 50 weight[uedge] = urandom(c); 51 } 67 weight[uedge] = wa[i]; 68 } 69 52 70 53 71 { … … 272 290 Graph::UEdgeMap<int> cost(graph); 273 291 cost = subMap(constMap<UEdge>(c), weight); 274 275 292 { 276 293 … … 285 302 bpmatch.potential(pm); 286 303 287 for (UEdgeIt it(graph); it != INVALID; ++it) {288 if (mm[it]) {289 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,290 "INVALID DUAL");291 } else {292 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,293 "INVALID DUAL");294 }295 }296 297 for (ANodeIt it(graph); it != INVALID; ++it) {298 int num = 0;299 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {300 if (mm[jt]) ++num;301 }302 check(num <= 1, "INVALID PRIMAL");303 }304 305 304 min_cost_matching = bpmatch.matchingCost(); 306 305 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); … … 308 307 == bpmatch.matchingCost(), "WRONG SIZE"); 309 308 309 for (UEdgeIt it(graph); it != INVALID; ++it) { 310 if (mm[it]) { 311 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0, 312 "INVALID DUAL"); 313 } else { 314 check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0, 315 "INVALID DUAL"); 316 } 317 } 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 min_cost_matching = bpmatch.matchingCost(); 328 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); 329 check(max_cardinality * c - max_cardinality_max_weight 330 == bpmatch.matchingCost(), "WRONG SIZE"); 331 310 332 } 311 333
Note: See TracChangeset
for help on using the changeset viewer.