Changes in test/min_cost_flow_test.cc [716:4faca85d40e6:898:75c97c3786d6] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/min_cost_flow_test.cc
r716 r898 25 25 26 26 #include <lemon/network_simplex.h> 27 #include <lemon/capacity_scaling.h> 28 #include <lemon/cost_scaling.h> 29 #include <lemon/cycle_canceling.h> 27 30 28 31 #include <lemon/concepts/digraph.h> 32 #include <lemon/concepts/heap.h> 29 33 #include <lemon/concept_check.h> 30 34 … … 33 37 using namespace lemon; 34 38 39 // Test networks 35 40 char test_lgf[] = 36 41 "@nodes\n" … … 77 82 "target 12\n"; 78 83 84 char test_neg1_lgf[] = 85 "@nodes\n" 86 "label sup\n" 87 " 1 100\n" 88 " 2 0\n" 89 " 3 0\n" 90 " 4 -100\n" 91 " 5 0\n" 92 " 6 0\n" 93 " 7 0\n" 94 "@arcs\n" 95 " cost low1 low2\n" 96 "1 2 100 0 0\n" 97 "1 3 30 0 0\n" 98 "2 4 20 0 0\n" 99 "3 4 80 0 0\n" 100 "3 2 50 0 0\n" 101 "5 3 10 0 0\n" 102 "5 6 80 0 1000\n" 103 "6 7 30 0 -1000\n" 104 "7 5 -120 0 0\n"; 105 106 char test_neg2_lgf[] = 107 "@nodes\n" 108 "label sup\n" 109 " 1 100\n" 110 " 2 -300\n" 111 "@arcs\n" 112 " cost\n" 113 "1 2 -1\n"; 114 115 116 // Test data 117 typedef ListDigraph Digraph; 118 DIGRAPH_TYPEDEFS(ListDigraph); 119 120 Digraph gr; 121 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr); 122 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); 123 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 124 Node v, w; 125 126 Digraph neg1_gr; 127 Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr); 128 ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000); 129 Digraph::NodeMap<int> neg1_s(neg1_gr); 130 131 Digraph neg2_gr; 132 Digraph::ArcMap<int> neg2_c(neg2_gr); 133 ConstMap<Arc, int> neg2_l(0), neg2_u(1000); 134 Digraph::NodeMap<int> neg2_s(neg2_gr); 135 79 136 80 137 enum SupplyType { … … 83 140 LEQ 84 141 }; 142 85 143 86 144 // Check the interface of an MCF algorithm … … 100 158 const MCF& const_mcf = mcf; 101 159 102 b = mcf.reset() 160 b = mcf.reset().resetParams() 103 161 .lowerMap(me.lower) 104 162 .upperMap(me.upper) … … 269 327 } 270 328 329 template < typename MCF, typename Param > 330 void runMcfGeqTests( Param param, 331 const std::string &test_str = "", 332 bool full_neg_cost_support = false ) 333 { 334 MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr); 335 336 // Basic tests 337 mcf1.upperMap(u).costMap(c).supplyMap(s1); 338 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1, 339 mcf1.OPTIMAL, true, 5240, test_str + "-1"); 340 mcf1.stSupply(v, w, 27); 341 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2, 342 mcf1.OPTIMAL, true, 7620, test_str + "-2"); 343 mcf1.lowerMap(l2).supplyMap(s1); 344 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1, 345 mcf1.OPTIMAL, true, 5970, test_str + "-3"); 346 mcf1.stSupply(v, w, 27); 347 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2, 348 mcf1.OPTIMAL, true, 8010, test_str + "-4"); 349 mcf1.resetParams().supplyMap(s1); 350 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1, 351 mcf1.OPTIMAL, true, 74, test_str + "-5"); 352 mcf1.lowerMap(l2).stSupply(v, w, 27); 353 checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2, 354 mcf1.OPTIMAL, true, 94, test_str + "-6"); 355 mcf1.reset(); 356 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3, 357 mcf1.OPTIMAL, true, 0, test_str + "-7"); 358 mcf1.lowerMap(l2).upperMap(u); 359 checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3, 360 mcf1.INFEASIBLE, false, 0, test_str + "-8"); 361 mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); 362 checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4, 363 mcf1.OPTIMAL, true, 6360, test_str + "-9"); 364 365 // Tests for the GEQ form 366 mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5); 367 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5, 368 mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ); 369 mcf1.lowerMap(l2); 370 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, 371 mcf1.OPTIMAL, true, 4540, test_str + "-11", GEQ); 372 mcf1.supplyMap(s6); 373 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, 374 mcf1.INFEASIBLE, false, 0, test_str + "-12", GEQ); 375 376 // Tests with negative costs 377 mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s); 378 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s, 379 mcf2.UNBOUNDED, false, 0, test_str + "-13"); 380 mcf2.upperMap(neg1_u2); 381 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s, 382 mcf2.OPTIMAL, true, -40000, test_str + "-14"); 383 mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s); 384 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s, 385 mcf2.UNBOUNDED, false, 0, test_str + "-15"); 386 387 mcf3.costMap(neg2_c).supplyMap(neg2_s); 388 if (full_neg_cost_support) { 389 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, 390 mcf3.OPTIMAL, true, -300, test_str + "-16", GEQ); 391 } else { 392 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, 393 mcf3.UNBOUNDED, false, 0, test_str + "-17", GEQ); 394 } 395 mcf3.upperMap(neg2_u); 396 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, 397 mcf3.OPTIMAL, true, -300, test_str + "-18", GEQ); 398 } 399 400 template < typename MCF, typename Param > 401 void runMcfLeqTests( Param param, 402 const std::string &test_str = "" ) 403 { 404 // Tests for the LEQ form 405 MCF mcf1(gr); 406 mcf1.supplyType(mcf1.LEQ); 407 mcf1.upperMap(u).costMap(c).supplyMap(s6); 408 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6, 409 mcf1.OPTIMAL, true, 5080, test_str + "-19", LEQ); 410 mcf1.lowerMap(l2); 411 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, 412 mcf1.OPTIMAL, true, 5930, test_str + "-20", LEQ); 413 mcf1.supplyMap(s5); 414 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, 415 mcf1.INFEASIBLE, false, 0, test_str + "-21", LEQ); 416 } 417 418 271 419 int main() 272 420 { 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 421 // Read the test networks 295 422 std::istringstream input(test_lgf); 296 423 DigraphReader<Digraph>(gr, input) … … 310 437 .run(); 311 438 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 364 { 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"); 439 std::istringstream neg_inp1(test_neg1_lgf); 440 DigraphReader<Digraph>(neg1_gr, neg_inp1) 441 .arcMap("cost", neg1_c) 442 .arcMap("low1", neg1_l1) 443 .arcMap("low2", neg1_l2) 444 .nodeMap("sup", neg1_s) 445 .run(); 446 447 std::istringstream neg_inp2(test_neg2_lgf); 448 DigraphReader<Digraph>(neg2_gr, neg_inp2) 449 .arcMap("cost", neg2_c) 450 .nodeMap("sup", neg2_s) 451 .run(); 452 453 // Check the interface of NetworkSimplex 454 { 455 typedef concepts::Digraph GR; 456 checkConcept< McfClassConcept<GR, int, int>, 457 NetworkSimplex<GR> >(); 458 checkConcept< McfClassConcept<GR, double, double>, 459 NetworkSimplex<GR, double> >(); 460 checkConcept< McfClassConcept<GR, int, double>, 461 NetworkSimplex<GR, int, double> >(); 462 } 463 464 // Check the interface of CapacityScaling 465 { 466 typedef concepts::Digraph GR; 467 checkConcept< McfClassConcept<GR, int, int>, 468 CapacityScaling<GR> >(); 469 checkConcept< McfClassConcept<GR, double, double>, 470 CapacityScaling<GR, double> >(); 471 checkConcept< McfClassConcept<GR, int, double>, 472 CapacityScaling<GR, int, double> >(); 473 typedef CapacityScaling<GR>:: 474 SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS; 475 checkConcept< McfClassConcept<GR, int, int>, CAS >(); 476 } 477 478 // Check the interface of CostScaling 479 { 480 typedef concepts::Digraph GR; 481 checkConcept< McfClassConcept<GR, int, int>, 482 CostScaling<GR> >(); 483 checkConcept< McfClassConcept<GR, double, double>, 484 CostScaling<GR, double> >(); 485 checkConcept< McfClassConcept<GR, int, double>, 486 CostScaling<GR, int, double> >(); 487 typedef CostScaling<GR>:: 488 SetLargeCost<double>::Create COS; 489 checkConcept< McfClassConcept<GR, int, int>, COS >(); 490 } 491 492 // Check the interface of CycleCanceling 493 { 494 typedef concepts::Digraph GR; 495 checkConcept< McfClassConcept<GR, int, int>, 496 CycleCanceling<GR> >(); 497 checkConcept< McfClassConcept<GR, double, double>, 498 CycleCanceling<GR, double> >(); 499 checkConcept< McfClassConcept<GR, int, double>, 500 CycleCanceling<GR, int, double> >(); 501 } 502 503 // Test NetworkSimplex 504 { 505 typedef NetworkSimplex<Digraph> MCF; 506 runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true); 507 runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE"); 508 runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE", true); 509 runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE"); 510 runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS", true); 511 runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS"); 512 runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true); 513 runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL"); 514 runMcfGeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL", true); 515 runMcfLeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL"); 516 } 517 518 // Test CapacityScaling 519 { 520 typedef CapacityScaling<Digraph> MCF; 521 runMcfGeqTests<MCF>(0, "SSP"); 522 runMcfGeqTests<MCF>(2, "CAS"); 523 } 524 525 // Test CostScaling 526 { 527 typedef CostScaling<Digraph> MCF; 528 runMcfGeqTests<MCF>(MCF::PUSH, "COS-PR"); 529 runMcfGeqTests<MCF>(MCF::AUGMENT, "COS-AR"); 530 runMcfGeqTests<MCF>(MCF::PARTIAL_AUGMENT, "COS-PAR"); 531 } 532 533 // Test CycleCanceling 534 { 535 typedef CycleCanceling<Digraph> MCF; 536 runMcfGeqTests<MCF>(MCF::SIMPLE_CYCLE_CANCELING, "SCC"); 537 runMcfGeqTests<MCF>(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC"); 538 runMcfGeqTests<MCF>(MCF::CANCEL_AND_TIGHTEN, "CAT"); 447 539 } 448 540
Note: See TracChangeset
for help on using the changeset viewer.