diff -r cb8270a98660 -r e01957e96c67 test/min_cost_flow_test.cc --- a/test/min_cost_flow_test.cc Wed Apr 29 16:15:29 2009 +0100 +++ b/test/min_cost_flow_test.cc Wed Apr 29 19:22:14 2009 +0100 @@ -18,6 +18,7 @@ #include #include +#include #include #include @@ -33,57 +34,57 @@ char test_lgf[] = "@nodes\n" - "label sup1 sup2 sup3 sup4 sup5\n" - " 1 20 27 0 20 30\n" - " 2 -4 0 0 -8 -3\n" - " 3 0 0 0 0 0\n" - " 4 0 0 0 0 0\n" - " 5 9 0 0 6 11\n" - " 6 -6 0 0 -5 -6\n" - " 7 0 0 0 0 0\n" - " 8 0 0 0 0 3\n" - " 9 3 0 0 0 0\n" - " 10 -2 0 0 -7 -2\n" - " 11 0 0 0 -10 0\n" - " 12 -20 -27 0 -30 -20\n" - "\n" + "label sup1 sup2 sup3 sup4 sup5 sup6\n" + " 1 20 27 0 30 20 30\n" + " 2 -4 0 0 0 -8 -3\n" + " 3 0 0 0 0 0 0\n" + " 4 0 0 0 0 0 0\n" + " 5 9 0 0 0 6 11\n" + " 6 -6 0 0 0 -5 -6\n" + " 7 0 0 0 0 0 0\n" + " 8 0 0 0 0 0 3\n" + " 9 3 0 0 0 0 0\n" + " 10 -2 0 0 0 -7 -2\n" + " 11 0 0 0 0 -10 0\n" + " 12 -20 -27 0 -30 -30 -20\n" + "\n" "@arcs\n" - " cost cap low1 low2\n" - " 1 2 70 11 0 8\n" - " 1 3 150 3 0 1\n" - " 1 4 80 15 0 2\n" - " 2 8 80 12 0 0\n" - " 3 5 140 5 0 3\n" - " 4 6 60 10 0 1\n" - " 4 7 80 2 0 0\n" - " 4 8 110 3 0 0\n" - " 5 7 60 14 0 0\n" - " 5 11 120 12 0 0\n" - " 6 3 0 3 0 0\n" - " 6 9 140 4 0 0\n" - " 6 10 90 8 0 0\n" - " 7 1 30 5 0 0\n" - " 8 12 60 16 0 4\n" - " 9 12 50 6 0 0\n" - "10 12 70 13 0 5\n" - "10 2 100 7 0 0\n" - "10 7 60 10 0 0\n" - "11 10 20 14 0 6\n" - "12 11 30 10 0 0\n" + " cost cap low1 low2 low3\n" + " 1 2 70 11 0 8 8\n" + " 1 3 150 3 0 1 0\n" + " 1 4 80 15 0 2 2\n" + " 2 8 80 12 0 0 0\n" + " 3 5 140 5 0 3 1\n" + " 4 6 60 10 0 1 0\n" + " 4 7 80 2 0 0 0\n" + " 4 8 110 3 0 0 0\n" + " 5 7 60 14 0 0 0\n" + " 5 11 120 12 0 0 0\n" + " 6 3 0 3 0 0 0\n" + " 6 9 140 4 0 0 0\n" + " 6 10 90 8 0 0 0\n" + " 7 1 30 5 0 0 -5\n" + " 8 12 60 16 0 4 3\n" + " 9 12 50 6 0 0 0\n" + "10 12 70 13 0 5 2\n" + "10 2 100 7 0 0 0\n" + "10 7 60 10 0 0 -3\n" + "11 10 20 14 0 6 -20\n" + "12 11 30 10 0 0 -10\n" "\n" "@attributes\n" "source 1\n" "target 12\n"; -enum ProblemType { +enum SupplyType { EQ, GEQ, LEQ }; // Check the interface of an MCF algorithm -template +template class McfClassConcept { public: @@ -94,53 +95,46 @@ checkConcept(); MCF mcf(g); + const MCF& const_mcf = mcf; b = mcf.reset() .lowerMap(lower) .upperMap(upper) - .capacityMap(upper) - .boundMaps(lower, upper) .costMap(cost) .supplyMap(sup) .stSupply(n, n, k) - .flowMap(flow) - .potentialMap(pot) .run(); - - const MCF& const_mcf = mcf; - const typename MCF::FlowMap &fm = const_mcf.flowMap(); - const typename MCF::PotentialMap &pm = const_mcf.potentialMap(); - - v = const_mcf.totalCost(); - double x = const_mcf.template totalCost(); + c = const_mcf.totalCost(); + x = const_mcf.template totalCost(); v = const_mcf.flow(a); - v = const_mcf.potential(n); - - ignore_unused_variable_warning(fm); - ignore_unused_variable_warning(pm); - ignore_unused_variable_warning(x); + c = const_mcf.potential(n); + const_mcf.flowMap(fm); + const_mcf.potentialMap(pm); } typedef typename GR::Node Node; typedef typename GR::Arc Arc; - typedef concepts::ReadMap NM; - typedef concepts::ReadMap FAM; + typedef concepts::ReadMap NM; + typedef concepts::ReadMap VAM; typedef concepts::ReadMap CAM; + typedef concepts::WriteMap FlowMap; + typedef concepts::WriteMap PotMap; const GR &g; - const FAM &lower; - const FAM &upper; + const VAM &lower; + const VAM &upper; const CAM &cost; const NM ⊃ const Node &n; const Arc &a; - const Flow &k; - Flow v; + const Value &k; + FlowMap fm; + PotMap pm; bool b; - - typename MCF::FlowMap &flow; - typename MCF::PotentialMap &pot; + double x; + typename MCF::Value v; + typename MCF::Cost c; }; }; @@ -151,7 +145,7 @@ typename SM, typename FM > bool checkFlow( const GR& gr, const LM& lower, const UM& upper, const SM& supply, const FM& flow, - ProblemType type = EQ ) + SupplyType type = EQ ) { TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -208,21 +202,25 @@ // Run a minimum cost flow algorithm and check the results template < typename MCF, typename GR, typename LM, typename UM, - typename CM, typename SM > -void checkMcf( const MCF& mcf, bool mcf_result, + typename CM, typename SM, + typename PT > +void checkMcf( const MCF& mcf, PT mcf_result, const GR& gr, const LM& lower, const UM& upper, const CM& cost, const SM& supply, - bool result, typename CM::Value total, + PT result, bool optimal, typename CM::Value total, const std::string &test_id = "", - ProblemType type = EQ ) + SupplyType type = EQ ) { check(mcf_result == result, "Wrong result " + test_id); - if (result) { - check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type), + if (optimal) { + typename GR::template ArcMap flow(gr); + typename GR::template NodeMap pi(gr); + mcf.flowMap(flow); + mcf.potentialMap(pi); + check(checkFlow(gr, lower, upper, supply, flow, type), "The flow is not feasible " + test_id); check(mcf.totalCost() == total, "The flow is not optimal " + test_id); - check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(), - mcf.potentialMap()), + check(checkPotential(gr, lower, upper, cost, supply, flow, pi), "Wrong potentials " + test_id); } } @@ -231,11 +229,13 @@ { // Check the interfaces { - typedef int Flow; - typedef int Cost; typedef concepts::Digraph GR; - checkConcept< McfClassConcept, - NetworkSimplex >(); + checkConcept< McfClassConcept, + NetworkSimplex >(); + checkConcept< McfClassConcept, + NetworkSimplex >(); + checkConcept< McfClassConcept, + NetworkSimplex >(); } // Run various MCF tests @@ -244,8 +244,8 @@ // Read the test digraph Digraph gr; - Digraph::ArcMap c(gr), l1(gr), l2(gr), u(gr); - Digraph::NodeMap s1(gr), s2(gr), s3(gr), s4(gr), s5(gr); + Digraph::ArcMap c(gr), l1(gr), l2(gr), l3(gr), u(gr); + Digraph::NodeMap s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); ConstMap cc(1), cu(std::numeric_limits::max()); Node v, w; @@ -255,14 +255,56 @@ .arcMap("cap", u) .arcMap("low1", l1) .arcMap("low2", l2) + .arcMap("low3", l3) .nodeMap("sup1", s1) .nodeMap("sup2", s2) .nodeMap("sup3", s3) .nodeMap("sup4", s4) .nodeMap("sup5", s5) + .nodeMap("sup6", s6) .node("source", v) .node("target", w) .run(); + + // Build a test digraph for testing negative costs + Digraph ngr; + Node n1 = ngr.addNode(); + Node n2 = ngr.addNode(); + Node n3 = ngr.addNode(); + Node n4 = ngr.addNode(); + Node n5 = ngr.addNode(); + Node n6 = ngr.addNode(); + Node n7 = ngr.addNode(); + + Arc a1 = ngr.addArc(n1, n2); + Arc a2 = ngr.addArc(n1, n3); + Arc a3 = ngr.addArc(n2, n4); + Arc a4 = ngr.addArc(n3, n4); + Arc a5 = ngr.addArc(n3, n2); + Arc a6 = ngr.addArc(n5, n3); + Arc a7 = ngr.addArc(n5, n6); + Arc a8 = ngr.addArc(n6, n7); + Arc a9 = ngr.addArc(n7, n5); + + Digraph::ArcMap nc(ngr), nl1(ngr, 0), nl2(ngr, 0); + ConstMap nu1(std::numeric_limits::max()), nu2(5000); + Digraph::NodeMap ns(ngr, 0); + + nl2[a7] = 1000; + nl2[a8] = -1000; + + ns[n1] = 100; + ns[n4] = -100; + + nc[a1] = 100; + nc[a2] = 30; + nc[a3] = 20; + nc[a4] = 80; + nc[a5] = 50; + nc[a6] = 10; + nc[a7] = 80; + nc[a8] = 30; + nc[a9] = -120; // A. Test NetworkSimplex with the default pivot rule { @@ -271,63 +313,77 @@ // Check the equality form mcf.upperMap(u).costMap(c); checkMcf(mcf, mcf.supplyMap(s1).run(), - gr, l1, u, c, s1, true, 5240, "#A1"); + gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1"); checkMcf(mcf, mcf.stSupply(v, w, 27).run(), - gr, l1, u, c, s2, true, 7620, "#A2"); + gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2"); mcf.lowerMap(l2); checkMcf(mcf, mcf.supplyMap(s1).run(), - gr, l2, u, c, s1, true, 5970, "#A3"); + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3"); checkMcf(mcf, mcf.stSupply(v, w, 27).run(), - gr, l2, u, c, s2, true, 8010, "#A4"); + gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4"); mcf.reset(); checkMcf(mcf, mcf.supplyMap(s1).run(), - gr, l1, cu, cc, s1, true, 74, "#A5"); + gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5"); checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), - gr, l2, cu, cc, s2, true, 94, "#A6"); + gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6"); mcf.reset(); checkMcf(mcf, mcf.run(), - gr, l1, cu, cc, s3, true, 0, "#A7"); - checkMcf(mcf, mcf.boundMaps(l2, u).run(), - gr, l2, u, cc, s3, false, 0, "#A8"); + gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7"); + checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(), + gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8"); + mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); + checkMcf(mcf, mcf.run(), + gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9"); // Check the GEQ form - mcf.reset().upperMap(u).costMap(c).supplyMap(s4); + mcf.reset().upperMap(u).costMap(c).supplyMap(s5); checkMcf(mcf, mcf.run(), - gr, l1, u, c, s4, true, 3530, "#A9", GEQ); - mcf.problemType(mcf.GEQ); + gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ); + mcf.supplyType(mcf.GEQ); checkMcf(mcf, mcf.lowerMap(l2).run(), - gr, l2, u, c, s4, true, 4540, "#A10", GEQ); - mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5); + gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ); + mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6); checkMcf(mcf, mcf.run(), - gr, l2, u, c, s5, false, 0, "#A11", GEQ); + gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ); // Check the LEQ form - mcf.reset().problemType(mcf.LEQ); - mcf.upperMap(u).costMap(c).supplyMap(s5); + mcf.reset().supplyType(mcf.LEQ); + mcf.upperMap(u).costMap(c).supplyMap(s6); checkMcf(mcf, mcf.run(), - gr, l1, u, c, s5, true, 5080, "#A12", LEQ); + gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ); checkMcf(mcf, mcf.lowerMap(l2).run(), - gr, l2, u, c, s5, true, 5930, "#A13", LEQ); - mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4); + gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); + mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5); checkMcf(mcf, mcf.run(), - gr, l2, u, c, s4, false, 0, "#A14", LEQ); + gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); + + // Check negative costs + NetworkSimplex nmcf(ngr); + nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns); + checkMcf(nmcf, nmcf.run(), + ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16"); + checkMcf(nmcf, nmcf.upperMap(nu2).run(), + ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17"); + nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns); + checkMcf(nmcf, nmcf.run(), + ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18"); } // B. Test NetworkSimplex with each pivot rule { NetworkSimplex mcf(gr); - mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2); + mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2); checkMcf(mcf, mcf.run(NetworkSimplex::FIRST_ELIGIBLE), - gr, l2, u, c, s1, true, 5970, "#B1"); + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1"); checkMcf(mcf, mcf.run(NetworkSimplex::BEST_ELIGIBLE), - gr, l2, u, c, s1, true, 5970, "#B2"); + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2"); checkMcf(mcf, mcf.run(NetworkSimplex::BLOCK_SEARCH), - gr, l2, u, c, s1, true, 5970, "#B3"); + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3"); checkMcf(mcf, mcf.run(NetworkSimplex::CANDIDATE_LIST), - gr, l2, u, c, s1, true, 5970, "#B4"); + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4"); checkMcf(mcf, mcf.run(NetworkSimplex::ALTERING_LIST), - gr, l2, u, c, s1, true, 5970, "#B5"); + gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5"); } return 0;