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;