test/min_cost_flow_test.cc
changeset 648 e8349c6f12ca
child 652 5232721b3f14
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/min_cost_flow_test.cc	Tue Feb 24 09:46:02 2009 +0100
     1.3 @@ -0,0 +1,455 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2009
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <iostream>
    1.23 +#include <fstream>
    1.24 +
    1.25 +#include <lemon/list_graph.h>
    1.26 +#include <lemon/smart_graph.h>
    1.27 +#include <lemon/lgf_reader.h>
    1.28 +
    1.29 +//#include <lemon/cycle_canceling.h>
    1.30 +//#include <lemon/capacity_scaling.h>
    1.31 +//#include <lemon/cost_scaling.h>
    1.32 +#include <lemon/network_simplex.h>
    1.33 +//#include <lemon/min_cost_flow.h>
    1.34 +//#include <lemon/min_cost_max_flow.h>
    1.35 +
    1.36 +#include <lemon/concepts/digraph.h>
    1.37 +#include <lemon/concept_check.h>
    1.38 +
    1.39 +#include "test_tools.h"
    1.40 +
    1.41 +using namespace lemon;
    1.42 +
    1.43 +char test_lgf[] =
    1.44 +  "@nodes\n"
    1.45 +  "label  sup1 sup2 sup3\n"
    1.46 +  "    1    20   27    0\n"
    1.47 +  "    2    -4    0    0\n"
    1.48 +  "    3     0    0    0\n"
    1.49 +  "    4     0    0    0\n"
    1.50 +  "    5     9    0    0\n"
    1.51 +  "    6    -6    0    0\n"
    1.52 +  "    7     0    0    0\n"
    1.53 +  "    8     0    0    0\n"
    1.54 +  "    9     3    0    0\n"
    1.55 +  "   10    -2    0    0\n"
    1.56 +  "   11     0    0    0\n"
    1.57 +  "   12   -20  -27    0\n"
    1.58 +  "\n"
    1.59 +  "@arcs\n"
    1.60 +  "       cost  cap low1 low2\n"
    1.61 +  " 1  2    70   11    0    8\n"
    1.62 +  " 1  3   150    3    0    1\n"
    1.63 +  " 1  4    80   15    0    2\n"
    1.64 +  " 2  8    80   12    0    0\n"
    1.65 +  " 3  5   140    5    0    3\n"
    1.66 +  " 4  6    60   10    0    1\n"
    1.67 +  " 4  7    80    2    0    0\n"
    1.68 +  " 4  8   110    3    0    0\n"
    1.69 +  " 5  7    60   14    0    0\n"
    1.70 +  " 5 11   120   12    0    0\n"
    1.71 +  " 6  3     0    3    0    0\n"
    1.72 +  " 6  9   140    4    0    0\n"
    1.73 +  " 6 10    90    8    0    0\n"
    1.74 +  " 7  1    30    5    0    0\n"
    1.75 +  " 8 12    60   16    0    4\n"
    1.76 +  " 9 12    50    6    0    0\n"
    1.77 +  "10 12    70   13    0    5\n"
    1.78 +  "10  2   100    7    0    0\n"
    1.79 +  "10  7    60   10    0    0\n"
    1.80 +  "11 10    20   14    0    6\n"
    1.81 +  "12 11    30   10    0    0\n"
    1.82 +  "\n"
    1.83 +  "@attributes\n"
    1.84 +  "source 1\n"
    1.85 +  "target 12\n";
    1.86 +
    1.87 +
    1.88 +// Check the interface of an MCF algorithm
    1.89 +template <typename GR, typename Value>
    1.90 +class McfClassConcept
    1.91 +{
    1.92 +public:
    1.93 +
    1.94 +  template <typename MCF>
    1.95 +  struct Constraints {
    1.96 +    void constraints() {
    1.97 +      checkConcept<concepts::Digraph, GR>();
    1.98 +
    1.99 +      MCF mcf_test1(g, lower, upper, cost, sup);
   1.100 +      MCF mcf_test2(g, upper, cost, sup);
   1.101 +      MCF mcf_test3(g, lower, upper, cost, n, n, k);
   1.102 +      MCF mcf_test4(g, upper, cost, n, n, k);
   1.103 +
   1.104 +      // TODO: This part should be enabled and the next part
   1.105 +      // should be removed if map copying is supported
   1.106 +/*
   1.107 +      flow = mcf_test1.flowMap();
   1.108 +      mcf_test1.flowMap(flow);
   1.109 +
   1.110 +      pot = mcf_test1.potentialMap();
   1.111 +      mcf_test1.potentialMap(pot);
   1.112 +*/
   1.113 +/**/
   1.114 +      const typename MCF::FlowMap &fm =
   1.115 +        mcf_test1.flowMap();
   1.116 +      mcf_test1.flowMap(flow);
   1.117 +      const typename MCF::PotentialMap &pm =
   1.118 +        mcf_test1.potentialMap();
   1.119 +      mcf_test1.potentialMap(pot);
   1.120 +      ignore_unused_variable_warning(fm);
   1.121 +      ignore_unused_variable_warning(pm);
   1.122 +/**/
   1.123 +
   1.124 +      mcf_test1.run();
   1.125 +
   1.126 +      v = mcf_test1.totalCost();
   1.127 +      v = mcf_test1.flow(a);
   1.128 +      v = mcf_test1.potential(n);
   1.129 +    }
   1.130 +
   1.131 +    typedef typename GR::Node Node;
   1.132 +    typedef typename GR::Arc Arc;
   1.133 +    typedef concepts::ReadMap<Node, Value> NM;
   1.134 +    typedef concepts::ReadMap<Arc, Value> AM;
   1.135 +
   1.136 +    const GR &g;
   1.137 +    const AM &lower;
   1.138 +    const AM &upper;
   1.139 +    const AM &cost;
   1.140 +    const NM &sup;
   1.141 +    const Node &n;
   1.142 +    const Arc &a;
   1.143 +    const Value &k;
   1.144 +    Value v;
   1.145 +
   1.146 +    typename MCF::FlowMap &flow;
   1.147 +    typename MCF::PotentialMap &pot;
   1.148 +  };
   1.149 +
   1.150 +};
   1.151 +
   1.152 +
   1.153 +// Check the feasibility of the given flow (primal soluiton)
   1.154 +template < typename GR, typename LM, typename UM,
   1.155 +           typename SM, typename FM >
   1.156 +bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
   1.157 +                const SM& supply, const FM& flow )
   1.158 +{
   1.159 +  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   1.160 +
   1.161 +  for (ArcIt e(gr); e != INVALID; ++e) {
   1.162 +    if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
   1.163 +  }
   1.164 +
   1.165 +  for (NodeIt n(gr); n != INVALID; ++n) {
   1.166 +    typename SM::Value sum = 0;
   1.167 +    for (OutArcIt e(gr, n); e != INVALID; ++e)
   1.168 +      sum += flow[e];
   1.169 +    for (InArcIt e(gr, n); e != INVALID; ++e)
   1.170 +      sum -= flow[e];
   1.171 +    if (sum != supply[n]) return false;
   1.172 +  }
   1.173 +
   1.174 +  return true;
   1.175 +}
   1.176 +
   1.177 +// Check the feasibility of the given potentials (dual soluiton)
   1.178 +// using the Complementary Slackness optimality condition
   1.179 +template < typename GR, typename LM, typename UM,
   1.180 +           typename CM, typename FM, typename PM >
   1.181 +bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
   1.182 +                     const CM& cost, const FM& flow, const PM& pi )
   1.183 +{
   1.184 +  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   1.185 +
   1.186 +  bool opt = true;
   1.187 +  for (ArcIt e(gr); opt && e != INVALID; ++e) {
   1.188 +    typename CM::Value red_cost =
   1.189 +      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
   1.190 +    opt = red_cost == 0 ||
   1.191 +          (red_cost > 0 && flow[e] == lower[e]) ||
   1.192 +          (red_cost < 0 && flow[e] == upper[e]);
   1.193 +  }
   1.194 +  return opt;
   1.195 +}
   1.196 +
   1.197 +// Run a minimum cost flow algorithm and check the results
   1.198 +template < typename MCF, typename GR,
   1.199 +           typename LM, typename UM,
   1.200 +           typename CM, typename SM >
   1.201 +void checkMcf( const MCF& mcf, bool mcf_result,
   1.202 +               const GR& gr, const LM& lower, const UM& upper,
   1.203 +               const CM& cost, const SM& supply,
   1.204 +               bool result, typename CM::Value total,
   1.205 +               const std::string &test_id = "" )
   1.206 +{
   1.207 +  check(mcf_result == result, "Wrong result " + test_id);
   1.208 +  if (result) {
   1.209 +    check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
   1.210 +          "The flow is not feasible " + test_id);
   1.211 +    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
   1.212 +    check(checkPotential(gr, lower, upper, cost, mcf.flowMap(),
   1.213 +                         mcf.potentialMap()),
   1.214 +          "Wrong potentials " + test_id);
   1.215 +  }
   1.216 +}
   1.217 +
   1.218 +int main()
   1.219 +{
   1.220 +  // Check the interfaces
   1.221 +  {
   1.222 +    typedef int Value;
   1.223 +    // This typedef should be enabled if the standard maps are
   1.224 +    // reference maps in the graph concepts
   1.225 +    //typedef concepts::Digraph GR;
   1.226 +    typedef ListDigraph GR;
   1.227 +    typedef concepts::ReadMap<GR::Node, Value> NM;
   1.228 +    typedef concepts::ReadMap<GR::Arc, Value> AM;
   1.229 +
   1.230 +    //checkConcept< McfClassConcept<GR, Value>,
   1.231 +    //              CycleCanceling<GR, AM, AM, AM, NM> >();
   1.232 +    //checkConcept< McfClassConcept<GR, Value>,
   1.233 +    //              CapacityScaling<GR, AM, AM, AM, NM> >();
   1.234 +    //checkConcept< McfClassConcept<GR, Value>,
   1.235 +    //              CostScaling<GR, AM, AM, AM, NM> >();
   1.236 +    checkConcept< McfClassConcept<GR, Value>,
   1.237 +                  NetworkSimplex<GR, AM, AM, AM, NM> >();
   1.238 +    //checkConcept< MinCostFlow<GR, Value>,
   1.239 +    //              NetworkSimplex<GR, AM, AM, AM, NM> >();
   1.240 +  }
   1.241 +
   1.242 +  // Run various MCF tests
   1.243 +  typedef ListDigraph Digraph;
   1.244 +  DIGRAPH_TYPEDEFS(ListDigraph);
   1.245 +
   1.246 +  // Read the test digraph
   1.247 +  Digraph gr;
   1.248 +  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
   1.249 +  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
   1.250 +  Node v, w;
   1.251 +
   1.252 +  std::istringstream input(test_lgf);
   1.253 +  DigraphReader<Digraph>(gr, input)
   1.254 +    .arcMap("cost", c)
   1.255 +    .arcMap("cap", u)
   1.256 +    .arcMap("low1", l1)
   1.257 +    .arcMap("low2", l2)
   1.258 +    .nodeMap("sup1", s1)
   1.259 +    .nodeMap("sup2", s2)
   1.260 +    .nodeMap("sup3", s3)
   1.261 +    .node("source", v)
   1.262 +    .node("target", w)
   1.263 +    .run();
   1.264 +
   1.265 +/*
   1.266 +  // A. Test CapacityScaling with scaling
   1.267 +  {
   1.268 +    CapacityScaling<Digraph> mcf1(gr, u, c, s1);
   1.269 +    CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
   1.270 +    CapacityScaling<Digraph> mcf3(gr, u, c, s3);
   1.271 +    CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
   1.272 +    CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.273 +    CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
   1.274 +
   1.275 +    checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true,  5240, "#A1");
   1.276 +    checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true,  7620, "#A2");
   1.277 +    checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true,     0, "#A3");
   1.278 +    checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true,  5970, "#A4");
   1.279 +    checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true,  8010, "#A5");
   1.280 +    checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false,    0, "#A6");
   1.281 +  }
   1.282 +
   1.283 +  // B. Test CapacityScaling without scaling
   1.284 +  {
   1.285 +    CapacityScaling<Digraph> mcf1(gr, u, c, s1);
   1.286 +    CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
   1.287 +    CapacityScaling<Digraph> mcf3(gr, u, c, s3);
   1.288 +    CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
   1.289 +    CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.290 +    CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
   1.291 +
   1.292 +    checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true,  5240, "#B1");
   1.293 +    checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true,  7620, "#B2");
   1.294 +    checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true,     0, "#B3");
   1.295 +    checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true,  5970, "#B4");
   1.296 +    checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true,  8010, "#B5");
   1.297 +    checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false,    0, "#B6");
   1.298 +  }
   1.299 +
   1.300 +  // C. Test CostScaling using partial augment-relabel method
   1.301 +  {
   1.302 +    CostScaling<Digraph> mcf1(gr, u, c, s1);
   1.303 +    CostScaling<Digraph> mcf2(gr, u, c, v, w, 27);
   1.304 +    CostScaling<Digraph> mcf3(gr, u, c, s3);
   1.305 +    CostScaling<Digraph> mcf4(gr, l2, u, c, s1);
   1.306 +    CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.307 +    CostScaling<Digraph> mcf6(gr, l2, u, c, s3);
   1.308 +
   1.309 +    checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true,  5240, "#C1");
   1.310 +    checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true,  7620, "#C2");
   1.311 +    checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true,     0, "#C3");
   1.312 +    checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true,  5970, "#C4");
   1.313 +    checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true,  8010, "#C5");
   1.314 +    checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false,    0, "#C6");
   1.315 +  }
   1.316 +
   1.317 +  // D. Test CostScaling using push-relabel method
   1.318 +  {
   1.319 +    CostScaling<Digraph> mcf1(gr, u, c, s1);
   1.320 +    CostScaling<Digraph> mcf2(gr, u, c, v, w, 27);
   1.321 +    CostScaling<Digraph> mcf3(gr, u, c, s3);
   1.322 +    CostScaling<Digraph> mcf4(gr, l2, u, c, s1);
   1.323 +    CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.324 +    CostScaling<Digraph> mcf6(gr, l2, u, c, s3);
   1.325 +
   1.326 +    checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true,  5240, "#D1");
   1.327 +    checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true,  7620, "#D2");
   1.328 +    checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true,     0, "#D3");
   1.329 +    checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true,  5970, "#D4");
   1.330 +    checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true,  8010, "#D5");
   1.331 +    checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false,    0, "#D6");
   1.332 +  }
   1.333 +*/
   1.334 +
   1.335 +  // E. Test NetworkSimplex with FIRST_ELIGIBLE_PIVOT
   1.336 +  {
   1.337 +    NetworkSimplex<Digraph>::PivotRuleEnum pr =
   1.338 +      NetworkSimplex<Digraph>::FIRST_ELIGIBLE_PIVOT;
   1.339 +    NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
   1.340 +    NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
   1.341 +    NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
   1.342 +    NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
   1.343 +    NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.344 +    NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
   1.345 +
   1.346 +    checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true,  5240, "#E1");
   1.347 +    checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true,  7620, "#E2");
   1.348 +    checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true,     0, "#E3");
   1.349 +    checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true,  5970, "#E4");
   1.350 +    checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true,  8010, "#E5");
   1.351 +    checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false,    0, "#E6");
   1.352 +  }
   1.353 +
   1.354 +  // F. Test NetworkSimplex with BEST_ELIGIBLE_PIVOT
   1.355 +  {
   1.356 +    NetworkSimplex<Digraph>::PivotRuleEnum pr =
   1.357 +      NetworkSimplex<Digraph>::BEST_ELIGIBLE_PIVOT;
   1.358 +    NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
   1.359 +    NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
   1.360 +    NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
   1.361 +    NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
   1.362 +    NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.363 +    NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
   1.364 +
   1.365 +    checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true,  5240, "#F1");
   1.366 +    checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true,  7620, "#F2");
   1.367 +    checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true,     0, "#F3");
   1.368 +    checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true,  5970, "#F4");
   1.369 +    checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true,  8010, "#F5");
   1.370 +    checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false,    0, "#F6");
   1.371 +  }
   1.372 +
   1.373 +  // G. Test NetworkSimplex with BLOCK_SEARCH_PIVOT
   1.374 +  {
   1.375 +    NetworkSimplex<Digraph>::PivotRuleEnum pr =
   1.376 +      NetworkSimplex<Digraph>::BLOCK_SEARCH_PIVOT;
   1.377 +    NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
   1.378 +    NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
   1.379 +    NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
   1.380 +    NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
   1.381 +    NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.382 +    NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
   1.383 +
   1.384 +    checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true,  5240, "#G1");
   1.385 +    checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true,  7620, "#G2");
   1.386 +    checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true,     0, "#G3");
   1.387 +    checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true,  5970, "#G4");
   1.388 +    checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true,  8010, "#G5");
   1.389 +    checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false,    0, "#G6");
   1.390 +  }
   1.391 +
   1.392 +  // H. Test NetworkSimplex with CANDIDATE_LIST_PIVOT
   1.393 +  {
   1.394 +    NetworkSimplex<Digraph>::PivotRuleEnum pr =
   1.395 +      NetworkSimplex<Digraph>::CANDIDATE_LIST_PIVOT;
   1.396 +    NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
   1.397 +    NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
   1.398 +    NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
   1.399 +    NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
   1.400 +    NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.401 +    NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
   1.402 +
   1.403 +    checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true,  5240, "#H1");
   1.404 +    checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true,  7620, "#H2");
   1.405 +    checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true,     0, "#H3");
   1.406 +    checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true,  5970, "#H4");
   1.407 +    checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true,  8010, "#H5");
   1.408 +    checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false,    0, "#H6");
   1.409 +  }
   1.410 +
   1.411 +  // I. Test NetworkSimplex with ALTERING_LIST_PIVOT
   1.412 +  {
   1.413 +    NetworkSimplex<Digraph>::PivotRuleEnum pr =
   1.414 +      NetworkSimplex<Digraph>::ALTERING_LIST_PIVOT;
   1.415 +    NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
   1.416 +    NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
   1.417 +    NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
   1.418 +    NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
   1.419 +    NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.420 +    NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
   1.421 +
   1.422 +    checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true,  5240, "#I1");
   1.423 +    checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true,  7620, "#I2");
   1.424 +    checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true,     0, "#I3");
   1.425 +    checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true,  5970, "#I4");
   1.426 +    checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true,  8010, "#I5");
   1.427 +    checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false,    0, "#I6");
   1.428 +  }
   1.429 +
   1.430 +/*
   1.431 +  // J. Test MinCostFlow
   1.432 +  {
   1.433 +    MinCostFlow<Digraph> mcf1(gr, u, c, s1);
   1.434 +    MinCostFlow<Digraph> mcf2(gr, u, c, v, w, 27);
   1.435 +    MinCostFlow<Digraph> mcf3(gr, u, c, s3);
   1.436 +    MinCostFlow<Digraph> mcf4(gr, l2, u, c, s1);
   1.437 +    MinCostFlow<Digraph> mcf5(gr, l2, u, c, v, w, 27);
   1.438 +    MinCostFlow<Digraph> mcf6(gr, l2, u, c, s3);
   1.439 +
   1.440 +    checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true,  5240, "#J1");
   1.441 +    checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true,  7620, "#J2");
   1.442 +    checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true,     0, "#J3");
   1.443 +    checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true,  5970, "#J4");
   1.444 +    checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true,  8010, "#J5");
   1.445 +    checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false,    0, "#J6");
   1.446 +  }
   1.447 +*/
   1.448 +/*
   1.449 +  // K. Test MinCostMaxFlow
   1.450 +  {
   1.451 +    MinCostMaxFlow<Digraph> mcmf(gr, u, c, v, w);
   1.452 +    mcmf.run();
   1.453 +    checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1");
   1.454 +  }
   1.455 +*/
   1.456 +
   1.457 +  return 0;
   1.458 +}