[593] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2009 |
---|
| 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | #include <iostream> |
---|
| 20 | #include <fstream> |
---|
| 21 | |
---|
| 22 | #include <lemon/list_graph.h> |
---|
| 23 | #include <lemon/smart_graph.h> |
---|
| 24 | #include <lemon/lgf_reader.h> |
---|
| 25 | |
---|
| 26 | //#include <lemon/cycle_canceling.h> |
---|
| 27 | //#include <lemon/capacity_scaling.h> |
---|
| 28 | //#include <lemon/cost_scaling.h> |
---|
| 29 | #include <lemon/network_simplex.h> |
---|
| 30 | //#include <lemon/min_cost_flow.h> |
---|
| 31 | //#include <lemon/min_cost_max_flow.h> |
---|
| 32 | |
---|
| 33 | #include <lemon/concepts/digraph.h> |
---|
| 34 | #include <lemon/concept_check.h> |
---|
| 35 | |
---|
| 36 | #include "test_tools.h" |
---|
| 37 | |
---|
| 38 | using namespace lemon; |
---|
| 39 | |
---|
| 40 | char test_lgf[] = |
---|
| 41 | "@nodes\n" |
---|
| 42 | "label sup1 sup2 sup3\n" |
---|
| 43 | " 1 20 27 0\n" |
---|
| 44 | " 2 -4 0 0\n" |
---|
| 45 | " 3 0 0 0\n" |
---|
| 46 | " 4 0 0 0\n" |
---|
| 47 | " 5 9 0 0\n" |
---|
| 48 | " 6 -6 0 0\n" |
---|
| 49 | " 7 0 0 0\n" |
---|
| 50 | " 8 0 0 0\n" |
---|
| 51 | " 9 3 0 0\n" |
---|
| 52 | " 10 -2 0 0\n" |
---|
| 53 | " 11 0 0 0\n" |
---|
| 54 | " 12 -20 -27 0\n" |
---|
| 55 | "\n" |
---|
| 56 | "@arcs\n" |
---|
| 57 | " cost cap low1 low2\n" |
---|
| 58 | " 1 2 70 11 0 8\n" |
---|
| 59 | " 1 3 150 3 0 1\n" |
---|
| 60 | " 1 4 80 15 0 2\n" |
---|
| 61 | " 2 8 80 12 0 0\n" |
---|
| 62 | " 3 5 140 5 0 3\n" |
---|
| 63 | " 4 6 60 10 0 1\n" |
---|
| 64 | " 4 7 80 2 0 0\n" |
---|
| 65 | " 4 8 110 3 0 0\n" |
---|
| 66 | " 5 7 60 14 0 0\n" |
---|
| 67 | " 5 11 120 12 0 0\n" |
---|
| 68 | " 6 3 0 3 0 0\n" |
---|
| 69 | " 6 9 140 4 0 0\n" |
---|
| 70 | " 6 10 90 8 0 0\n" |
---|
| 71 | " 7 1 30 5 0 0\n" |
---|
| 72 | " 8 12 60 16 0 4\n" |
---|
| 73 | " 9 12 50 6 0 0\n" |
---|
| 74 | "10 12 70 13 0 5\n" |
---|
| 75 | "10 2 100 7 0 0\n" |
---|
| 76 | "10 7 60 10 0 0\n" |
---|
| 77 | "11 10 20 14 0 6\n" |
---|
| 78 | "12 11 30 10 0 0\n" |
---|
| 79 | "\n" |
---|
| 80 | "@attributes\n" |
---|
| 81 | "source 1\n" |
---|
| 82 | "target 12\n"; |
---|
| 83 | |
---|
| 84 | |
---|
| 85 | // Check the interface of an MCF algorithm |
---|
| 86 | template <typename GR, typename Value> |
---|
| 87 | class McfClassConcept |
---|
| 88 | { |
---|
| 89 | public: |
---|
| 90 | |
---|
| 91 | template <typename MCF> |
---|
| 92 | struct Constraints { |
---|
| 93 | void constraints() { |
---|
| 94 | checkConcept<concepts::Digraph, GR>(); |
---|
| 95 | |
---|
| 96 | MCF mcf_test1(g, lower, upper, cost, sup); |
---|
| 97 | MCF mcf_test2(g, upper, cost, sup); |
---|
| 98 | MCF mcf_test3(g, lower, upper, cost, n, n, k); |
---|
| 99 | MCF mcf_test4(g, upper, cost, n, n, k); |
---|
| 100 | |
---|
| 101 | // TODO: This part should be enabled and the next part |
---|
| 102 | // should be removed if map copying is supported |
---|
| 103 | /* |
---|
| 104 | flow = mcf_test1.flowMap(); |
---|
| 105 | mcf_test1.flowMap(flow); |
---|
| 106 | |
---|
| 107 | pot = mcf_test1.potentialMap(); |
---|
| 108 | mcf_test1.potentialMap(pot); |
---|
| 109 | */ |
---|
| 110 | /**/ |
---|
| 111 | const typename MCF::FlowMap &fm = |
---|
| 112 | mcf_test1.flowMap(); |
---|
| 113 | mcf_test1.flowMap(flow); |
---|
| 114 | const typename MCF::PotentialMap &pm = |
---|
| 115 | mcf_test1.potentialMap(); |
---|
| 116 | mcf_test1.potentialMap(pot); |
---|
| 117 | ignore_unused_variable_warning(fm); |
---|
| 118 | ignore_unused_variable_warning(pm); |
---|
| 119 | /**/ |
---|
| 120 | |
---|
| 121 | mcf_test1.run(); |
---|
| 122 | |
---|
| 123 | v = mcf_test1.totalCost(); |
---|
| 124 | v = mcf_test1.flow(a); |
---|
| 125 | v = mcf_test1.potential(n); |
---|
| 126 | } |
---|
| 127 | |
---|
| 128 | typedef typename GR::Node Node; |
---|
| 129 | typedef typename GR::Arc Arc; |
---|
| 130 | typedef concepts::ReadMap<Node, Value> NM; |
---|
| 131 | typedef concepts::ReadMap<Arc, Value> AM; |
---|
| 132 | |
---|
| 133 | const GR &g; |
---|
| 134 | const AM &lower; |
---|
| 135 | const AM &upper; |
---|
| 136 | const AM &cost; |
---|
| 137 | const NM ⊃ |
---|
| 138 | const Node &n; |
---|
| 139 | const Arc &a; |
---|
| 140 | const Value &k; |
---|
| 141 | Value v; |
---|
| 142 | |
---|
| 143 | typename MCF::FlowMap &flow; |
---|
| 144 | typename MCF::PotentialMap &pot; |
---|
| 145 | }; |
---|
| 146 | |
---|
| 147 | }; |
---|
| 148 | |
---|
| 149 | |
---|
| 150 | // Check the feasibility of the given flow (primal soluiton) |
---|
| 151 | template < typename GR, typename LM, typename UM, |
---|
| 152 | typename SM, typename FM > |
---|
| 153 | bool checkFlow( const GR& gr, const LM& lower, const UM& upper, |
---|
| 154 | const SM& supply, const FM& flow ) |
---|
| 155 | { |
---|
| 156 | TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
---|
| 157 | |
---|
| 158 | for (ArcIt e(gr); e != INVALID; ++e) { |
---|
| 159 | if (flow[e] < lower[e] || flow[e] > upper[e]) return false; |
---|
| 160 | } |
---|
| 161 | |
---|
| 162 | for (NodeIt n(gr); n != INVALID; ++n) { |
---|
| 163 | typename SM::Value sum = 0; |
---|
| 164 | for (OutArcIt e(gr, n); e != INVALID; ++e) |
---|
| 165 | sum += flow[e]; |
---|
| 166 | for (InArcIt e(gr, n); e != INVALID; ++e) |
---|
| 167 | sum -= flow[e]; |
---|
| 168 | if (sum != supply[n]) return false; |
---|
| 169 | } |
---|
| 170 | |
---|
| 171 | return true; |
---|
| 172 | } |
---|
| 173 | |
---|
| 174 | // Check the feasibility of the given potentials (dual soluiton) |
---|
| 175 | // using the Complementary Slackness optimality condition |
---|
| 176 | template < typename GR, typename LM, typename UM, |
---|
| 177 | typename CM, typename FM, typename PM > |
---|
| 178 | bool checkPotential( const GR& gr, const LM& lower, const UM& upper, |
---|
| 179 | const CM& cost, const FM& flow, const PM& pi ) |
---|
| 180 | { |
---|
| 181 | TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
---|
| 182 | |
---|
| 183 | bool opt = true; |
---|
| 184 | for (ArcIt e(gr); opt && e != INVALID; ++e) { |
---|
| 185 | typename CM::Value red_cost = |
---|
| 186 | cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; |
---|
| 187 | opt = red_cost == 0 || |
---|
| 188 | (red_cost > 0 && flow[e] == lower[e]) || |
---|
| 189 | (red_cost < 0 && flow[e] == upper[e]); |
---|
| 190 | } |
---|
| 191 | return opt; |
---|
| 192 | } |
---|
| 193 | |
---|
| 194 | // Run a minimum cost flow algorithm and check the results |
---|
| 195 | template < typename MCF, typename GR, |
---|
| 196 | typename LM, typename UM, |
---|
| 197 | typename CM, typename SM > |
---|
| 198 | void checkMcf( const MCF& mcf, bool mcf_result, |
---|
| 199 | const GR& gr, const LM& lower, const UM& upper, |
---|
| 200 | const CM& cost, const SM& supply, |
---|
| 201 | bool result, typename CM::Value total, |
---|
| 202 | const std::string &test_id = "" ) |
---|
| 203 | { |
---|
| 204 | check(mcf_result == result, "Wrong result " + test_id); |
---|
| 205 | if (result) { |
---|
| 206 | check(checkFlow(gr, lower, upper, supply, mcf.flowMap()), |
---|
| 207 | "The flow is not feasible " + test_id); |
---|
| 208 | check(mcf.totalCost() == total, "The flow is not optimal " + test_id); |
---|
| 209 | check(checkPotential(gr, lower, upper, cost, mcf.flowMap(), |
---|
| 210 | mcf.potentialMap()), |
---|
| 211 | "Wrong potentials " + test_id); |
---|
| 212 | } |
---|
| 213 | } |
---|
| 214 | |
---|
| 215 | int main() |
---|
| 216 | { |
---|
| 217 | // Check the interfaces |
---|
| 218 | { |
---|
| 219 | typedef int Value; |
---|
| 220 | // This typedef should be enabled if the standard maps are |
---|
| 221 | // reference maps in the graph concepts |
---|
| 222 | //typedef concepts::Digraph GR; |
---|
| 223 | typedef ListDigraph GR; |
---|
| 224 | typedef concepts::ReadMap<GR::Node, Value> NM; |
---|
| 225 | typedef concepts::ReadMap<GR::Arc, Value> AM; |
---|
| 226 | |
---|
| 227 | //checkConcept< McfClassConcept<GR, Value>, |
---|
| 228 | // CycleCanceling<GR, AM, AM, AM, NM> >(); |
---|
| 229 | //checkConcept< McfClassConcept<GR, Value>, |
---|
| 230 | // CapacityScaling<GR, AM, AM, AM, NM> >(); |
---|
| 231 | //checkConcept< McfClassConcept<GR, Value>, |
---|
| 232 | // CostScaling<GR, AM, AM, AM, NM> >(); |
---|
| 233 | checkConcept< McfClassConcept<GR, Value>, |
---|
| 234 | NetworkSimplex<GR, AM, AM, AM, NM> >(); |
---|
| 235 | //checkConcept< MinCostFlow<GR, Value>, |
---|
| 236 | // NetworkSimplex<GR, AM, AM, AM, NM> >(); |
---|
| 237 | } |
---|
| 238 | |
---|
| 239 | // Run various MCF tests |
---|
| 240 | typedef ListDigraph Digraph; |
---|
| 241 | DIGRAPH_TYPEDEFS(ListDigraph); |
---|
| 242 | |
---|
| 243 | // Read the test digraph |
---|
| 244 | Digraph gr; |
---|
| 245 | Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr); |
---|
| 246 | Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr); |
---|
| 247 | Node v, w; |
---|
| 248 | |
---|
| 249 | std::istringstream input(test_lgf); |
---|
| 250 | DigraphReader<Digraph>(gr, input) |
---|
| 251 | .arcMap("cost", c) |
---|
| 252 | .arcMap("cap", u) |
---|
| 253 | .arcMap("low1", l1) |
---|
| 254 | .arcMap("low2", l2) |
---|
| 255 | .nodeMap("sup1", s1) |
---|
| 256 | .nodeMap("sup2", s2) |
---|
| 257 | .nodeMap("sup3", s3) |
---|
| 258 | .node("source", v) |
---|
| 259 | .node("target", w) |
---|
| 260 | .run(); |
---|
| 261 | |
---|
| 262 | /* |
---|
| 263 | // A. Test CapacityScaling with scaling |
---|
| 264 | { |
---|
| 265 | CapacityScaling<Digraph> mcf1(gr, u, c, s1); |
---|
| 266 | CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 267 | CapacityScaling<Digraph> mcf3(gr, u, c, s3); |
---|
| 268 | CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 269 | CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 270 | CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 271 | |
---|
| 272 | checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#A1"); |
---|
| 273 | checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#A2"); |
---|
| 274 | checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#A3"); |
---|
| 275 | checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#A4"); |
---|
| 276 | checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#A5"); |
---|
| 277 | checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#A6"); |
---|
| 278 | } |
---|
| 279 | |
---|
| 280 | // B. Test CapacityScaling without scaling |
---|
| 281 | { |
---|
| 282 | CapacityScaling<Digraph> mcf1(gr, u, c, s1); |
---|
| 283 | CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 284 | CapacityScaling<Digraph> mcf3(gr, u, c, s3); |
---|
| 285 | CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 286 | CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 287 | CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 288 | |
---|
| 289 | checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#B1"); |
---|
| 290 | checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#B2"); |
---|
| 291 | checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#B3"); |
---|
| 292 | checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#B4"); |
---|
| 293 | checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#B5"); |
---|
| 294 | checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#B6"); |
---|
| 295 | } |
---|
| 296 | |
---|
| 297 | // C. Test CostScaling using partial augment-relabel method |
---|
| 298 | { |
---|
| 299 | CostScaling<Digraph> mcf1(gr, u, c, s1); |
---|
| 300 | CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 301 | CostScaling<Digraph> mcf3(gr, u, c, s3); |
---|
| 302 | CostScaling<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 303 | CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 304 | CostScaling<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 305 | |
---|
| 306 | checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#C1"); |
---|
| 307 | checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#C2"); |
---|
| 308 | checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#C3"); |
---|
| 309 | checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#C4"); |
---|
| 310 | checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#C5"); |
---|
| 311 | checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#C6"); |
---|
| 312 | } |
---|
| 313 | |
---|
| 314 | // D. Test CostScaling using push-relabel method |
---|
| 315 | { |
---|
| 316 | CostScaling<Digraph> mcf1(gr, u, c, s1); |
---|
| 317 | CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 318 | CostScaling<Digraph> mcf3(gr, u, c, s3); |
---|
| 319 | CostScaling<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 320 | CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 321 | CostScaling<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 322 | |
---|
| 323 | checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#D1"); |
---|
| 324 | checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#D2"); |
---|
| 325 | checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#D3"); |
---|
| 326 | checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#D4"); |
---|
| 327 | checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#D5"); |
---|
| 328 | checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#D6"); |
---|
| 329 | } |
---|
| 330 | */ |
---|
| 331 | |
---|
| 332 | // E. Test NetworkSimplex with FIRST_ELIGIBLE_PIVOT |
---|
| 333 | { |
---|
| 334 | NetworkSimplex<Digraph>::PivotRuleEnum pr = |
---|
| 335 | NetworkSimplex<Digraph>::FIRST_ELIGIBLE_PIVOT; |
---|
| 336 | NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
---|
| 337 | NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 338 | NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
---|
| 339 | NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 340 | NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 341 | NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 342 | |
---|
| 343 | checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#E1"); |
---|
| 344 | checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#E2"); |
---|
| 345 | checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#E3"); |
---|
| 346 | checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#E4"); |
---|
| 347 | checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#E5"); |
---|
| 348 | checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#E6"); |
---|
| 349 | } |
---|
| 350 | |
---|
| 351 | // F. Test NetworkSimplex with BEST_ELIGIBLE_PIVOT |
---|
| 352 | { |
---|
| 353 | NetworkSimplex<Digraph>::PivotRuleEnum pr = |
---|
| 354 | NetworkSimplex<Digraph>::BEST_ELIGIBLE_PIVOT; |
---|
| 355 | NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
---|
| 356 | NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 357 | NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
---|
| 358 | NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 359 | NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 360 | NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 361 | |
---|
| 362 | checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#F1"); |
---|
| 363 | checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#F2"); |
---|
| 364 | checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#F3"); |
---|
| 365 | checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#F4"); |
---|
| 366 | checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#F5"); |
---|
| 367 | checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#F6"); |
---|
| 368 | } |
---|
| 369 | |
---|
| 370 | // G. Test NetworkSimplex with BLOCK_SEARCH_PIVOT |
---|
| 371 | { |
---|
| 372 | NetworkSimplex<Digraph>::PivotRuleEnum pr = |
---|
| 373 | NetworkSimplex<Digraph>::BLOCK_SEARCH_PIVOT; |
---|
| 374 | NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
---|
| 375 | NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 376 | NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
---|
| 377 | NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 378 | NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 379 | NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 380 | |
---|
| 381 | checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#G1"); |
---|
| 382 | checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#G2"); |
---|
| 383 | checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#G3"); |
---|
| 384 | checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#G4"); |
---|
| 385 | checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#G5"); |
---|
| 386 | checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#G6"); |
---|
| 387 | } |
---|
| 388 | |
---|
| 389 | // H. Test NetworkSimplex with CANDIDATE_LIST_PIVOT |
---|
| 390 | { |
---|
| 391 | NetworkSimplex<Digraph>::PivotRuleEnum pr = |
---|
| 392 | NetworkSimplex<Digraph>::CANDIDATE_LIST_PIVOT; |
---|
| 393 | NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
---|
| 394 | NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 395 | NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
---|
| 396 | NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 397 | NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 398 | NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 399 | |
---|
| 400 | checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#H1"); |
---|
| 401 | checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#H2"); |
---|
| 402 | checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#H3"); |
---|
| 403 | checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#H4"); |
---|
| 404 | checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#H5"); |
---|
| 405 | checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#H6"); |
---|
| 406 | } |
---|
| 407 | |
---|
| 408 | // I. Test NetworkSimplex with ALTERING_LIST_PIVOT |
---|
| 409 | { |
---|
| 410 | NetworkSimplex<Digraph>::PivotRuleEnum pr = |
---|
| 411 | NetworkSimplex<Digraph>::ALTERING_LIST_PIVOT; |
---|
| 412 | NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
---|
| 413 | NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 414 | NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
---|
| 415 | NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 416 | NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 417 | NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 418 | |
---|
| 419 | checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#I1"); |
---|
| 420 | checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#I2"); |
---|
| 421 | checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#I3"); |
---|
| 422 | checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#I4"); |
---|
| 423 | checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#I5"); |
---|
| 424 | checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#I6"); |
---|
| 425 | } |
---|
| 426 | |
---|
| 427 | /* |
---|
| 428 | // J. Test MinCostFlow |
---|
| 429 | { |
---|
| 430 | MinCostFlow<Digraph> mcf1(gr, u, c, s1); |
---|
| 431 | MinCostFlow<Digraph> mcf2(gr, u, c, v, w, 27); |
---|
| 432 | MinCostFlow<Digraph> mcf3(gr, u, c, s3); |
---|
| 433 | MinCostFlow<Digraph> mcf4(gr, l2, u, c, s1); |
---|
| 434 | MinCostFlow<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
---|
| 435 | MinCostFlow<Digraph> mcf6(gr, l2, u, c, s3); |
---|
| 436 | |
---|
| 437 | checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#J1"); |
---|
| 438 | checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#J2"); |
---|
| 439 | checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#J3"); |
---|
| 440 | checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#J4"); |
---|
| 441 | checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#J5"); |
---|
| 442 | checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#J6"); |
---|
| 443 | } |
---|
| 444 | */ |
---|
| 445 | /* |
---|
| 446 | // K. Test MinCostMaxFlow |
---|
| 447 | { |
---|
| 448 | MinCostMaxFlow<Digraph> mcmf(gr, u, c, v, w); |
---|
| 449 | mcmf.run(); |
---|
| 450 | checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1"); |
---|
| 451 | } |
---|
| 452 | */ |
---|
| 453 | |
---|
| 454 | return 0; |
---|
| 455 | } |
---|