1.1 --- a/test/min_cost_flow_test.cc Fri Apr 03 18:59:15 2009 +0200
1.2 +++ b/test/min_cost_flow_test.cc Fri Apr 17 18:04:36 2009 +0200
1.3 @@ -33,19 +33,19 @@
1.4
1.5 char test_lgf[] =
1.6 "@nodes\n"
1.7 - "label sup1 sup2 sup3\n"
1.8 - " 1 20 27 0\n"
1.9 - " 2 -4 0 0\n"
1.10 - " 3 0 0 0\n"
1.11 - " 4 0 0 0\n"
1.12 - " 5 9 0 0\n"
1.13 - " 6 -6 0 0\n"
1.14 - " 7 0 0 0\n"
1.15 - " 8 0 0 0\n"
1.16 - " 9 3 0 0\n"
1.17 - " 10 -2 0 0\n"
1.18 - " 11 0 0 0\n"
1.19 - " 12 -20 -27 0\n"
1.20 + "label sup1 sup2 sup3 sup4 sup5\n"
1.21 + " 1 20 27 0 20 30\n"
1.22 + " 2 -4 0 0 -8 -3\n"
1.23 + " 3 0 0 0 0 0\n"
1.24 + " 4 0 0 0 0 0\n"
1.25 + " 5 9 0 0 6 11\n"
1.26 + " 6 -6 0 0 -5 -6\n"
1.27 + " 7 0 0 0 0 0\n"
1.28 + " 8 0 0 0 0 3\n"
1.29 + " 9 3 0 0 0 0\n"
1.30 + " 10 -2 0 0 -7 -2\n"
1.31 + " 11 0 0 0 -10 0\n"
1.32 + " 12 -20 -27 0 -30 -20\n"
1.33 "\n"
1.34 "@arcs\n"
1.35 " cost cap low1 low2\n"
1.36 @@ -76,6 +76,12 @@
1.37 "target 12\n";
1.38
1.39
1.40 +enum ProblemType {
1.41 + EQ,
1.42 + GEQ,
1.43 + LEQ
1.44 +};
1.45 +
1.46 // Check the interface of an MCF algorithm
1.47 template <typename GR, typename Flow, typename Cost>
1.48 class McfClassConcept
1.49 @@ -97,17 +103,19 @@
1.50 .costMap(cost)
1.51 .supplyMap(sup)
1.52 .stSupply(n, n, k)
1.53 + .flowMap(flow)
1.54 + .potentialMap(pot)
1.55 .run();
1.56 +
1.57 + const MCF& const_mcf = mcf;
1.58
1.59 - const typename MCF::FlowMap &fm = mcf.flowMap();
1.60 - const typename MCF::PotentialMap &pm = mcf.potentialMap();
1.61 + const typename MCF::FlowMap &fm = const_mcf.flowMap();
1.62 + const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
1.63
1.64 - v = mcf.totalCost();
1.65 - double x = mcf.template totalCost<double>();
1.66 - v = mcf.flow(a);
1.67 - v = mcf.potential(n);
1.68 - mcf.flowMap(flow);
1.69 - mcf.potentialMap(pot);
1.70 + v = const_mcf.totalCost();
1.71 + double x = const_mcf.template totalCost<double>();
1.72 + v = const_mcf.flow(a);
1.73 + v = const_mcf.potential(n);
1.74
1.75 ignore_unused_variable_warning(fm);
1.76 ignore_unused_variable_warning(pm);
1.77 @@ -142,7 +150,8 @@
1.78 template < typename GR, typename LM, typename UM,
1.79 typename SM, typename FM >
1.80 bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
1.81 - const SM& supply, const FM& flow )
1.82 + const SM& supply, const FM& flow,
1.83 + ProblemType type = EQ )
1.84 {
1.85 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.86
1.87 @@ -156,7 +165,10 @@
1.88 sum += flow[e];
1.89 for (InArcIt e(gr, n); e != INVALID; ++e)
1.90 sum -= flow[e];
1.91 - if (sum != supply[n]) return false;
1.92 + bool b = (type == EQ && sum == supply[n]) ||
1.93 + (type == GEQ && sum >= supply[n]) ||
1.94 + (type == LEQ && sum <= supply[n]);
1.95 + if (!b) return false;
1.96 }
1.97
1.98 return true;
1.99 @@ -165,9 +177,10 @@
1.100 // Check the feasibility of the given potentials (dual soluiton)
1.101 // using the "Complementary Slackness" optimality condition
1.102 template < typename GR, typename LM, typename UM,
1.103 - typename CM, typename FM, typename PM >
1.104 + typename CM, typename SM, typename FM, typename PM >
1.105 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
1.106 - const CM& cost, const FM& flow, const PM& pi )
1.107 + const CM& cost, const SM& supply, const FM& flow,
1.108 + const PM& pi )
1.109 {
1.110 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.111
1.112 @@ -179,6 +192,16 @@
1.113 (red_cost > 0 && flow[e] == lower[e]) ||
1.114 (red_cost < 0 && flow[e] == upper[e]);
1.115 }
1.116 +
1.117 + for (NodeIt n(gr); opt && n != INVALID; ++n) {
1.118 + typename SM::Value sum = 0;
1.119 + for (OutArcIt e(gr, n); e != INVALID; ++e)
1.120 + sum += flow[e];
1.121 + for (InArcIt e(gr, n); e != INVALID; ++e)
1.122 + sum -= flow[e];
1.123 + opt = (sum == supply[n]) || (pi[n] == 0);
1.124 + }
1.125 +
1.126 return opt;
1.127 }
1.128
1.129 @@ -190,14 +213,15 @@
1.130 const GR& gr, const LM& lower, const UM& upper,
1.131 const CM& cost, const SM& supply,
1.132 bool result, typename CM::Value total,
1.133 - const std::string &test_id = "" )
1.134 + const std::string &test_id = "",
1.135 + ProblemType type = EQ )
1.136 {
1.137 check(mcf_result == result, "Wrong result " + test_id);
1.138 if (result) {
1.139 - check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
1.140 + check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
1.141 "The flow is not feasible " + test_id);
1.142 check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
1.143 - check(checkPotential(gr, lower, upper, cost, mcf.flowMap(),
1.144 + check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(),
1.145 mcf.potentialMap()),
1.146 "Wrong potentials " + test_id);
1.147 }
1.148 @@ -226,7 +250,7 @@
1.149 // Read the test digraph
1.150 Digraph gr;
1.151 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
1.152 - Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
1.153 + Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
1.154 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
1.155 Node v, w;
1.156
1.157 @@ -239,6 +263,8 @@
1.158 .nodeMap("sup1", s1)
1.159 .nodeMap("sup2", s2)
1.160 .nodeMap("sup3", s3)
1.161 + .nodeMap("sup4", s4)
1.162 + .nodeMap("sup5", s5)
1.163 .node("source", v)
1.164 .node("target", w)
1.165 .run();
1.166 @@ -247,6 +273,7 @@
1.167 {
1.168 NetworkSimplex<Digraph> mcf(gr);
1.169
1.170 + // Check the equality form
1.171 mcf.upperMap(u).costMap(c);
1.172 checkMcf(mcf, mcf.supplyMap(s1).run(),
1.173 gr, l1, u, c, s1, true, 5240, "#A1");
1.174 @@ -267,6 +294,28 @@
1.175 gr, l1, cu, cc, s3, true, 0, "#A7");
1.176 checkMcf(mcf, mcf.boundMaps(l2, u).run(),
1.177 gr, l2, u, cc, s3, false, 0, "#A8");
1.178 +
1.179 + // Check the GEQ form
1.180 + mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
1.181 + checkMcf(mcf, mcf.run(),
1.182 + gr, l1, u, c, s4, true, 3530, "#A9", GEQ);
1.183 + mcf.problemType(mcf.GEQ);
1.184 + checkMcf(mcf, mcf.lowerMap(l2).run(),
1.185 + gr, l2, u, c, s4, true, 4540, "#A10", GEQ);
1.186 + mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
1.187 + checkMcf(mcf, mcf.run(),
1.188 + gr, l2, u, c, s5, false, 0, "#A11", GEQ);
1.189 +
1.190 + // Check the LEQ form
1.191 + mcf.reset().problemType(mcf.LEQ);
1.192 + mcf.upperMap(u).costMap(c).supplyMap(s5);
1.193 + checkMcf(mcf, mcf.run(),
1.194 + gr, l1, u, c, s5, true, 5080, "#A12", LEQ);
1.195 + checkMcf(mcf, mcf.lowerMap(l2).run(),
1.196 + gr, l2, u, c, s5, true, 5930, "#A13", LEQ);
1.197 + mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
1.198 + checkMcf(mcf, mcf.run(),
1.199 + gr, l2, u, c, s4, false, 0, "#A14", LEQ);
1.200 }
1.201
1.202 // B. Test NetworkSimplex with each pivot rule