Mercuriallemon-main / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/min_cost_flow_test.cc
changeset 605 5232721b3f14
parent 601 e8349c6f12ca
child 606 c7d160f73d52
equal deleted inserted replaced
0:63fbe9b448b0 1:a661d0d8fc5b 
    18 
    18 
    19 #include <iostream>
 
    19 #include <iostream>
 
    20 #include <fstream>
 
    20 #include <fstream>
 
    21 
    21 
    22 #include <lemon/list_graph.h>
 
    22 #include <lemon/list_graph.h>
 
    23 #include <lemon/smart_graph.h>
 
       
    24 #include <lemon/lgf_reader.h>
 
    23 #include <lemon/lgf_reader.h>
 
    25 
    24 
    26 //#include <lemon/cycle_canceling.h>
 
       
    27 //#include <lemon/capacity_scaling.h>
 
       
    28 //#include <lemon/cost_scaling.h>
 
       
    29 #include <lemon/network_simplex.h>
 
    25 #include <lemon/network_simplex.h>
 
    30 //#include <lemon/min_cost_flow.h>
 
       
    31 //#include <lemon/min_cost_max_flow.h>
 
       
    32 
    26 
    33 #include <lemon/concepts/digraph.h>
 
    27 #include <lemon/concepts/digraph.h>
 
    34 #include <lemon/concept_check.h>
 
    28 #include <lemon/concept_check.h>
 
    35 
    29 
    36 #include "test_tools.h"
 
    30 #include "test_tools.h"
 
    91   template <typename MCF>
 
    85   template <typename MCF>
 
    92   struct Constraints {
 
    86   struct Constraints {
 
    93     void constraints() {
 
    87     void constraints() {
 
    94       checkConcept<concepts::Digraph, GR>();
 
    88       checkConcept<concepts::Digraph, GR>();
 
    95 
    89 
    96       MCF mcf_test1(g, lower, upper, cost, sup);
 
    90       MCF mcf(g);
 
    97       MCF mcf_test2(g, upper, cost, sup);
 
    91 
    98       MCF mcf_test3(g, lower, upper, cost, n, n, k);
 
    92       b = mcf.lowerMap(lower)
 
    99       MCF mcf_test4(g, upper, cost, n, n, k);
 
    93              .upperMap(upper)
 
   100 
    94              .capacityMap(upper)
 
   101       // TODO: This part should be enabled and the next part
 
    95              .boundMaps(lower, upper)
 
   102       // should be removed if map copying is supported
 
    96              .costMap(cost)
 
   103 /*
 
    97              .supplyMap(sup)
 
   104       flow = mcf_test1.flowMap();
 
    98              .stSupply(n, n, k)
 
   105       mcf_test1.flowMap(flow);
 
    99              .run();
 
   106 
   100 
   107       pot = mcf_test1.potentialMap();
 
   101       const typename MCF::FlowMap &fm = mcf.flowMap();
 
   108       mcf_test1.potentialMap(pot);
 
   102       const typename MCF::PotentialMap &pm = mcf.potentialMap();
 
   109 */
 
   103 
   110 /**/
 
   104       v = mcf.totalCost();
 
   111       const typename MCF::FlowMap &fm =
 
   105       double x = mcf.template totalCost<double>();
 
   112         mcf_test1.flowMap();
 
   106       v = mcf.flow(a);
 
   113       mcf_test1.flowMap(flow);
 
   107       v = mcf.potential(n);
 
   114       const typename MCF::PotentialMap &pm =
 
   108       mcf.flowMap(flow);
 
   115         mcf_test1.potentialMap();
 
   109       mcf.potentialMap(pot);
 
   116       mcf_test1.potentialMap(pot);
 
   110 
   117       ignore_unused_variable_warning(fm);
 
   111       ignore_unused_variable_warning(fm);
 
   118       ignore_unused_variable_warning(pm);
 
   112       ignore_unused_variable_warning(pm);
 
   119 /**/
 
   113       ignore_unused_variable_warning(x);
 
   120 
       
   121       mcf_test1.run();
 
       
   122 
       
   123       v = mcf_test1.totalCost();
 
       
   124       v = mcf_test1.flow(a);
 
       
   125       v = mcf_test1.potential(n);
 
       
   126     }
 
   114     }
 
   127 
   115 
   128     typedef typename GR::Node Node;
 
   116     typedef typename GR::Node Node;
 
   129     typedef typename GR::Arc Arc;
 
   117     typedef typename GR::Arc Arc;
 
   130     typedef concepts::ReadMap<Node, Value> NM;
 
   118     typedef concepts::ReadMap<Node, Value> NM;
 
   137     const NM &sup;
 
   125     const NM &sup;
 
   138     const Node &n;
 
   126     const Node &n;
 
   139     const Arc &a;
 
   127     const Arc &a;
 
   140     const Value &k;
 
   128     const Value &k;
 
   141     Value v;
 
   129     Value v;
 
       
   130     bool b;
 
   142 
   131 
   143     typename MCF::FlowMap &flow;
 
   132     typename MCF::FlowMap &flow;
 
   144     typename MCF::PotentialMap &pot;
 
   133     typename MCF::PotentialMap &pot;
 
   145   };
 
   134   };
 
   146 
   135 
   170 
   159 
   171   return true;
 
   160   return true;
 
   172 }
 
   161 }
 
   173 
   162 
   174 // Check the feasibility of the given potentials (dual soluiton)
 
   163 // Check the feasibility of the given potentials (dual soluiton)
 
   175 // using the Complementary Slackness optimality condition
 
   164 // using the "Complementary Slackness" optimality condition
 
   176 template < typename GR, typename LM, typename UM,
 
   165 template < typename GR, typename LM, typename UM,
 
   177            typename CM, typename FM, typename PM >
 
   166            typename CM, typename FM, typename PM >
 
   178 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
 
   167 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
 
   179                      const CM& cost, const FM& flow, const PM& pi )
 
   168                      const CM& cost, const FM& flow, const PM& pi )
 
   180 {
 
   169 {
 
   215 int main()
 
   204 int main()
 
   216 {
 
   205 {
 
   217   // Check the interfaces
 
   206   // Check the interfaces
 
   218   {
 
   207   {
 
   219     typedef int Value;
 
   208     typedef int Value;
 
   220     // This typedef should be enabled if the standard maps are
 
   209     // TODO: This typedef should be enabled if the standard maps are
 
   221     // reference maps in the graph concepts
 
   210     // reference maps in the graph concepts (See #190).
 
       
   211 /**/
 
   222     //typedef concepts::Digraph GR;
 
   212     //typedef concepts::Digraph GR;
 
   223     typedef ListDigraph GR;
 
   213     typedef ListDigraph GR;
 
   224     typedef concepts::ReadMap<GR::Node, Value> NM;
 
   214 /**/
 
   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>,
 
   215     checkConcept< McfClassConcept<GR, Value>,
 
   234                   NetworkSimplex<GR, AM, AM, AM, NM> >();
 
   216                   NetworkSimplex<GR, Value> >();
 
   235     //checkConcept< MinCostFlow<GR, Value>,
 
       
   236     //              NetworkSimplex<GR, AM, AM, AM, NM> >();
 
       
   237   }
 
   217   }
 
   238 
   218 
   239   // Run various MCF tests
 
   219   // Run various MCF tests
 
   240   typedef ListDigraph Digraph;
 
   220   typedef ListDigraph Digraph;
 
   241   DIGRAPH_TYPEDEFS(ListDigraph);
 
   221   DIGRAPH_TYPEDEFS(ListDigraph);
 
   242 
   222 
   243   // Read the test digraph
 
   223   // Read the test digraph
 
   244   Digraph gr;
 
   224   Digraph gr;
 
   245   Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
 
   225   Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
 
   246   Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
 
   226   Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
 
       
   227   ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
 
   247   Node v, w;
 
   228   Node v, w;
 
   248 
   229 
   249   std::istringstream input(test_lgf);
 
   230   std::istringstream input(test_lgf);
 
   250   DigraphReader<Digraph>(gr, input)
 
   231   DigraphReader<Digraph>(gr, input)
 
   251     .arcMap("cost", c)
 
   232     .arcMap("cost", c)
 
   257     .nodeMap("sup3", s3)
 
   238     .nodeMap("sup3", s3)
 
   258     .node("source", v)
 
   239     .node("source", v)
 
   259     .node("target", w)
 
   240     .node("target", w)
 
   260     .run();
 
   241     .run();
 
   261 
   242 
   262 /*
 
   243   // A. Test NetworkSimplex with the default pivot rule
 
   263   // A. Test CapacityScaling with scaling
 
       
   264   {
 
   244   {
 
   265     CapacityScaling<Digraph> mcf1(gr, u, c, s1);
 
   245     NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
 
   266     CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
 
   246                             mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
 
   267     CapacityScaling<Digraph> mcf3(gr, u, c, s3);
 
   247 
   268     CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
 
   248     checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
 
   269     CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
 
   249              gr, l1, u, c, s1, true,  5240, "#A1");
 
   270     CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
 
   250     checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
 
   271 
   251              gr, l1, u, c, s2, true,  7620, "#A2");
 
   272     checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true,  5240, "#A1");
 
   252     checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
 
   273     checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true,  7620, "#A2");
 
   253              gr, l2, u, c, s1, true,  5970, "#A3");
 
   274     checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true,     0, "#A3");
 
   254     checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
 
   275     checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true,  5970, "#A4");
 
   255              gr, l2, u, c, s2, true,  8010, "#A4");
 
   276     checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true,  8010, "#A5");
 
   256     checkMcf(mcf5, mcf5.supplyMap(s1).run(),
 
   277     checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false,    0, "#A6");
 
   257              gr, l1, cu, cc, s1, true,  74, "#A5");
 
   278   }
 
   258     checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
 
   279 
   259              gr, l2, cu, cc, s2, true,  94, "#A6");
 
   280   // B. Test CapacityScaling without scaling
 
   260     checkMcf(mcf7, mcf7.run(),
 
       
   261              gr, l1, cu, cc, s3, true,   0, "#A7");
 
       
   262     checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
 
       
   263              gr, l2, u, cc, s3, false,   0, "#A8");
 
       
   264   }
 
       
   265 
       
   266   // B. Test NetworkSimplex with each pivot rule
 
   281   {
 
   267   {
 
   282     CapacityScaling<Digraph> mcf1(gr, u, c, s1);
 
   268     NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
 
   283     CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
 
   269     NetworkSimplex<Digraph>::PivotRule pr;
 
   284     CapacityScaling<Digraph> mcf3(gr, u, c, s3);
 
   270 
   285     CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
 
   271     pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
 
   286     CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
 
   272     checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
 
   287     CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
 
   273              gr, l2, u, c, s1, true,  5970, "#B1");
 
   288 
   274     pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
 
   289     checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true,  5240, "#B1");
 
   275     checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
 
   290     checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true,  7620, "#B2");
 
   276              gr, l2, u, c, s1, true,  5970, "#B2");
 
   291     checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true,     0, "#B3");
 
   277     pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
 
   292     checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true,  5970, "#B4");
 
   278     checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
 
   293     checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true,  8010, "#B5");
 
   279              gr, l2, u, c, s1, true,  5970, "#B3");
 
   294     checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false,    0, "#B6");
 
   280     pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
 
   295   }
 
   281     checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
 
   296 
   282              gr, l2, u, c, s1, true,  5970, "#B4");
 
   297   // C. Test CostScaling using partial augment-relabel method
 
   283     pr = NetworkSimplex<Digraph>::ALTERING_LIST;
 
   298   {
 
   284     checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
 
   299     CostScaling<Digraph> mcf1(gr, u, c, s1);
 
   285              gr, l2, u, c, s1, true,  5970, "#B5");
 
   300     CostScaling<Digraph> mcf2(gr, u, c, v, w, 27);
 
   286   }
 
   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 
   287 
   454   return 0;
 
   288   return 0;
 
   455 }
 
   289 }
lemon-main