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 ⊃
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 +}