COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 818:bc75ee2ad082 in lemon-main


Ignore:
Timestamp:
11/13/09 00:23:07 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Rebase:
65656431343031623762366435616430366631313134323838366233633836663331376338613038
Message:

Rework the MCF test file to help extending it (#180)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • test/min_cost_flow_test.cc

    r669 r818  
    3333using namespace lemon;
    3434
     35// Test networks
    3536char test_lgf[] =
    3637  "@nodes\n"
    … …  
    7778  "target 12\n";
    7879
     80char 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 
     102char 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
     113typedef ListDigraph Digraph;
     114DIGRAPH_TYPEDEFS(ListDigraph);
     115
     116Digraph gr;
     117Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
     118Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
     119ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
     120Node v, w;
     121
     122Digraph neg1_gr;
     123Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
     124ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
     125Digraph::NodeMap<int> neg1_s(neg1_gr);
     126
     127Digraph neg2_gr;
     128Digraph::ArcMap<int> neg2_c(neg2_gr);
     129ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
     130Digraph::NodeMap<int> neg2_s(neg2_gr);
     131
    79132
    80133enum SupplyType {
    … …  
    83136  LEQ
    84137};
     138
    85139
    86140// Check the interface of an MCF algorithm
    … …  
    269323}
    270324
     325template < typename MCF, typename Param >
     326void 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
     396template < typename MCF, typename Param >
     397void 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
    271415int main()
    272416{
    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
    295418  std::istringstream input(test_lgf);
    296419  DigraphReader<Digraph>(gr, input)
    … …  
    310433    .run();
    311434 
    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
    364450  {
    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, "NS-FE", true);
     464    runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
     465    runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE", true);
     466    runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE");
     467    runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS", true);
     468    runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS");
     469    runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
     470    runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
     471    runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
     472    runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
    447473  }
    448474
Note: See TracChangeset for help on using the changeset viewer.