1.1 --- a/test/min_cost_flow_test.cc Wed Apr 29 16:15:29 2009 +0100
1.2 +++ b/test/min_cost_flow_test.cc Wed Apr 29 19:22:14 2009 +0100
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,57 +34,57 @@
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 };
1.100
1.101 // Check the interface of an MCF algorithm
1.102 -template <typename GR, typename Flow, typename Cost>
1.103 +template <typename GR, typename Value, typename Cost>
1.104 class McfClassConcept
1.105 {
1.106 public:
1.107 @@ -94,53 +95,46 @@
1.108 checkConcept<concepts::Digraph, GR>();
1.109
1.110 MCF mcf(g);
1.111 + const MCF& const_mcf = mcf;
1.112
1.113 b = mcf.reset()
1.114 .lowerMap(lower)
1.115 .upperMap(upper)
1.116 - .capacityMap(upper)
1.117 - .boundMaps(lower, upper)
1.118 .costMap(cost)
1.119 .supplyMap(sup)
1.120 .stSupply(n, n, k)
1.121 - .flowMap(flow)
1.122 - .potentialMap(pot)
1.123 .run();
1.124 -
1.125 - const MCF& const_mcf = mcf;
1.126
1.127 - const typename MCF::FlowMap &fm = const_mcf.flowMap();
1.128 - const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
1.129 -
1.130 - v = const_mcf.totalCost();
1.131 - double x = const_mcf.template totalCost<double>();
1.132 + c = const_mcf.totalCost();
1.133 + x = const_mcf.template totalCost<double>();
1.134 v = const_mcf.flow(a);
1.135 - v = const_mcf.potential(n);
1.136 -
1.137 - ignore_unused_variable_warning(fm);
1.138 - ignore_unused_variable_warning(pm);
1.139 - ignore_unused_variable_warning(x);
1.140 + c = const_mcf.potential(n);
1.141 + const_mcf.flowMap(fm);
1.142 + const_mcf.potentialMap(pm);
1.143 }
1.144
1.145 typedef typename GR::Node Node;
1.146 typedef typename GR::Arc Arc;
1.147 - typedef concepts::ReadMap<Node, Flow> NM;
1.148 - typedef concepts::ReadMap<Arc, Flow> FAM;
1.149 + typedef concepts::ReadMap<Node, Value> NM;
1.150 + typedef concepts::ReadMap<Arc, Value> VAM;
1.151 typedef concepts::ReadMap<Arc, Cost> CAM;
1.152 + typedef concepts::WriteMap<Arc, Value> FlowMap;
1.153 + typedef concepts::WriteMap<Node, Cost> PotMap;
1.154
1.155 const GR &g;
1.156 - const FAM &lower;
1.157 - const FAM &upper;
1.158 + const VAM &lower;
1.159 + const VAM &upper;
1.160 const CAM &cost;
1.161 const NM ⊃
1.162 const Node &n;
1.163 const Arc &a;
1.164 - const Flow &k;
1.165 - Flow v;
1.166 + const Value &k;
1.167 + FlowMap fm;
1.168 + PotMap pm;
1.169 bool b;
1.170 -
1.171 - typename MCF::FlowMap &flow;
1.172 - typename MCF::PotentialMap &pot;
1.173 + double x;
1.174 + typename MCF::Value v;
1.175 + typename MCF::Cost c;
1.176 };
1.177
1.178 };
1.179 @@ -151,7 +145,7 @@
1.180 typename SM, typename FM >
1.181 bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
1.182 const SM& supply, const FM& flow,
1.183 - ProblemType type = EQ )
1.184 + SupplyType type = EQ )
1.185 {
1.186 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.187
1.188 @@ -208,21 +202,25 @@
1.189 // Run a minimum cost flow algorithm and check the results
1.190 template < typename MCF, typename GR,
1.191 typename LM, typename UM,
1.192 - typename CM, typename SM >
1.193 -void checkMcf( const MCF& mcf, bool mcf_result,
1.194 + typename CM, typename SM,
1.195 + typename PT >
1.196 +void checkMcf( const MCF& mcf, PT mcf_result,
1.197 const GR& gr, const LM& lower, const UM& upper,
1.198 const CM& cost, const SM& supply,
1.199 - bool result, typename CM::Value total,
1.200 + PT result, bool optimal, typename CM::Value total,
1.201 const std::string &test_id = "",
1.202 - ProblemType type = EQ )
1.203 + SupplyType type = EQ )
1.204 {
1.205 check(mcf_result == result, "Wrong result " + test_id);
1.206 - if (result) {
1.207 - check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
1.208 + if (optimal) {
1.209 + typename GR::template ArcMap<typename SM::Value> flow(gr);
1.210 + typename GR::template NodeMap<typename CM::Value> pi(gr);
1.211 + mcf.flowMap(flow);
1.212 + mcf.potentialMap(pi);
1.213 + check(checkFlow(gr, lower, upper, supply, flow, type),
1.214 "The flow is not feasible " + test_id);
1.215 check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
1.216 - check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(),
1.217 - mcf.potentialMap()),
1.218 + check(checkPotential(gr, lower, upper, cost, supply, flow, pi),
1.219 "Wrong potentials " + test_id);
1.220 }
1.221 }
1.222 @@ -231,11 +229,13 @@
1.223 {
1.224 // Check the interfaces
1.225 {
1.226 - typedef int Flow;
1.227 - typedef int Cost;
1.228 typedef concepts::Digraph GR;
1.229 - checkConcept< McfClassConcept<GR, Flow, Cost>,
1.230 - NetworkSimplex<GR, Flow, Cost> >();
1.231 + checkConcept< McfClassConcept<GR, int, int>,
1.232 + NetworkSimplex<GR> >();
1.233 + checkConcept< McfClassConcept<GR, double, double>,
1.234 + NetworkSimplex<GR, double> >();
1.235 + checkConcept< McfClassConcept<GR, int, double>,
1.236 + NetworkSimplex<GR, int, double> >();
1.237 }
1.238
1.239 // Run various MCF tests
1.240 @@ -244,8 +244,8 @@
1.241
1.242 // Read the test digraph
1.243 Digraph gr;
1.244 - Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
1.245 - Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
1.246 + Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
1.247 + Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
1.248 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
1.249 Node v, w;
1.250
1.251 @@ -255,14 +255,56 @@
1.252 .arcMap("cap", u)
1.253 .arcMap("low1", l1)
1.254 .arcMap("low2", l2)
1.255 + .arcMap("low3", l3)
1.256 .nodeMap("sup1", s1)
1.257 .nodeMap("sup2", s2)
1.258 .nodeMap("sup3", s3)
1.259 .nodeMap("sup4", s4)
1.260 .nodeMap("sup5", s5)
1.261 + .nodeMap("sup6", s6)
1.262 .node("source", v)
1.263 .node("target", w)
1.264 .run();
1.265 +
1.266 + // Build a test digraph for testing negative costs
1.267 + Digraph ngr;
1.268 + Node n1 = ngr.addNode();
1.269 + Node n2 = ngr.addNode();
1.270 + Node n3 = ngr.addNode();
1.271 + Node n4 = ngr.addNode();
1.272 + Node n5 = ngr.addNode();
1.273 + Node n6 = ngr.addNode();
1.274 + Node n7 = ngr.addNode();
1.275 +
1.276 + Arc a1 = ngr.addArc(n1, n2);
1.277 + Arc a2 = ngr.addArc(n1, n3);
1.278 + Arc a3 = ngr.addArc(n2, n4);
1.279 + Arc a4 = ngr.addArc(n3, n4);
1.280 + Arc a5 = ngr.addArc(n3, n2);
1.281 + Arc a6 = ngr.addArc(n5, n3);
1.282 + Arc a7 = ngr.addArc(n5, n6);
1.283 + Arc a8 = ngr.addArc(n6, n7);
1.284 + Arc a9 = ngr.addArc(n7, n5);
1.285 +
1.286 + Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
1.287 + ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
1.288 + Digraph::NodeMap<int> ns(ngr, 0);
1.289 +
1.290 + nl2[a7] = 1000;
1.291 + nl2[a8] = -1000;
1.292 +
1.293 + ns[n1] = 100;
1.294 + ns[n4] = -100;
1.295 +
1.296 + nc[a1] = 100;
1.297 + nc[a2] = 30;
1.298 + nc[a3] = 20;
1.299 + nc[a4] = 80;
1.300 + nc[a5] = 50;
1.301 + nc[a6] = 10;
1.302 + nc[a7] = 80;
1.303 + nc[a8] = 30;
1.304 + nc[a9] = -120;
1.305
1.306 // A. Test NetworkSimplex with the default pivot rule
1.307 {
1.308 @@ -271,63 +313,77 @@
1.309 // Check the equality form
1.310 mcf.upperMap(u).costMap(c);
1.311 checkMcf(mcf, mcf.supplyMap(s1).run(),
1.312 - gr, l1, u, c, s1, true, 5240, "#A1");
1.313 + gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1");
1.314 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
1.315 - gr, l1, u, c, s2, true, 7620, "#A2");
1.316 + gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2");
1.317 mcf.lowerMap(l2);
1.318 checkMcf(mcf, mcf.supplyMap(s1).run(),
1.319 - gr, l2, u, c, s1, true, 5970, "#A3");
1.320 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3");
1.321 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
1.322 - gr, l2, u, c, s2, true, 8010, "#A4");
1.323 + gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4");
1.324 mcf.reset();
1.325 checkMcf(mcf, mcf.supplyMap(s1).run(),
1.326 - gr, l1, cu, cc, s1, true, 74, "#A5");
1.327 + gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5");
1.328 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
1.329 - gr, l2, cu, cc, s2, true, 94, "#A6");
1.330 + gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6");
1.331 mcf.reset();
1.332 checkMcf(mcf, mcf.run(),
1.333 - gr, l1, cu, cc, s3, true, 0, "#A7");
1.334 - checkMcf(mcf, mcf.boundMaps(l2, u).run(),
1.335 - gr, l2, u, cc, s3, false, 0, "#A8");
1.336 + gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7");
1.337 + checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
1.338 + gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
1.339 + mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
1.340 + checkMcf(mcf, mcf.run(),
1.341 + gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9");
1.342
1.343 // Check the GEQ form
1.344 - mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
1.345 + mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
1.346 checkMcf(mcf, mcf.run(),
1.347 - gr, l1, u, c, s4, true, 3530, "#A9", GEQ);
1.348 - mcf.problemType(mcf.GEQ);
1.349 + gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ);
1.350 + mcf.supplyType(mcf.GEQ);
1.351 checkMcf(mcf, mcf.lowerMap(l2).run(),
1.352 - gr, l2, u, c, s4, true, 4540, "#A10", GEQ);
1.353 - mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
1.354 + gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ);
1.355 + mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
1.356 checkMcf(mcf, mcf.run(),
1.357 - gr, l2, u, c, s5, false, 0, "#A11", GEQ);
1.358 + gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ);
1.359
1.360 // Check the LEQ form
1.361 - mcf.reset().problemType(mcf.LEQ);
1.362 - mcf.upperMap(u).costMap(c).supplyMap(s5);
1.363 + mcf.reset().supplyType(mcf.LEQ);
1.364 + mcf.upperMap(u).costMap(c).supplyMap(s6);
1.365 checkMcf(mcf, mcf.run(),
1.366 - gr, l1, u, c, s5, true, 5080, "#A12", LEQ);
1.367 + gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ);
1.368 checkMcf(mcf, mcf.lowerMap(l2).run(),
1.369 - gr, l2, u, c, s5, true, 5930, "#A13", LEQ);
1.370 - mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
1.371 + gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ);
1.372 + mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
1.373 checkMcf(mcf, mcf.run(),
1.374 - gr, l2, u, c, s4, false, 0, "#A14", LEQ);
1.375 + gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ);
1.376 +
1.377 + // Check negative costs
1.378 + NetworkSimplex<Digraph> nmcf(ngr);
1.379 + nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
1.380 + checkMcf(nmcf, nmcf.run(),
1.381 + ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16");
1.382 + checkMcf(nmcf, nmcf.upperMap(nu2).run(),
1.383 + ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17");
1.384 + nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
1.385 + checkMcf(nmcf, nmcf.run(),
1.386 + ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18");
1.387 }
1.388
1.389 // B. Test NetworkSimplex with each pivot rule
1.390 {
1.391 NetworkSimplex<Digraph> mcf(gr);
1.392 - mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
1.393 + mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
1.394
1.395 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
1.396 - gr, l2, u, c, s1, true, 5970, "#B1");
1.397 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1");
1.398 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
1.399 - gr, l2, u, c, s1, true, 5970, "#B2");
1.400 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2");
1.401 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
1.402 - gr, l2, u, c, s1, true, 5970, "#B3");
1.403 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3");
1.404 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
1.405 - gr, l2, u, c, s1, true, 5970, "#B4");
1.406 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4");
1.407 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
1.408 - gr, l2, u, c, s1, true, 5970, "#B5");
1.409 + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5");
1.410 }
1.411
1.412 return 0;