1.1 --- a/test/min_cost_flow_test.cc Sun Apr 26 16:36:23 2009 +0100
1.2 +++ b/test/min_cost_flow_test.cc Wed Apr 29 03:15:24 2009 +0200
1.3 @@ -18,6 +18,7 @@
1.4
1.5 #include <iostream>
1.6 #include <fstream>
1.7 +#include <limits>
1.8
1.9 #include <lemon/list_graph.h>
1.10 #include <lemon/lgf_reader.h>
1.11 @@ -33,50 +34,50 @@
1.12
1.13 char test_lgf[] =
1.14 "@nodes\n"
1.15 - "label sup1 sup2 sup3 sup4 sup5\n"
1.16 - " 1 20 27 0 20 30\n"
1.17 - " 2 -4 0 0 -8 -3\n"
1.18 - " 3 0 0 0 0 0\n"
1.19 - " 4 0 0 0 0 0\n"
1.20 - " 5 9 0 0 6 11\n"
1.21 - " 6 -6 0 0 -5 -6\n"
1.22 - " 7 0 0 0 0 0\n"
1.23 - " 8 0 0 0 0 3\n"
1.24 - " 9 3 0 0 0 0\n"
1.25 - " 10 -2 0 0 -7 -2\n"
1.26 - " 11 0 0 0 -10 0\n"
1.27 - " 12 -20 -27 0 -30 -20\n"
1.28 - "\n"
1.29 + "label sup1 sup2 sup3 sup4 sup5 sup6\n"
1.30 + " 1 20 27 0 30 20 30\n"
1.31 + " 2 -4 0 0 0 -8 -3\n"
1.32 + " 3 0 0 0 0 0 0\n"
1.33 + " 4 0 0 0 0 0 0\n"
1.34 + " 5 9 0 0 0 6 11\n"
1.35 + " 6 -6 0 0 0 -5 -6\n"
1.36 + " 7 0 0 0 0 0 0\n"
1.37 + " 8 0 0 0 0 0 3\n"
1.38 + " 9 3 0 0 0 0 0\n"
1.39 + " 10 -2 0 0 0 -7 -2\n"
1.40 + " 11 0 0 0 0 -10 0\n"
1.41 + " 12 -20 -27 0 -30 -30 -20\n"
1.42 + "\n"
1.43 "@arcs\n"
1.44 - " cost cap low1 low2\n"
1.45 - " 1 2 70 11 0 8\n"
1.46 - " 1 3 150 3 0 1\n"
1.47 - " 1 4 80 15 0 2\n"
1.48 - " 2 8 80 12 0 0\n"
1.49 - " 3 5 140 5 0 3\n"
1.50 - " 4 6 60 10 0 1\n"
1.51 - " 4 7 80 2 0 0\n"
1.52 - " 4 8 110 3 0 0\n"
1.53 - " 5 7 60 14 0 0\n"
1.54 - " 5 11 120 12 0 0\n"
1.55 - " 6 3 0 3 0 0\n"
1.56 - " 6 9 140 4 0 0\n"
1.57 - " 6 10 90 8 0 0\n"
1.58 - " 7 1 30 5 0 0\n"
1.59 - " 8 12 60 16 0 4\n"
1.60 - " 9 12 50 6 0 0\n"
1.61 - "10 12 70 13 0 5\n"
1.62 - "10 2 100 7 0 0\n"
1.63 - "10 7 60 10 0 0\n"
1.64 - "11 10 20 14 0 6\n"
1.65 - "12 11 30 10 0 0\n"
1.66 + " cost cap low1 low2 low3\n"
1.67 + " 1 2 70 11 0 8 8\n"
1.68 + " 1 3 150 3 0 1 0\n"
1.69 + " 1 4 80 15 0 2 2\n"
1.70 + " 2 8 80 12 0 0 0\n"
1.71 + " 3 5 140 5 0 3 1\n"
1.72 + " 4 6 60 10 0 1 0\n"
1.73 + " 4 7 80 2 0 0 0\n"
1.74 + " 4 8 110 3 0 0 0\n"
1.75 + " 5 7 60 14 0 0 0\n"
1.76 + " 5 11 120 12 0 0 0\n"
1.77 + " 6 3 0 3 0 0 0\n"
1.78 + " 6 9 140 4 0 0 0\n"
1.79 + " 6 10 90 8 0 0 0\n"
1.80 + " 7 1 30 5 0 0 -5\n"
1.81 + " 8 12 60 16 0 4 3\n"
1.82 + " 9 12 50 6 0 0 0\n"
1.83 + "10 12 70 13 0 5 2\n"
1.84 + "10 2 100 7 0 0 0\n"
1.85 + "10 7 60 10 0 0 -3\n"
1.86 + "11 10 20 14 0 6 -20\n"
1.87 + "12 11 30 10 0 0 -10\n"
1.88 "\n"
1.89 "@attributes\n"
1.90 "source 1\n"
1.91 "target 12\n";
1.92
1.93
1.94 -enum ProblemType {
1.95 +enum SupplyType {
1.96 EQ,
1.97 GEQ,
1.98 LEQ
1.99 @@ -98,8 +99,6 @@
1.100 b = mcf.reset()
1.101 .lowerMap(lower)
1.102 .upperMap(upper)
1.103 - .capacityMap(upper)
1.104 - .boundMaps(lower, upper)
1.105 .costMap(cost)
1.106 .supplyMap(sup)
1.107 .stSupply(n, n, k)
1.108 @@ -112,10 +111,12 @@
1.109 const typename MCF::FlowMap &fm = const_mcf.flowMap();
1.110 const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
1.111
1.112 - v = const_mcf.totalCost();
1.113 + c = const_mcf.totalCost();
1.114 double x = const_mcf.template totalCost<double>();
1.115 v = const_mcf.flow(a);
1.116 - v = const_mcf.potential(n);
1.117 + c = const_mcf.potential(n);
1.118 +
1.119 + v = const_mcf.INF;
1.120
1.121 ignore_unused_variable_warning(fm);
1.122 ignore_unused_variable_warning(pm);
1.123 @@ -137,6 +138,7 @@
1.124 const Arc &a;
1.125 const Flow &k;
1.126 Flow v;
1.127 + Cost c;
1.128 bool b;
1.129
1.130 typename MCF::FlowMap &flow;
1.131 @@ -151,7 +153,7 @@
1.132 typename SM, typename FM >
1.133 bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
1.134 const SM& supply, const FM& flow,
1.135 - ProblemType type = EQ )
1.136 + SupplyType type = EQ )
1.137 {
1.138 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.139
1.140 @@ -208,16 +210,17 @@
1.141 // Run a minimum cost flow algorithm and check the results
1.142 template < typename MCF, typename GR,
1.143 typename LM, typename UM,
1.144 - typename CM, typename SM >
1.145 -void checkMcf( const MCF& mcf, bool mcf_result,
1.146 + typename CM, typename SM,
1.147 + typename PT >
1.148 +void checkMcf( const MCF& mcf, PT mcf_result,
1.149 const GR& gr, const LM& lower, const UM& upper,
1.150 const CM& cost, const SM& supply,
1.151 - bool result, typename CM::Value total,
1.152 + PT result, bool optimal, typename CM::Value total,
1.153 const std::string &test_id = "",
1.154 - ProblemType type = EQ )
1.155 + SupplyType type = EQ )
1.156 {
1.157 check(mcf_result == result, "Wrong result " + test_id);
1.158 - if (result) {
1.159 + if (optimal) {
1.160 check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
1.161 "The flow is not feasible " + test_id);
1.162 check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
1.163 @@ -244,8 +247,8 @@
1.164
1.165 // Read the test digraph
1.166 Digraph gr;
1.167 - Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
1.168 - Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
1.169 + Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
1.170 + Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
1.171 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
1.172 Node v, w;
1.173
1.174 @@ -255,14 +258,56 @@
1.175 .arcMap("cap", u)
1.176 .arcMap("low1", l1)
1.177 .arcMap("low2", l2)
1.178 + .arcMap("low3", l3)
1.179 .nodeMap("sup1", s1)
1.180 .nodeMap("sup2", s2)
1.181 .nodeMap("sup3", s3)
1.182 .nodeMap("sup4", s4)
1.183 .nodeMap("sup5", s5)
1.184 + .nodeMap("sup6", s6)
1.185 .node("source", v)
1.186 .node("target", w)
1.187 .run();
1.188 +
1.189 + // Build a test digraph for testing negative costs
1.190 + Digraph ngr;
1.191 + Node n1 = ngr.addNode();
1.192 + Node n2 = ngr.addNode();
1.193 + Node n3 = ngr.addNode();
1.194 + Node n4 = ngr.addNode();
1.195 + Node n5 = ngr.addNode();
1.196 + Node n6 = ngr.addNode();
1.197 + Node n7 = ngr.addNode();
1.198 +
1.199 + Arc a1 = ngr.addArc(n1, n2);
1.200 + Arc a2 = ngr.addArc(n1, n3);
1.201 + Arc a3 = ngr.addArc(n2, n4);
1.202 + Arc a4 = ngr.addArc(n3, n4);
1.203 + Arc a5 = ngr.addArc(n3, n2);
1.204 + Arc a6 = ngr.addArc(n5, n3);
1.205 + Arc a7 = ngr.addArc(n5, n6);
1.206 + Arc a8 = ngr.addArc(n6, n7);
1.207 + Arc a9 = ngr.addArc(n7, n5);
1.208 +
1.209 + Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
1.210 + ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
1.211 + Digraph::NodeMap<int> ns(ngr, 0);
1.212 +
1.213 + nl2[a7] = 1000;
1.214 + nl2[a8] = -1000;
1.215 +
1.216 + ns[n1] = 100;
1.217 + ns[n4] = -100;
1.218 +
1.219 + nc[a1] = 100;
1.220 + nc[a2] = 30;
1.221 + nc[a3] = 20;
1.222 + nc[a4] = 80;
1.223 + nc[a5] = 50;
1.224 + nc[a6] = 10;
1.225 + nc[a7] = 80;
1.226 + nc[a8] = 30;
1.227 + nc[a9] = -120;
1.228
1.229 // A. Test NetworkSimplex with the default pivot rule
1.230 {
1.231 @@ -271,63 +316,77 @@
1.232 // Check the equality form
1.233 mcf.upperMap(u).costMap(c);
1.234 checkMcf(mcf, mcf.supplyMap(s1).run(),
1.235 - gr, l1, u, c, s1, true, 5240, "#A1");
1.236 + gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1");
1.237 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
1.238 - gr, l1, u, c, s2, true, 7620, "#A2");
1.239 + gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2");
1.240 mcf.lowerMap(l2);
1.241 checkMcf(mcf, mcf.supplyMap(s1).run(),
1.242 - gr, l2, u, c, s1, true, 5970, "#A3");
1.243 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3");
1.244 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
1.245 - gr, l2, u, c, s2, true, 8010, "#A4");
1.246 + gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4");
1.247 mcf.reset();
1.248 checkMcf(mcf, mcf.supplyMap(s1).run(),
1.249 - gr, l1, cu, cc, s1, true, 74, "#A5");
1.250 + gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5");
1.251 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
1.252 - gr, l2, cu, cc, s2, true, 94, "#A6");
1.253 + gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6");
1.254 mcf.reset();
1.255 checkMcf(mcf, mcf.run(),
1.256 - gr, l1, cu, cc, s3, true, 0, "#A7");
1.257 - checkMcf(mcf, mcf.boundMaps(l2, u).run(),
1.258 - gr, l2, u, cc, s3, false, 0, "#A8");
1.259 + gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7");
1.260 + checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
1.261 + gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
1.262 + mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
1.263 + checkMcf(mcf, mcf.run(),
1.264 + gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9");
1.265
1.266 // Check the GEQ form
1.267 - mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
1.268 + mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
1.269 checkMcf(mcf, mcf.run(),
1.270 - gr, l1, u, c, s4, true, 3530, "#A9", GEQ);
1.271 - mcf.problemType(mcf.GEQ);
1.272 + gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ);
1.273 + mcf.supplyType(mcf.GEQ);
1.274 checkMcf(mcf, mcf.lowerMap(l2).run(),
1.275 - gr, l2, u, c, s4, true, 4540, "#A10", GEQ);
1.276 - mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
1.277 + gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ);
1.278 + mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
1.279 checkMcf(mcf, mcf.run(),
1.280 - gr, l2, u, c, s5, false, 0, "#A11", GEQ);
1.281 + gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ);
1.282
1.283 // Check the LEQ form
1.284 - mcf.reset().problemType(mcf.LEQ);
1.285 - mcf.upperMap(u).costMap(c).supplyMap(s5);
1.286 + mcf.reset().supplyType(mcf.LEQ);
1.287 + mcf.upperMap(u).costMap(c).supplyMap(s6);
1.288 checkMcf(mcf, mcf.run(),
1.289 - gr, l1, u, c, s5, true, 5080, "#A12", LEQ);
1.290 + gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ);
1.291 checkMcf(mcf, mcf.lowerMap(l2).run(),
1.292 - gr, l2, u, c, s5, true, 5930, "#A13", LEQ);
1.293 - mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
1.294 + gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ);
1.295 + mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
1.296 checkMcf(mcf, mcf.run(),
1.297 - gr, l2, u, c, s4, false, 0, "#A14", LEQ);
1.298 + gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ);
1.299 +
1.300 + // Check negative costs
1.301 + NetworkSimplex<Digraph> nmcf(ngr);
1.302 + nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
1.303 + checkMcf(nmcf, nmcf.run(),
1.304 + ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16");
1.305 + checkMcf(nmcf, nmcf.upperMap(nu2).run(),
1.306 + ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17");
1.307 + nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
1.308 + checkMcf(nmcf, nmcf.run(),
1.309 + ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18");
1.310 }
1.311
1.312 // B. Test NetworkSimplex with each pivot rule
1.313 {
1.314 NetworkSimplex<Digraph> mcf(gr);
1.315 - mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
1.316 + mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
1.317
1.318 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
1.319 - gr, l2, u, c, s1, true, 5970, "#B1");
1.320 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1");
1.321 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
1.322 - gr, l2, u, c, s1, true, 5970, "#B2");
1.323 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2");
1.324 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
1.325 - gr, l2, u, c, s1, true, 5970, "#B3");
1.326 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3");
1.327 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
1.328 - gr, l2, u, c, s1, true, 5970, "#B4");
1.329 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4");
1.330 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
1.331 - gr, l2, u, c, s1, true, 5970, "#B5");
1.332 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5");
1.333 }
1.334
1.335 return 0;