1.1 --- a/test/min_cost_flow_test.cc Tue Dec 20 17:44:38 2011 +0100
1.2 +++ b/test/min_cost_flow_test.cc Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -24,14 +24,19 @@
1.13 #include <lemon/lgf_reader.h>
1.14
1.15 #include <lemon/network_simplex.h>
1.16 +#include <lemon/capacity_scaling.h>
1.17 +#include <lemon/cost_scaling.h>
1.18 +#include <lemon/cycle_canceling.h>
1.19
1.20 #include <lemon/concepts/digraph.h>
1.21 +#include <lemon/concepts/heap.h>
1.22 #include <lemon/concept_check.h>
1.23
1.24 #include "test_tools.h"
1.25
1.26 using namespace lemon;
1.27
1.28 +// Test networks
1.29 char test_lgf[] =
1.30 "@nodes\n"
1.31 "label sup1 sup2 sup3 sup4 sup5 sup6\n"
1.32 @@ -47,7 +52,7 @@
1.33 " 10 -2 0 0 0 -7 -2\n"
1.34 " 11 0 0 0 0 -10 0\n"
1.35 " 12 -20 -27 0 -30 -30 -20\n"
1.36 - "\n"
1.37 + "\n"
1.38 "@arcs\n"
1.39 " cost cap low1 low2 low3\n"
1.40 " 1 2 70 11 0 8 8\n"
1.41 @@ -76,6 +81,58 @@
1.42 "source 1\n"
1.43 "target 12\n";
1.44
1.45 +char test_neg1_lgf[] =
1.46 + "@nodes\n"
1.47 + "label sup\n"
1.48 + " 1 100\n"
1.49 + " 2 0\n"
1.50 + " 3 0\n"
1.51 + " 4 -100\n"
1.52 + " 5 0\n"
1.53 + " 6 0\n"
1.54 + " 7 0\n"
1.55 + "@arcs\n"
1.56 + " cost low1 low2\n"
1.57 + "1 2 100 0 0\n"
1.58 + "1 3 30 0 0\n"
1.59 + "2 4 20 0 0\n"
1.60 + "3 4 80 0 0\n"
1.61 + "3 2 50 0 0\n"
1.62 + "5 3 10 0 0\n"
1.63 + "5 6 80 0 1000\n"
1.64 + "6 7 30 0 -1000\n"
1.65 + "7 5 -120 0 0\n";
1.66 +
1.67 +char test_neg2_lgf[] =
1.68 + "@nodes\n"
1.69 + "label sup\n"
1.70 + " 1 100\n"
1.71 + " 2 -300\n"
1.72 + "@arcs\n"
1.73 + " cost\n"
1.74 + "1 2 -1\n";
1.75 +
1.76 +
1.77 +// Test data
1.78 +typedef ListDigraph Digraph;
1.79 +DIGRAPH_TYPEDEFS(ListDigraph);
1.80 +
1.81 +Digraph gr;
1.82 +Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
1.83 +Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
1.84 +ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
1.85 +Node v, w;
1.86 +
1.87 +Digraph neg1_gr;
1.88 +Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
1.89 +ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
1.90 +Digraph::NodeMap<int> neg1_s(neg1_gr);
1.91 +
1.92 +Digraph neg2_gr;
1.93 +Digraph::ArcMap<int> neg2_c(neg2_gr);
1.94 +ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
1.95 +Digraph::NodeMap<int> neg2_s(neg2_gr);
1.96 +
1.97
1.98 enum SupplyType {
1.99 EQ,
1.100 @@ -83,6 +140,7 @@
1.101 LEQ
1.102 };
1.103
1.104 +
1.105 // Check the interface of an MCF algorithm
1.106 template <typename GR, typename Value, typename Cost>
1.107 class McfClassConcept
1.108 @@ -93,13 +151,13 @@
1.109 struct Constraints {
1.110 void constraints() {
1.111 checkConcept<concepts::Digraph, GR>();
1.112 -
1.113 +
1.114 const Constraints& me = *this;
1.115
1.116 MCF mcf(me.g);
1.117 const MCF& const_mcf = mcf;
1.118
1.119 - b = mcf.reset()
1.120 + b = mcf.reset().resetParams()
1.121 .lowerMap(me.lower)
1.122 .upperMap(me.upper)
1.123 .costMap(me.cost)
1.124 @@ -122,7 +180,7 @@
1.125 typedef concepts::ReadMap<Arc, Cost> CAM;
1.126 typedef concepts::WriteMap<Arc, Value> FlowMap;
1.127 typedef concepts::WriteMap<Node, Cost> PotMap;
1.128 -
1.129 +
1.130 GR g;
1.131 VAM lower;
1.132 VAM upper;
1.133 @@ -176,7 +234,7 @@
1.134 template < typename GR, typename LM, typename UM,
1.135 typename CM, typename SM, typename FM, typename PM >
1.136 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
1.137 - const CM& cost, const SM& supply, const FM& flow,
1.138 + const CM& cost, const SM& supply, const FM& flow,
1.139 const PM& pi, SupplyType type )
1.140 {
1.141 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.142 @@ -189,7 +247,7 @@
1.143 (red_cost > 0 && flow[e] == lower[e]) ||
1.144 (red_cost < 0 && flow[e] == upper[e]);
1.145 }
1.146 -
1.147 +
1.148 for (NodeIt n(gr); opt && n != INVALID; ++n) {
1.149 typename SM::Value sum = 0;
1.150 for (OutArcIt e(gr, n); e != INVALID; ++e)
1.151 @@ -202,7 +260,7 @@
1.152 opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
1.153 }
1.154 }
1.155 -
1.156 +
1.157 return opt;
1.158 }
1.159
1.160 @@ -227,7 +285,7 @@
1.161 red_supply[gr.target(a)] += lower[a];
1.162 }
1.163 }
1.164 -
1.165 +
1.166 for (NodeIt n(gr); n != INVALID; ++n) {
1.167 dual_cost -= red_supply[n] * pi[n];
1.168 }
1.169 @@ -236,7 +294,7 @@
1.170 cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
1.171 dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
1.172 }
1.173 -
1.174 +
1.175 return dual_cost == total;
1.176 }
1.177
1.178 @@ -268,30 +326,99 @@
1.179 }
1.180 }
1.181
1.182 +template < typename MCF, typename Param >
1.183 +void runMcfGeqTests( Param param,
1.184 + const std::string &test_str = "",
1.185 + bool full_neg_cost_support = false )
1.186 +{
1.187 + MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
1.188 +
1.189 + // Basic tests
1.190 + mcf1.upperMap(u).costMap(c).supplyMap(s1);
1.191 + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,
1.192 + mcf1.OPTIMAL, true, 5240, test_str + "-1");
1.193 + mcf1.stSupply(v, w, 27);
1.194 + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2,
1.195 + mcf1.OPTIMAL, true, 7620, test_str + "-2");
1.196 + mcf1.lowerMap(l2).supplyMap(s1);
1.197 + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1,
1.198 + mcf1.OPTIMAL, true, 5970, test_str + "-3");
1.199 + mcf1.stSupply(v, w, 27);
1.200 + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
1.201 + mcf1.OPTIMAL, true, 8010, test_str + "-4");
1.202 + mcf1.resetParams().supplyMap(s1);
1.203 + checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
1.204 + mcf1.OPTIMAL, true, 74, test_str + "-5");
1.205 + mcf1.lowerMap(l2).stSupply(v, w, 27);
1.206 + checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2,
1.207 + mcf1.OPTIMAL, true, 94, test_str + "-6");
1.208 + mcf1.reset();
1.209 + checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3,
1.210 + mcf1.OPTIMAL, true, 0, test_str + "-7");
1.211 + mcf1.lowerMap(l2).upperMap(u);
1.212 + checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3,
1.213 + mcf1.INFEASIBLE, false, 0, test_str + "-8");
1.214 + mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
1.215 + checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4,
1.216 + mcf1.OPTIMAL, true, 6360, test_str + "-9");
1.217 +
1.218 + // Tests for the GEQ form
1.219 + mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
1.220 + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
1.221 + mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ);
1.222 + mcf1.lowerMap(l2);
1.223 + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
1.224 + mcf1.OPTIMAL, true, 4540, test_str + "-11", GEQ);
1.225 + mcf1.supplyMap(s6);
1.226 + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
1.227 + mcf1.INFEASIBLE, false, 0, test_str + "-12", GEQ);
1.228 +
1.229 + // Tests with negative costs
1.230 + mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s);
1.231 + checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s,
1.232 + mcf2.UNBOUNDED, false, 0, test_str + "-13");
1.233 + mcf2.upperMap(neg1_u2);
1.234 + checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
1.235 + mcf2.OPTIMAL, true, -40000, test_str + "-14");
1.236 + mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
1.237 + checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
1.238 + mcf2.UNBOUNDED, false, 0, test_str + "-15");
1.239 +
1.240 + mcf3.costMap(neg2_c).supplyMap(neg2_s);
1.241 + if (full_neg_cost_support) {
1.242 + checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
1.243 + mcf3.OPTIMAL, true, -300, test_str + "-16", GEQ);
1.244 + } else {
1.245 + checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
1.246 + mcf3.UNBOUNDED, false, 0, test_str + "-17", GEQ);
1.247 + }
1.248 + mcf3.upperMap(neg2_u);
1.249 + checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
1.250 + mcf3.OPTIMAL, true, -300, test_str + "-18", GEQ);
1.251 +}
1.252 +
1.253 +template < typename MCF, typename Param >
1.254 +void runMcfLeqTests( Param param,
1.255 + const std::string &test_str = "" )
1.256 +{
1.257 + // Tests for the LEQ form
1.258 + MCF mcf1(gr);
1.259 + mcf1.supplyType(mcf1.LEQ);
1.260 + mcf1.upperMap(u).costMap(c).supplyMap(s6);
1.261 + checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6,
1.262 + mcf1.OPTIMAL, true, 5080, test_str + "-19", LEQ);
1.263 + mcf1.lowerMap(l2);
1.264 + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
1.265 + mcf1.OPTIMAL, true, 5930, test_str + "-20", LEQ);
1.266 + mcf1.supplyMap(s5);
1.267 + checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
1.268 + mcf1.INFEASIBLE, false, 0, test_str + "-21", LEQ);
1.269 +}
1.270 +
1.271 +
1.272 int main()
1.273 {
1.274 - // Check the interfaces
1.275 - {
1.276 - typedef concepts::Digraph GR;
1.277 - checkConcept< McfClassConcept<GR, int, int>,
1.278 - NetworkSimplex<GR> >();
1.279 - checkConcept< McfClassConcept<GR, double, double>,
1.280 - NetworkSimplex<GR, double> >();
1.281 - checkConcept< McfClassConcept<GR, int, double>,
1.282 - NetworkSimplex<GR, int, double> >();
1.283 - }
1.284 -
1.285 - // Run various MCF tests
1.286 - typedef ListDigraph Digraph;
1.287 - DIGRAPH_TYPEDEFS(ListDigraph);
1.288 -
1.289 - // Read the test digraph
1.290 - Digraph gr;
1.291 - Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
1.292 - Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
1.293 - ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
1.294 - Node v, w;
1.295 -
1.296 + // Read the test networks
1.297 std::istringstream input(test_lgf);
1.298 DigraphReader<Digraph>(gr, input)
1.299 .arcMap("cost", c)
1.300 @@ -308,142 +435,107 @@
1.301 .node("source", v)
1.302 .node("target", w)
1.303 .run();
1.304 -
1.305 - // Build test digraphs with negative costs
1.306 - Digraph neg_gr;
1.307 - Node n1 = neg_gr.addNode();
1.308 - Node n2 = neg_gr.addNode();
1.309 - Node n3 = neg_gr.addNode();
1.310 - Node n4 = neg_gr.addNode();
1.311 - Node n5 = neg_gr.addNode();
1.312 - Node n6 = neg_gr.addNode();
1.313 - Node n7 = neg_gr.addNode();
1.314 -
1.315 - Arc a1 = neg_gr.addArc(n1, n2);
1.316 - Arc a2 = neg_gr.addArc(n1, n3);
1.317 - Arc a3 = neg_gr.addArc(n2, n4);
1.318 - Arc a4 = neg_gr.addArc(n3, n4);
1.319 - Arc a5 = neg_gr.addArc(n3, n2);
1.320 - Arc a6 = neg_gr.addArc(n5, n3);
1.321 - Arc a7 = neg_gr.addArc(n5, n6);
1.322 - Arc a8 = neg_gr.addArc(n6, n7);
1.323 - Arc a9 = neg_gr.addArc(n7, n5);
1.324 -
1.325 - Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
1.326 - ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
1.327 - Digraph::NodeMap<int> neg_s(neg_gr, 0);
1.328 -
1.329 - neg_l2[a7] = 1000;
1.330 - neg_l2[a8] = -1000;
1.331 -
1.332 - neg_s[n1] = 100;
1.333 - neg_s[n4] = -100;
1.334 -
1.335 - neg_c[a1] = 100;
1.336 - neg_c[a2] = 30;
1.337 - neg_c[a3] = 20;
1.338 - neg_c[a4] = 80;
1.339 - neg_c[a5] = 50;
1.340 - neg_c[a6] = 10;
1.341 - neg_c[a7] = 80;
1.342 - neg_c[a8] = 30;
1.343 - neg_c[a9] = -120;
1.344
1.345 - Digraph negs_gr;
1.346 - Digraph::NodeMap<int> negs_s(negs_gr);
1.347 - Digraph::ArcMap<int> negs_c(negs_gr);
1.348 - ConstMap<Arc, int> negs_l(0), negs_u(1000);
1.349 - n1 = negs_gr.addNode();
1.350 - n2 = negs_gr.addNode();
1.351 - negs_s[n1] = 100;
1.352 - negs_s[n2] = -300;
1.353 - negs_c[negs_gr.addArc(n1, n2)] = -1;
1.354 + std::istringstream neg_inp1(test_neg1_lgf);
1.355 + DigraphReader<Digraph>(neg1_gr, neg_inp1)
1.356 + .arcMap("cost", neg1_c)
1.357 + .arcMap("low1", neg1_l1)
1.358 + .arcMap("low2", neg1_l2)
1.359 + .nodeMap("sup", neg1_s)
1.360 + .run();
1.361
1.362 + std::istringstream neg_inp2(test_neg2_lgf);
1.363 + DigraphReader<Digraph>(neg2_gr, neg_inp2)
1.364 + .arcMap("cost", neg2_c)
1.365 + .nodeMap("sup", neg2_s)
1.366 + .run();
1.367
1.368 - // A. Test NetworkSimplex with the default pivot rule
1.369 + // Check the interface of NetworkSimplex
1.370 {
1.371 - NetworkSimplex<Digraph> mcf(gr);
1.372 -
1.373 - // Check the equality form
1.374 - mcf.upperMap(u).costMap(c);
1.375 - checkMcf(mcf, mcf.supplyMap(s1).run(),
1.376 - gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1");
1.377 - checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
1.378 - gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2");
1.379 - mcf.lowerMap(l2);
1.380 - checkMcf(mcf, mcf.supplyMap(s1).run(),
1.381 - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3");
1.382 - checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
1.383 - gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4");
1.384 - mcf.reset();
1.385 - checkMcf(mcf, mcf.supplyMap(s1).run(),
1.386 - gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5");
1.387 - checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
1.388 - gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6");
1.389 - mcf.reset();
1.390 - checkMcf(mcf, mcf.run(),
1.391 - gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7");
1.392 - checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
1.393 - gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
1.394 - mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
1.395 - checkMcf(mcf, mcf.run(),
1.396 - gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9");
1.397 -
1.398 - // Check the GEQ form
1.399 - mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
1.400 - checkMcf(mcf, mcf.run(),
1.401 - gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ);
1.402 - mcf.supplyType(mcf.GEQ);
1.403 - checkMcf(mcf, mcf.lowerMap(l2).run(),
1.404 - gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ);
1.405 - mcf.supplyMap(s6);
1.406 - checkMcf(mcf, mcf.run(),
1.407 - gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ);
1.408 -
1.409 - // Check the LEQ form
1.410 - mcf.reset().supplyType(mcf.LEQ);
1.411 - mcf.upperMap(u).costMap(c).supplyMap(s6);
1.412 - checkMcf(mcf, mcf.run(),
1.413 - gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ);
1.414 - checkMcf(mcf, mcf.lowerMap(l2).run(),
1.415 - gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ);
1.416 - mcf.supplyMap(s5);
1.417 - checkMcf(mcf, mcf.run(),
1.418 - gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ);
1.419 -
1.420 - // Check negative costs
1.421 - NetworkSimplex<Digraph> neg_mcf(neg_gr);
1.422 - neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
1.423 - checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
1.424 - neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16");
1.425 - neg_mcf.upperMap(neg_u2);
1.426 - checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
1.427 - neg_c, neg_s, neg_mcf.OPTIMAL, true, -40000, "#A17");
1.428 - neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
1.429 - checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
1.430 - neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18");
1.431 -
1.432 - NetworkSimplex<Digraph> negs_mcf(negs_gr);
1.433 - negs_mcf.costMap(negs_c).supplyMap(negs_s);
1.434 - checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
1.435 - negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
1.436 + typedef concepts::Digraph GR;
1.437 + checkConcept< McfClassConcept<GR, int, int>,
1.438 + NetworkSimplex<GR> >();
1.439 + checkConcept< McfClassConcept<GR, double, double>,
1.440 + NetworkSimplex<GR, double> >();
1.441 + checkConcept< McfClassConcept<GR, int, double>,
1.442 + NetworkSimplex<GR, int, double> >();
1.443 }
1.444
1.445 - // B. Test NetworkSimplex with each pivot rule
1.446 + // Check the interface of CapacityScaling
1.447 {
1.448 - NetworkSimplex<Digraph> mcf(gr);
1.449 - mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
1.450 + typedef concepts::Digraph GR;
1.451 + checkConcept< McfClassConcept<GR, int, int>,
1.452 + CapacityScaling<GR> >();
1.453 + checkConcept< McfClassConcept<GR, double, double>,
1.454 + CapacityScaling<GR, double> >();
1.455 + checkConcept< McfClassConcept<GR, int, double>,
1.456 + CapacityScaling<GR, int, double> >();
1.457 + typedef CapacityScaling<GR>::
1.458 + SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS;
1.459 + checkConcept< McfClassConcept<GR, int, int>, CAS >();
1.460 + }
1.461
1.462 - checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
1.463 - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1");
1.464 - checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
1.465 - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2");
1.466 - checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
1.467 - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3");
1.468 - checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
1.469 - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4");
1.470 - checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
1.471 - gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5");
1.472 + // Check the interface of CostScaling
1.473 + {
1.474 + typedef concepts::Digraph GR;
1.475 + checkConcept< McfClassConcept<GR, int, int>,
1.476 + CostScaling<GR> >();
1.477 + checkConcept< McfClassConcept<GR, double, double>,
1.478 + CostScaling<GR, double> >();
1.479 + checkConcept< McfClassConcept<GR, int, double>,
1.480 + CostScaling<GR, int, double> >();
1.481 + typedef CostScaling<GR>::
1.482 + SetLargeCost<double>::Create COS;
1.483 + checkConcept< McfClassConcept<GR, int, int>, COS >();
1.484 + }
1.485 +
1.486 + // Check the interface of CycleCanceling
1.487 + {
1.488 + typedef concepts::Digraph GR;
1.489 + checkConcept< McfClassConcept<GR, int, int>,
1.490 + CycleCanceling<GR> >();
1.491 + checkConcept< McfClassConcept<GR, double, double>,
1.492 + CycleCanceling<GR, double> >();
1.493 + checkConcept< McfClassConcept<GR, int, double>,
1.494 + CycleCanceling<GR, int, double> >();
1.495 + }
1.496 +
1.497 + // Test NetworkSimplex
1.498 + {
1.499 + typedef NetworkSimplex<Digraph> MCF;
1.500 + runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
1.501 + runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
1.502 + runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE", true);
1.503 + runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE");
1.504 + runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS", true);
1.505 + runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS");
1.506 + runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
1.507 + runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
1.508 + runMcfGeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL", true);
1.509 + runMcfLeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL");
1.510 + }
1.511 +
1.512 + // Test CapacityScaling
1.513 + {
1.514 + typedef CapacityScaling<Digraph> MCF;
1.515 + runMcfGeqTests<MCF>(0, "SSP");
1.516 + runMcfGeqTests<MCF>(2, "CAS");
1.517 + }
1.518 +
1.519 + // Test CostScaling
1.520 + {
1.521 + typedef CostScaling<Digraph> MCF;
1.522 + runMcfGeqTests<MCF>(MCF::PUSH, "COS-PR");
1.523 + runMcfGeqTests<MCF>(MCF::AUGMENT, "COS-AR");
1.524 + runMcfGeqTests<MCF>(MCF::PARTIAL_AUGMENT, "COS-PAR");
1.525 + }
1.526 +
1.527 + // Test CycleCanceling
1.528 + {
1.529 + typedef CycleCanceling<Digraph> MCF;
1.530 + runMcfGeqTests<MCF>(MCF::SIMPLE_CYCLE_CANCELING, "SCC");
1.531 + runMcfGeqTests<MCF>(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC");
1.532 + runMcfGeqTests<MCF>(MCF::CANCEL_AND_TIGHTEN, "CAT");
1.533 }
1.534
1.535 return 0;