Rework the MCF test file to help extending it (#180)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 00:23:07 +0100
changeset 818bc75ee2ad082
parent 817 b87f0504cdbe
child 819 d93490b861e9
Rework the MCF test file to help extending it (#180)
test/min_cost_flow_test.cc
     1.1 --- a/test/min_cost_flow_test.cc	Fri Nov 13 00:15:50 2009 +0100
     1.2 +++ b/test/min_cost_flow_test.cc	Fri Nov 13 00:23:07 2009 +0100
     1.3 @@ -32,6 +32,7 @@
     1.4  
     1.5  using namespace lemon;
     1.6  
     1.7 +// Test networks
     1.8  char test_lgf[] =
     1.9    "@nodes\n"
    1.10    "label  sup1 sup2 sup3 sup4 sup5 sup6\n"
    1.11 @@ -76,6 +77,58 @@
    1.12    "source 1\n"
    1.13    "target 12\n";
    1.14  
    1.15 +char test_neg1_lgf[] =
    1.16 +  "@nodes\n"
    1.17 +  "label   sup\n"
    1.18 +  "    1   100\n"
    1.19 +  "    2     0\n"
    1.20 +  "    3     0\n"
    1.21 +  "    4  -100\n"
    1.22 +  "    5     0\n"
    1.23 +  "    6     0\n"
    1.24 +  "    7     0\n"
    1.25 +  "@arcs\n"
    1.26 +  "      cost   low1   low2\n"
    1.27 +  "1 2    100      0      0\n"
    1.28 +  "1 3     30      0      0\n"
    1.29 +  "2 4     20      0      0\n"
    1.30 +  "3 4     80      0      0\n"
    1.31 +  "3 2     50      0      0\n"
    1.32 +  "5 3     10      0      0\n"
    1.33 +  "5 6     80      0   1000\n"
    1.34 +  "6 7     30      0  -1000\n"
    1.35 +  "7 5   -120      0      0\n";
    1.36 +  
    1.37 +char test_neg2_lgf[] =
    1.38 +  "@nodes\n"
    1.39 +  "label   sup\n"
    1.40 +  "    1   100\n"
    1.41 +  "    2  -300\n"
    1.42 +  "@arcs\n"
    1.43 +  "      cost\n"
    1.44 +  "1 2     -1\n";
    1.45 +
    1.46 +
    1.47 +// Test data
    1.48 +typedef ListDigraph Digraph;
    1.49 +DIGRAPH_TYPEDEFS(ListDigraph);
    1.50 +
    1.51 +Digraph gr;
    1.52 +Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
    1.53 +Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
    1.54 +ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    1.55 +Node v, w;
    1.56 +
    1.57 +Digraph neg1_gr;
    1.58 +Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
    1.59 +ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
    1.60 +Digraph::NodeMap<int> neg1_s(neg1_gr);
    1.61 +
    1.62 +Digraph neg2_gr;
    1.63 +Digraph::ArcMap<int> neg2_c(neg2_gr);
    1.64 +ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
    1.65 +Digraph::NodeMap<int> neg2_s(neg2_gr);
    1.66 +
    1.67  
    1.68  enum SupplyType {
    1.69    EQ,
    1.70 @@ -83,6 +136,7 @@
    1.71    LEQ
    1.72  };
    1.73  
    1.74 +
    1.75  // Check the interface of an MCF algorithm
    1.76  template <typename GR, typename Value, typename Cost>
    1.77  class McfClassConcept
    1.78 @@ -268,30 +322,99 @@
    1.79    }
    1.80  }
    1.81  
    1.82 +template < typename MCF, typename Param >
    1.83 +void runMcfGeqTests( Param param,
    1.84 +                     const std::string &test_str = "",
    1.85 +                     bool full_neg_cost_support = false )
    1.86 +{
    1.87 +  MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
    1.88 +  
    1.89 +  // Basic tests
    1.90 +  mcf1.upperMap(u).costMap(c).supplyMap(s1);
    1.91 +  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,
    1.92 +           mcf1.OPTIMAL, true,     5240, test_str + "-1");
    1.93 +  mcf1.stSupply(v, w, 27);
    1.94 +  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2,
    1.95 +           mcf1.OPTIMAL, true,     7620, test_str + "-2");
    1.96 +  mcf1.lowerMap(l2).supplyMap(s1);
    1.97 +  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1,
    1.98 +           mcf1.OPTIMAL, true,     5970, test_str + "-3");
    1.99 +  mcf1.stSupply(v, w, 27);
   1.100 +  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
   1.101 +           mcf1.OPTIMAL, true,     8010, test_str + "-4");
   1.102 +  mcf1.reset().supplyMap(s1);
   1.103 +  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
   1.104 +           mcf1.OPTIMAL, true,       74, test_str + "-5");
   1.105 +  mcf1.lowerMap(l2).stSupply(v, w, 27);
   1.106 +  checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2,
   1.107 +           mcf1.OPTIMAL, true,       94, test_str + "-6");
   1.108 +  mcf1.reset();
   1.109 +  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3,
   1.110 +           mcf1.OPTIMAL, true,        0, test_str + "-7");
   1.111 +  mcf1.lowerMap(l2).upperMap(u);
   1.112 +  checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3,
   1.113 +           mcf1.INFEASIBLE, false,    0, test_str + "-8");
   1.114 +  mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
   1.115 +  checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4,
   1.116 +           mcf1.OPTIMAL, true,     6360, test_str + "-9");
   1.117 +
   1.118 +  // Tests for the GEQ form
   1.119 +  mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
   1.120 +  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
   1.121 +           mcf1.OPTIMAL, true,     3530, test_str + "-10", GEQ);
   1.122 +  mcf1.lowerMap(l2);
   1.123 +  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
   1.124 +           mcf1.OPTIMAL, true,     4540, test_str + "-11", GEQ);
   1.125 +  mcf1.supplyMap(s6);
   1.126 +  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
   1.127 +           mcf1.INFEASIBLE, false,    0, test_str + "-12", GEQ);
   1.128 +
   1.129 +  // Tests with negative costs
   1.130 +  mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s);
   1.131 +  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s,
   1.132 +           mcf2.UNBOUNDED, false,     0, test_str + "-13");
   1.133 +  mcf2.upperMap(neg1_u2);
   1.134 +  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
   1.135 +           mcf2.OPTIMAL, true,   -40000, test_str + "-14");
   1.136 +  mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
   1.137 +  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
   1.138 +           mcf2.UNBOUNDED, false,     0, test_str + "-15");
   1.139 +
   1.140 +  mcf3.costMap(neg2_c).supplyMap(neg2_s);
   1.141 +  if (full_neg_cost_support) {
   1.142 +    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
   1.143 +             mcf3.OPTIMAL, true,   -300, test_str + "-16", GEQ);
   1.144 +  } else {
   1.145 +    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
   1.146 +             mcf3.UNBOUNDED, false,   0, test_str + "-17", GEQ);
   1.147 +  }
   1.148 +  mcf3.upperMap(neg2_u);
   1.149 +  checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
   1.150 +           mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ);
   1.151 +}
   1.152 +
   1.153 +template < typename MCF, typename Param >
   1.154 +void runMcfLeqTests( Param param,
   1.155 +                     const std::string &test_str = "" )
   1.156 +{
   1.157 +  // Tests for the LEQ form
   1.158 +  MCF mcf1(gr);
   1.159 +  mcf1.supplyType(mcf1.LEQ);
   1.160 +  mcf1.upperMap(u).costMap(c).supplyMap(s6);
   1.161 +  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6,
   1.162 +           mcf1.OPTIMAL, true,   5080, test_str + "-19", LEQ);
   1.163 +  mcf1.lowerMap(l2);
   1.164 +  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
   1.165 +           mcf1.OPTIMAL, true,   5930, test_str + "-20", LEQ);
   1.166 +  mcf1.supplyMap(s5);
   1.167 +  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
   1.168 +           mcf1.INFEASIBLE, false,  0, test_str + "-21", LEQ);
   1.169 +}
   1.170 +
   1.171 +
   1.172  int main()
   1.173  {
   1.174 -  // Check the interfaces
   1.175 -  {
   1.176 -    typedef concepts::Digraph GR;
   1.177 -    checkConcept< McfClassConcept<GR, int, int>,
   1.178 -                  NetworkSimplex<GR> >();
   1.179 -    checkConcept< McfClassConcept<GR, double, double>,
   1.180 -                  NetworkSimplex<GR, double> >();
   1.181 -    checkConcept< McfClassConcept<GR, int, double>,
   1.182 -                  NetworkSimplex<GR, int, double> >();
   1.183 -  }
   1.184 -
   1.185 -  // Run various MCF tests
   1.186 -  typedef ListDigraph Digraph;
   1.187 -  DIGRAPH_TYPEDEFS(ListDigraph);
   1.188 -
   1.189 -  // Read the test digraph
   1.190 -  Digraph gr;
   1.191 -  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
   1.192 -  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
   1.193 -  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
   1.194 -  Node v, w;
   1.195 -
   1.196 +  // Read the test networks
   1.197    std::istringstream input(test_lgf);
   1.198    DigraphReader<Digraph>(gr, input)
   1.199      .arcMap("cost", c)
   1.200 @@ -309,141 +432,44 @@
   1.201      .node("target", w)
   1.202      .run();
   1.203    
   1.204 -  // Build test digraphs with negative costs
   1.205 -  Digraph neg_gr;
   1.206 -  Node n1 = neg_gr.addNode();
   1.207 -  Node n2 = neg_gr.addNode();
   1.208 -  Node n3 = neg_gr.addNode();
   1.209 -  Node n4 = neg_gr.addNode();
   1.210 -  Node n5 = neg_gr.addNode();
   1.211 -  Node n6 = neg_gr.addNode();
   1.212 -  Node n7 = neg_gr.addNode();
   1.213 +  std::istringstream neg_inp1(test_neg1_lgf);
   1.214 +  DigraphReader<Digraph>(neg1_gr, neg_inp1)
   1.215 +    .arcMap("cost", neg1_c)
   1.216 +    .arcMap("low1", neg1_l1)
   1.217 +    .arcMap("low2", neg1_l2)
   1.218 +    .nodeMap("sup", neg1_s)
   1.219 +    .run();
   1.220    
   1.221 -  Arc a1 = neg_gr.addArc(n1, n2);
   1.222 -  Arc a2 = neg_gr.addArc(n1, n3);
   1.223 -  Arc a3 = neg_gr.addArc(n2, n4);
   1.224 -  Arc a4 = neg_gr.addArc(n3, n4);
   1.225 -  Arc a5 = neg_gr.addArc(n3, n2);
   1.226 -  Arc a6 = neg_gr.addArc(n5, n3);
   1.227 -  Arc a7 = neg_gr.addArc(n5, n6);
   1.228 -  Arc a8 = neg_gr.addArc(n6, n7);
   1.229 -  Arc a9 = neg_gr.addArc(n7, n5);
   1.230 +  std::istringstream neg_inp2(test_neg2_lgf);
   1.231 +  DigraphReader<Digraph>(neg2_gr, neg_inp2)
   1.232 +    .arcMap("cost", neg2_c)
   1.233 +    .nodeMap("sup", neg2_s)
   1.234 +    .run();
   1.235    
   1.236 -  Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
   1.237 -  ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
   1.238 -  Digraph::NodeMap<int> neg_s(neg_gr, 0);
   1.239 -  
   1.240 -  neg_l2[a7] =  1000;
   1.241 -  neg_l2[a8] = -1000;
   1.242 -  
   1.243 -  neg_s[n1] =  100;
   1.244 -  neg_s[n4] = -100;
   1.245 -  
   1.246 -  neg_c[a1] =  100;
   1.247 -  neg_c[a2] =   30;
   1.248 -  neg_c[a3] =   20;
   1.249 -  neg_c[a4] =   80;
   1.250 -  neg_c[a5] =   50;
   1.251 -  neg_c[a6] =   10;
   1.252 -  neg_c[a7] =   80;
   1.253 -  neg_c[a8] =   30;
   1.254 -  neg_c[a9] = -120;
   1.255 -
   1.256 -  Digraph negs_gr;
   1.257 -  Digraph::NodeMap<int> negs_s(negs_gr);
   1.258 -  Digraph::ArcMap<int> negs_c(negs_gr);
   1.259 -  ConstMap<Arc, int> negs_l(0), negs_u(1000);
   1.260 -  n1 = negs_gr.addNode();
   1.261 -  n2 = negs_gr.addNode();
   1.262 -  negs_s[n1] = 100;
   1.263 -  negs_s[n2] = -300;
   1.264 -  negs_c[negs_gr.addArc(n1, n2)] = -1;
   1.265 -
   1.266 -
   1.267 -  // A. Test NetworkSimplex with the default pivot rule
   1.268 +  // Check the interface of NetworkSimplex
   1.269    {
   1.270 -    NetworkSimplex<Digraph> mcf(gr);
   1.271 -
   1.272 -    // Check the equality form
   1.273 -    mcf.upperMap(u).costMap(c);
   1.274 -    checkMcf(mcf, mcf.supplyMap(s1).run(),
   1.275 -             gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
   1.276 -    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
   1.277 -             gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
   1.278 -    mcf.lowerMap(l2);
   1.279 -    checkMcf(mcf, mcf.supplyMap(s1).run(),
   1.280 -             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
   1.281 -    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
   1.282 -             gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
   1.283 -    mcf.reset();
   1.284 -    checkMcf(mcf, mcf.supplyMap(s1).run(),
   1.285 -             gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
   1.286 -    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
   1.287 -             gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
   1.288 -    mcf.reset();
   1.289 -    checkMcf(mcf, mcf.run(),
   1.290 -             gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
   1.291 -    checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
   1.292 -             gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
   1.293 -    mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
   1.294 -    checkMcf(mcf, mcf.run(),
   1.295 -             gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
   1.296 -
   1.297 -    // Check the GEQ form
   1.298 -    mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
   1.299 -    checkMcf(mcf, mcf.run(),
   1.300 -             gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
   1.301 -    mcf.supplyType(mcf.GEQ);
   1.302 -    checkMcf(mcf, mcf.lowerMap(l2).run(),
   1.303 -             gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
   1.304 -    mcf.supplyMap(s6);
   1.305 -    checkMcf(mcf, mcf.run(),
   1.306 -             gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
   1.307 -
   1.308 -    // Check the LEQ form
   1.309 -    mcf.reset().supplyType(mcf.LEQ);
   1.310 -    mcf.upperMap(u).costMap(c).supplyMap(s6);
   1.311 -    checkMcf(mcf, mcf.run(),
   1.312 -             gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
   1.313 -    checkMcf(mcf, mcf.lowerMap(l2).run(),
   1.314 -             gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
   1.315 -    mcf.supplyMap(s5);
   1.316 -    checkMcf(mcf, mcf.run(),
   1.317 -             gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
   1.318 -
   1.319 -    // Check negative costs
   1.320 -    NetworkSimplex<Digraph> neg_mcf(neg_gr);
   1.321 -    neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
   1.322 -    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
   1.323 -      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");
   1.324 -    neg_mcf.upperMap(neg_u2);
   1.325 -    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
   1.326 -      neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");
   1.327 -    neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
   1.328 -    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
   1.329 -      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
   1.330 -      
   1.331 -    NetworkSimplex<Digraph> negs_mcf(negs_gr);
   1.332 -    negs_mcf.costMap(negs_c).supplyMap(negs_s);
   1.333 -    checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
   1.334 -      negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
   1.335 +    typedef concepts::Digraph GR;
   1.336 +    checkConcept< McfClassConcept<GR, int, int>,
   1.337 +                  NetworkSimplex<GR> >();
   1.338 +    checkConcept< McfClassConcept<GR, double, double>,
   1.339 +                  NetworkSimplex<GR, double> >();
   1.340 +    checkConcept< McfClassConcept<GR, int, double>,
   1.341 +                  NetworkSimplex<GR, int, double> >();
   1.342    }
   1.343  
   1.344 -  // B. Test NetworkSimplex with each pivot rule
   1.345 -  {
   1.346 -    NetworkSimplex<Digraph> mcf(gr);
   1.347 -    mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
   1.348 -
   1.349 -    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
   1.350 -             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
   1.351 -    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
   1.352 -             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
   1.353 -    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
   1.354 -             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
   1.355 -    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
   1.356 -             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
   1.357 -    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
   1.358 -             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
   1.359 +  // Test NetworkSimplex
   1.360 +  { 
   1.361 +    typedef NetworkSimplex<Digraph> MCF;
   1.362 +    runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
   1.363 +    runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
   1.364 +    runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE", true);
   1.365 +    runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE");
   1.366 +    runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS", true);
   1.367 +    runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS");
   1.368 +    runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
   1.369 +    runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
   1.370 +    runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
   1.371 +    runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
   1.372    }
   1.373  
   1.374    return 0;