1.1 --- a/test/min_cost_flow_test.cc Tue Mar 24 00:18:25 2009 +0100
1.2 +++ b/test/min_cost_flow_test.cc Wed Mar 25 15:58:44 2009 +0100
1.3 @@ -20,15 +20,9 @@
1.4 #include <fstream>
1.5
1.6 #include <lemon/list_graph.h>
1.7 -#include <lemon/smart_graph.h>
1.8 #include <lemon/lgf_reader.h>
1.9
1.10 -//#include <lemon/cycle_canceling.h>
1.11 -//#include <lemon/capacity_scaling.h>
1.12 -//#include <lemon/cost_scaling.h>
1.13 #include <lemon/network_simplex.h>
1.14 -//#include <lemon/min_cost_flow.h>
1.15 -//#include <lemon/min_cost_max_flow.h>
1.16
1.17 #include <lemon/concepts/digraph.h>
1.18 #include <lemon/concept_check.h>
1.19 @@ -93,36 +87,30 @@
1.20 void constraints() {
1.21 checkConcept<concepts::Digraph, GR>();
1.22
1.23 - MCF mcf_test1(g, lower, upper, cost, sup);
1.24 - MCF mcf_test2(g, upper, cost, sup);
1.25 - MCF mcf_test3(g, lower, upper, cost, n, n, k);
1.26 - MCF mcf_test4(g, upper, cost, n, n, k);
1.27 + MCF mcf(g);
1.28
1.29 - // TODO: This part should be enabled and the next part
1.30 - // should be removed if map copying is supported
1.31 -/*
1.32 - flow = mcf_test1.flowMap();
1.33 - mcf_test1.flowMap(flow);
1.34 + b = mcf.lowerMap(lower)
1.35 + .upperMap(upper)
1.36 + .capacityMap(upper)
1.37 + .boundMaps(lower, upper)
1.38 + .costMap(cost)
1.39 + .supplyMap(sup)
1.40 + .stSupply(n, n, k)
1.41 + .run();
1.42
1.43 - pot = mcf_test1.potentialMap();
1.44 - mcf_test1.potentialMap(pot);
1.45 -*/
1.46 -/**/
1.47 - const typename MCF::FlowMap &fm =
1.48 - mcf_test1.flowMap();
1.49 - mcf_test1.flowMap(flow);
1.50 - const typename MCF::PotentialMap &pm =
1.51 - mcf_test1.potentialMap();
1.52 - mcf_test1.potentialMap(pot);
1.53 + const typename MCF::FlowMap &fm = mcf.flowMap();
1.54 + const typename MCF::PotentialMap &pm = mcf.potentialMap();
1.55 +
1.56 + v = mcf.totalCost();
1.57 + double x = mcf.template totalCost<double>();
1.58 + v = mcf.flow(a);
1.59 + v = mcf.potential(n);
1.60 + mcf.flowMap(flow);
1.61 + mcf.potentialMap(pot);
1.62 +
1.63 ignore_unused_variable_warning(fm);
1.64 ignore_unused_variable_warning(pm);
1.65 -/**/
1.66 -
1.67 - mcf_test1.run();
1.68 -
1.69 - v = mcf_test1.totalCost();
1.70 - v = mcf_test1.flow(a);
1.71 - v = mcf_test1.potential(n);
1.72 + ignore_unused_variable_warning(x);
1.73 }
1.74
1.75 typedef typename GR::Node Node;
1.76 @@ -139,6 +127,7 @@
1.77 const Arc &a;
1.78 const Value &k;
1.79 Value v;
1.80 + bool b;
1.81
1.82 typename MCF::FlowMap &flow;
1.83 typename MCF::PotentialMap &pot;
1.84 @@ -172,7 +161,7 @@
1.85 }
1.86
1.87 // Check the feasibility of the given potentials (dual soluiton)
1.88 -// using the Complementary Slackness optimality condition
1.89 +// using the "Complementary Slackness" optimality condition
1.90 template < typename GR, typename LM, typename UM,
1.91 typename CM, typename FM, typename PM >
1.92 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
1.93 @@ -217,23 +206,14 @@
1.94 // Check the interfaces
1.95 {
1.96 typedef int Value;
1.97 - // This typedef should be enabled if the standard maps are
1.98 - // reference maps in the graph concepts
1.99 + // TODO: This typedef should be enabled if the standard maps are
1.100 + // reference maps in the graph concepts (See #190).
1.101 +/**/
1.102 //typedef concepts::Digraph GR;
1.103 typedef ListDigraph GR;
1.104 - typedef concepts::ReadMap<GR::Node, Value> NM;
1.105 - typedef concepts::ReadMap<GR::Arc, Value> AM;
1.106 -
1.107 - //checkConcept< McfClassConcept<GR, Value>,
1.108 - // CycleCanceling<GR, AM, AM, AM, NM> >();
1.109 - //checkConcept< McfClassConcept<GR, Value>,
1.110 - // CapacityScaling<GR, AM, AM, AM, NM> >();
1.111 - //checkConcept< McfClassConcept<GR, Value>,
1.112 - // CostScaling<GR, AM, AM, AM, NM> >();
1.113 +/**/
1.114 checkConcept< McfClassConcept<GR, Value>,
1.115 - NetworkSimplex<GR, AM, AM, AM, NM> >();
1.116 - //checkConcept< MinCostFlow<GR, Value>,
1.117 - // NetworkSimplex<GR, AM, AM, AM, NM> >();
1.118 + NetworkSimplex<GR, Value> >();
1.119 }
1.120
1.121 // Run various MCF tests
1.122 @@ -244,6 +224,7 @@
1.123 Digraph gr;
1.124 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
1.125 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
1.126 + ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
1.127 Node v, w;
1.128
1.129 std::istringstream input(test_lgf);
1.130 @@ -259,197 +240,50 @@
1.131 .node("target", w)
1.132 .run();
1.133
1.134 -/*
1.135 - // A. Test CapacityScaling with scaling
1.136 + // A. Test NetworkSimplex with the default pivot rule
1.137 {
1.138 - CapacityScaling<Digraph> mcf1(gr, u, c, s1);
1.139 - CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
1.140 - CapacityScaling<Digraph> mcf3(gr, u, c, s3);
1.141 - CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
1.142 - CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.143 - CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
1.144 + NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
1.145 + mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
1.146
1.147 - checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#A1");
1.148 - checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#A2");
1.149 - checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#A3");
1.150 - checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#A4");
1.151 - checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#A5");
1.152 - checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#A6");
1.153 + checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
1.154 + gr, l1, u, c, s1, true, 5240, "#A1");
1.155 + checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
1.156 + gr, l1, u, c, s2, true, 7620, "#A2");
1.157 + checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
1.158 + gr, l2, u, c, s1, true, 5970, "#A3");
1.159 + checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
1.160 + gr, l2, u, c, s2, true, 8010, "#A4");
1.161 + checkMcf(mcf5, mcf5.supplyMap(s1).run(),
1.162 + gr, l1, cu, cc, s1, true, 74, "#A5");
1.163 + checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
1.164 + gr, l2, cu, cc, s2, true, 94, "#A6");
1.165 + checkMcf(mcf7, mcf7.run(),
1.166 + gr, l1, cu, cc, s3, true, 0, "#A7");
1.167 + checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
1.168 + gr, l2, u, cc, s3, false, 0, "#A8");
1.169 }
1.170
1.171 - // B. Test CapacityScaling without scaling
1.172 + // B. Test NetworkSimplex with each pivot rule
1.173 {
1.174 - CapacityScaling<Digraph> mcf1(gr, u, c, s1);
1.175 - CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
1.176 - CapacityScaling<Digraph> mcf3(gr, u, c, s3);
1.177 - CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
1.178 - CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.179 - CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
1.180 + NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
1.181 + NetworkSimplex<Digraph>::PivotRule pr;
1.182
1.183 - checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#B1");
1.184 - checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#B2");
1.185 - checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#B3");
1.186 - checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#B4");
1.187 - checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#B5");
1.188 - checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#B6");
1.189 + pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
1.190 + checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
1.191 + gr, l2, u, c, s1, true, 5970, "#B1");
1.192 + pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
1.193 + checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
1.194 + gr, l2, u, c, s1, true, 5970, "#B2");
1.195 + pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
1.196 + checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
1.197 + gr, l2, u, c, s1, true, 5970, "#B3");
1.198 + pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
1.199 + checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
1.200 + gr, l2, u, c, s1, true, 5970, "#B4");
1.201 + pr = NetworkSimplex<Digraph>::ALTERING_LIST;
1.202 + checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
1.203 + gr, l2, u, c, s1, true, 5970, "#B5");
1.204 }
1.205
1.206 - // C. Test CostScaling using partial augment-relabel method
1.207 - {
1.208 - CostScaling<Digraph> mcf1(gr, u, c, s1);
1.209 - CostScaling<Digraph> mcf2(gr, u, c, v, w, 27);
1.210 - CostScaling<Digraph> mcf3(gr, u, c, s3);
1.211 - CostScaling<Digraph> mcf4(gr, l2, u, c, s1);
1.212 - CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.213 - CostScaling<Digraph> mcf6(gr, l2, u, c, s3);
1.214 -
1.215 - checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#C1");
1.216 - checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#C2");
1.217 - checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#C3");
1.218 - checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#C4");
1.219 - checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#C5");
1.220 - checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#C6");
1.221 - }
1.222 -
1.223 - // D. Test CostScaling using push-relabel method
1.224 - {
1.225 - CostScaling<Digraph> mcf1(gr, u, c, s1);
1.226 - CostScaling<Digraph> mcf2(gr, u, c, v, w, 27);
1.227 - CostScaling<Digraph> mcf3(gr, u, c, s3);
1.228 - CostScaling<Digraph> mcf4(gr, l2, u, c, s1);
1.229 - CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.230 - CostScaling<Digraph> mcf6(gr, l2, u, c, s3);
1.231 -
1.232 - checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#D1");
1.233 - checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#D2");
1.234 - checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#D3");
1.235 - checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#D4");
1.236 - checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#D5");
1.237 - checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#D6");
1.238 - }
1.239 -*/
1.240 -
1.241 - // E. Test NetworkSimplex with FIRST_ELIGIBLE_PIVOT
1.242 - {
1.243 - NetworkSimplex<Digraph>::PivotRuleEnum pr =
1.244 - NetworkSimplex<Digraph>::FIRST_ELIGIBLE_PIVOT;
1.245 - NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
1.246 - NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
1.247 - NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
1.248 - NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
1.249 - NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.250 - NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
1.251 -
1.252 - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#E1");
1.253 - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#E2");
1.254 - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#E3");
1.255 - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#E4");
1.256 - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#E5");
1.257 - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#E6");
1.258 - }
1.259 -
1.260 - // F. Test NetworkSimplex with BEST_ELIGIBLE_PIVOT
1.261 - {
1.262 - NetworkSimplex<Digraph>::PivotRuleEnum pr =
1.263 - NetworkSimplex<Digraph>::BEST_ELIGIBLE_PIVOT;
1.264 - NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
1.265 - NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
1.266 - NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
1.267 - NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
1.268 - NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.269 - NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
1.270 -
1.271 - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#F1");
1.272 - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#F2");
1.273 - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#F3");
1.274 - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#F4");
1.275 - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#F5");
1.276 - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#F6");
1.277 - }
1.278 -
1.279 - // G. Test NetworkSimplex with BLOCK_SEARCH_PIVOT
1.280 - {
1.281 - NetworkSimplex<Digraph>::PivotRuleEnum pr =
1.282 - NetworkSimplex<Digraph>::BLOCK_SEARCH_PIVOT;
1.283 - NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
1.284 - NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
1.285 - NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
1.286 - NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
1.287 - NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.288 - NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
1.289 -
1.290 - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#G1");
1.291 - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#G2");
1.292 - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#G3");
1.293 - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#G4");
1.294 - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#G5");
1.295 - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#G6");
1.296 - }
1.297 -
1.298 - // H. Test NetworkSimplex with CANDIDATE_LIST_PIVOT
1.299 - {
1.300 - NetworkSimplex<Digraph>::PivotRuleEnum pr =
1.301 - NetworkSimplex<Digraph>::CANDIDATE_LIST_PIVOT;
1.302 - NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
1.303 - NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
1.304 - NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
1.305 - NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
1.306 - NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.307 - NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
1.308 -
1.309 - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#H1");
1.310 - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#H2");
1.311 - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#H3");
1.312 - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#H4");
1.313 - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#H5");
1.314 - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#H6");
1.315 - }
1.316 -
1.317 - // I. Test NetworkSimplex with ALTERING_LIST_PIVOT
1.318 - {
1.319 - NetworkSimplex<Digraph>::PivotRuleEnum pr =
1.320 - NetworkSimplex<Digraph>::ALTERING_LIST_PIVOT;
1.321 - NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
1.322 - NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
1.323 - NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
1.324 - NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
1.325 - NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.326 - NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3);
1.327 -
1.328 - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#I1");
1.329 - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#I2");
1.330 - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#I3");
1.331 - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#I4");
1.332 - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#I5");
1.333 - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#I6");
1.334 - }
1.335 -
1.336 -/*
1.337 - // J. Test MinCostFlow
1.338 - {
1.339 - MinCostFlow<Digraph> mcf1(gr, u, c, s1);
1.340 - MinCostFlow<Digraph> mcf2(gr, u, c, v, w, 27);
1.341 - MinCostFlow<Digraph> mcf3(gr, u, c, s3);
1.342 - MinCostFlow<Digraph> mcf4(gr, l2, u, c, s1);
1.343 - MinCostFlow<Digraph> mcf5(gr, l2, u, c, v, w, 27);
1.344 - MinCostFlow<Digraph> mcf6(gr, l2, u, c, s3);
1.345 -
1.346 - checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#J1");
1.347 - checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#J2");
1.348 - checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#J3");
1.349 - checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#J4");
1.350 - checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#J5");
1.351 - checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#J6");
1.352 - }
1.353 -*/
1.354 -/*
1.355 - // K. Test MinCostMaxFlow
1.356 - {
1.357 - MinCostMaxFlow<Digraph> mcmf(gr, u, c, v, w);
1.358 - mcmf.run();
1.359 - checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1");
1.360 - }
1.361 -*/
1.362 -
1.363 return 0;
1.364 }