Changeset 884:bc75ee2ad082 in lemon
 Timestamp:
 11/13/09 00:23:07 (15 years ago)
 Branch:
 default
 Phase:
 public
 Rebase:
 65656431343031623762366435616430366631313134323838366233633836663331376338613038
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/min_cost_flow_test.cc
r716 r884 33 33 using namespace lemon; 34 34 35 // Test networks 35 36 char test_lgf[] = 36 37 "@nodes\n" … … 77 78 "target 12\n"; 78 79 80 char test_neg1_lgf[] = 81 "@nodes\n" 82 "label sup\n" 83 " 1 100\n" 84 " 2 0\n" 85 " 3 0\n" 86 " 4 100\n" 87 " 5 0\n" 88 " 6 0\n" 89 " 7 0\n" 90 "@arcs\n" 91 " cost low1 low2\n" 92 "1 2 100 0 0\n" 93 "1 3 30 0 0\n" 94 "2 4 20 0 0\n" 95 "3 4 80 0 0\n" 96 "3 2 50 0 0\n" 97 "5 3 10 0 0\n" 98 "5 6 80 0 1000\n" 99 "6 7 30 0 1000\n" 100 "7 5 120 0 0\n"; 101 102 char test_neg2_lgf[] = 103 "@nodes\n" 104 "label sup\n" 105 " 1 100\n" 106 " 2 300\n" 107 "@arcs\n" 108 " cost\n" 109 "1 2 1\n"; 110 111 112 // Test data 113 typedef ListDigraph Digraph; 114 DIGRAPH_TYPEDEFS(ListDigraph); 115 116 Digraph gr; 117 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr); 118 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); 119 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 120 Node v, w; 121 122 Digraph neg1_gr; 123 Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr); 124 ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000); 125 Digraph::NodeMap<int> neg1_s(neg1_gr); 126 127 Digraph neg2_gr; 128 Digraph::ArcMap<int> neg2_c(neg2_gr); 129 ConstMap<Arc, int> neg2_l(0), neg2_u(1000); 130 Digraph::NodeMap<int> neg2_s(neg2_gr); 131 79 132 80 133 enum SupplyType { … … 83 136 LEQ 84 137 }; 138 85 139 86 140 // Check the interface of an MCF algorithm … … 269 323 } 270 324 325 template < typename MCF, typename Param > 326 void runMcfGeqTests( Param param, 327 const std::string &test_str = "", 328 bool full_neg_cost_support = false ) 329 { 330 MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr); 331 332 // Basic tests 333 mcf1.upperMap(u).costMap(c).supplyMap(s1); 334 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1, 335 mcf1.OPTIMAL, true, 5240, test_str + "1"); 336 mcf1.stSupply(v, w, 27); 337 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2, 338 mcf1.OPTIMAL, true, 7620, test_str + "2"); 339 mcf1.lowerMap(l2).supplyMap(s1); 340 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1, 341 mcf1.OPTIMAL, true, 5970, test_str + "3"); 342 mcf1.stSupply(v, w, 27); 343 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2, 344 mcf1.OPTIMAL, true, 8010, test_str + "4"); 345 mcf1.reset().supplyMap(s1); 346 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1, 347 mcf1.OPTIMAL, true, 74, test_str + "5"); 348 mcf1.lowerMap(l2).stSupply(v, w, 27); 349 checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2, 350 mcf1.OPTIMAL, true, 94, test_str + "6"); 351 mcf1.reset(); 352 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3, 353 mcf1.OPTIMAL, true, 0, test_str + "7"); 354 mcf1.lowerMap(l2).upperMap(u); 355 checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3, 356 mcf1.INFEASIBLE, false, 0, test_str + "8"); 357 mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); 358 checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4, 359 mcf1.OPTIMAL, true, 6360, test_str + "9"); 360 361 // Tests for the GEQ form 362 mcf1.reset().upperMap(u).costMap(c).supplyMap(s5); 363 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5, 364 mcf1.OPTIMAL, true, 3530, test_str + "10", GEQ); 365 mcf1.lowerMap(l2); 366 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, 367 mcf1.OPTIMAL, true, 4540, test_str + "11", GEQ); 368 mcf1.supplyMap(s6); 369 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, 370 mcf1.INFEASIBLE, false, 0, test_str + "12", GEQ); 371 372 // Tests with negative costs 373 mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s); 374 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s, 375 mcf2.UNBOUNDED, false, 0, test_str + "13"); 376 mcf2.upperMap(neg1_u2); 377 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s, 378 mcf2.OPTIMAL, true, 40000, test_str + "14"); 379 mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s); 380 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s, 381 mcf2.UNBOUNDED, false, 0, test_str + "15"); 382 383 mcf3.costMap(neg2_c).supplyMap(neg2_s); 384 if (full_neg_cost_support) { 385 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, 386 mcf3.OPTIMAL, true, 300, test_str + "16", GEQ); 387 } else { 388 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, 389 mcf3.UNBOUNDED, false, 0, test_str + "17", GEQ); 390 } 391 mcf3.upperMap(neg2_u); 392 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, 393 mcf3.OPTIMAL, true, 300, test_str + "18", GEQ); 394 } 395 396 template < typename MCF, typename Param > 397 void runMcfLeqTests( Param param, 398 const std::string &test_str = "" ) 399 { 400 // Tests for the LEQ form 401 MCF mcf1(gr); 402 mcf1.supplyType(mcf1.LEQ); 403 mcf1.upperMap(u).costMap(c).supplyMap(s6); 404 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6, 405 mcf1.OPTIMAL, true, 5080, test_str + "19", LEQ); 406 mcf1.lowerMap(l2); 407 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, 408 mcf1.OPTIMAL, true, 5930, test_str + "20", LEQ); 409 mcf1.supplyMap(s5); 410 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, 411 mcf1.INFEASIBLE, false, 0, test_str + "21", LEQ); 412 } 413 414 271 415 int main() 272 416 { 273 // Check the interfaces 274 { 275 typedef concepts::Digraph GR; 276 checkConcept< McfClassConcept<GR, int, int>, 277 NetworkSimplex<GR> >(); 278 checkConcept< McfClassConcept<GR, double, double>, 279 NetworkSimplex<GR, double> >(); 280 checkConcept< McfClassConcept<GR, int, double>, 281 NetworkSimplex<GR, int, double> >(); 282 } 283 284 // Run various MCF tests 285 typedef ListDigraph Digraph; 286 DIGRAPH_TYPEDEFS(ListDigraph); 287 288 // Read the test digraph 289 Digraph gr; 290 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr); 291 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); 292 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 293 Node v, w; 294 417 // Read the test networks 295 418 std::istringstream input(test_lgf); 296 419 DigraphReader<Digraph>(gr, input) … … 310 433 .run(); 311 434 312 // Build test digraphs with negative costs 313 Digraph neg_gr; 314 Node n1 = neg_gr.addNode(); 315 Node n2 = neg_gr.addNode(); 316 Node n3 = neg_gr.addNode(); 317 Node n4 = neg_gr.addNode(); 318 Node n5 = neg_gr.addNode(); 319 Node n6 = neg_gr.addNode(); 320 Node n7 = neg_gr.addNode(); 321 322 Arc a1 = neg_gr.addArc(n1, n2); 323 Arc a2 = neg_gr.addArc(n1, n3); 324 Arc a3 = neg_gr.addArc(n2, n4); 325 Arc a4 = neg_gr.addArc(n3, n4); 326 Arc a5 = neg_gr.addArc(n3, n2); 327 Arc a6 = neg_gr.addArc(n5, n3); 328 Arc a7 = neg_gr.addArc(n5, n6); 329 Arc a8 = neg_gr.addArc(n6, n7); 330 Arc a9 = neg_gr.addArc(n7, n5); 331 332 Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0); 333 ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000); 334 Digraph::NodeMap<int> neg_s(neg_gr, 0); 335 336 neg_l2[a7] = 1000; 337 neg_l2[a8] = 1000; 338 339 neg_s[n1] = 100; 340 neg_s[n4] = 100; 341 342 neg_c[a1] = 100; 343 neg_c[a2] = 30; 344 neg_c[a3] = 20; 345 neg_c[a4] = 80; 346 neg_c[a5] = 50; 347 neg_c[a6] = 10; 348 neg_c[a7] = 80; 349 neg_c[a8] = 30; 350 neg_c[a9] = 120; 351 352 Digraph negs_gr; 353 Digraph::NodeMap<int> negs_s(negs_gr); 354 Digraph::ArcMap<int> negs_c(negs_gr); 355 ConstMap<Arc, int> negs_l(0), negs_u(1000); 356 n1 = negs_gr.addNode(); 357 n2 = negs_gr.addNode(); 358 negs_s[n1] = 100; 359 negs_s[n2] = 300; 360 negs_c[negs_gr.addArc(n1, n2)] = 1; 361 362 363 // A. Test NetworkSimplex with the default pivot rule 435 std::istringstream neg_inp1(test_neg1_lgf); 436 DigraphReader<Digraph>(neg1_gr, neg_inp1) 437 .arcMap("cost", neg1_c) 438 .arcMap("low1", neg1_l1) 439 .arcMap("low2", neg1_l2) 440 .nodeMap("sup", neg1_s) 441 .run(); 442 443 std::istringstream neg_inp2(test_neg2_lgf); 444 DigraphReader<Digraph>(neg2_gr, neg_inp2) 445 .arcMap("cost", neg2_c) 446 .nodeMap("sup", neg2_s) 447 .run(); 448 449 // Check the interface of NetworkSimplex 364 450 { 365 NetworkSimplex<Digraph> mcf(gr); 366 367 // Check the equality form 368 mcf.upperMap(u).costMap(c); 369 checkMcf(mcf, mcf.supplyMap(s1).run(), 370 gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1"); 371 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 372 gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2"); 373 mcf.lowerMap(l2); 374 checkMcf(mcf, mcf.supplyMap(s1).run(), 375 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3"); 376 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 377 gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4"); 378 mcf.reset(); 379 checkMcf(mcf, mcf.supplyMap(s1).run(), 380 gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5"); 381 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), 382 gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6"); 383 mcf.reset(); 384 checkMcf(mcf, mcf.run(), 385 gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7"); 386 checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(), 387 gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8"); 388 mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); 389 checkMcf(mcf, mcf.run(), 390 gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9"); 391 392 // Check the GEQ form 393 mcf.reset().upperMap(u).costMap(c).supplyMap(s5); 394 checkMcf(mcf, mcf.run(), 395 gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ); 396 mcf.supplyType(mcf.GEQ); 397 checkMcf(mcf, mcf.lowerMap(l2).run(), 398 gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ); 399 mcf.supplyMap(s6); 400 checkMcf(mcf, mcf.run(), 401 gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ); 402 403 // Check the LEQ form 404 mcf.reset().supplyType(mcf.LEQ); 405 mcf.upperMap(u).costMap(c).supplyMap(s6); 406 checkMcf(mcf, mcf.run(), 407 gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ); 408 checkMcf(mcf, mcf.lowerMap(l2).run(), 409 gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); 410 mcf.supplyMap(s5); 411 checkMcf(mcf, mcf.run(), 412 gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); 413 414 // Check negative costs 415 NetworkSimplex<Digraph> neg_mcf(neg_gr); 416 neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s); 417 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1, 418 neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16"); 419 neg_mcf.upperMap(neg_u2); 420 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2, 421 neg_c, neg_s, neg_mcf.OPTIMAL, true, 40000, "#A17"); 422 neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s); 423 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1, 424 neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18"); 425 426 NetworkSimplex<Digraph> negs_mcf(negs_gr); 427 negs_mcf.costMap(negs_c).supplyMap(negs_s); 428 checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u, 429 negs_c, negs_s, negs_mcf.OPTIMAL, true, 300, "#A19", GEQ); 430 } 431 432 // B. Test NetworkSimplex with each pivot rule 433 { 434 NetworkSimplex<Digraph> mcf(gr); 435 mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2); 436 437 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE), 438 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1"); 439 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE), 440 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2"); 441 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH), 442 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3"); 443 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST), 444 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4"); 445 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST), 446 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5"); 451 typedef concepts::Digraph GR; 452 checkConcept< McfClassConcept<GR, int, int>, 453 NetworkSimplex<GR> >(); 454 checkConcept< McfClassConcept<GR, double, double>, 455 NetworkSimplex<GR, double> >(); 456 checkConcept< McfClassConcept<GR, int, double>, 457 NetworkSimplex<GR, int, double> >(); 458 } 459 460 // Test NetworkSimplex 461 { 462 typedef NetworkSimplex<Digraph> MCF; 463 runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NSFE", true); 464 runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NSFE"); 465 runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE, "NSBE", true); 466 runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE, "NSBE"); 467 runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH, "NSBS", true); 468 runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH, "NSBS"); 469 runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NSCL", true); 470 runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NSCL"); 471 runMcfGeqTests<MCF>(MCF::ALTERING_LIST, "NSAL", true); 472 runMcfLeqTests<MCF>(MCF::ALTERING_LIST, "NSAL"); 447 473 } 448 474
Note: See TracChangeset
for help on using the changeset viewer.