1.1 --- a/test/min_cost_flow_test.cc Thu Feb 28 02:57:36 2008 +0000
1.2 +++ b/test/min_cost_flow_test.cc Thu Feb 28 02:58:26 2008 +0000
1.3 @@ -17,112 +17,313 @@
1.4 */
1.5
1.6 #include <iostream>
1.7 +#include <fstream>
1.8 +
1.9 +#include <lemon/list_graph.h>
1.10 +#include <lemon/smart_graph.h>
1.11 +#include <lemon/graph_reader.h>
1.12 +#include <lemon/dimacs.h>
1.13 +#include <lemon/time_measure.h>
1.14 +
1.15 +#include <lemon/cycle_canceling.h>
1.16 +#include <lemon/capacity_scaling.h>
1.17 +#include <lemon/cost_scaling.h>
1.18 +#include <lemon/network_simplex.h>
1.19 +
1.20 +#include <lemon/min_cost_flow.h>
1.21 +#include <lemon/min_cost_max_flow.h>
1.22 +
1.23 #include "test_tools.h"
1.24 -#include <lemon/list_graph.h>
1.25 -#include <lemon/ssp_min_cost_flow.h>
1.26 -//#include <path.h>
1.27 -//#include <maps.h>
1.28
1.29 using namespace lemon;
1.30
1.31 +// Checks the feasibility of a flow
1.32 +template < typename Graph, typename LowerMap, typename CapacityMap,
1.33 + typename SupplyMap, typename FlowMap >
1.34 +bool checkFlow( const Graph& gr,
1.35 + const LowerMap& lower, const CapacityMap& upper,
1.36 + const SupplyMap& supply, const FlowMap& flow )
1.37 +{
1.38 + GRAPH_TYPEDEFS(typename Graph);
1.39 + for (EdgeIt e(gr); e != INVALID; ++e)
1.40 + if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
1.41
1.42 -bool passed = true;
1.43 -/*
1.44 -void check(bool rc, char *msg="") {
1.45 - passed = passed && rc;
1.46 - if(!rc) {
1.47 - std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
1.48 -
1.49 + for (NodeIt n(gr); n != INVALID; ++n) {
1.50 + typename SupplyMap::Value sum = 0;
1.51 + for (OutEdgeIt e(gr, n); e != INVALID; ++e)
1.52 + sum += flow[e];
1.53 + for (InEdgeIt e(gr, n); e != INVALID; ++e)
1.54 + sum -= flow[e];
1.55 + if (sum != supply[n]) return false;
1.56 + }
1.57
1.58 + return true;
1.59 +}
1.60 +
1.61 +// Checks the optimalitiy of a flow
1.62 +template < typename Graph, typename LowerMap, typename CapacityMap,
1.63 + typename CostMap, typename FlowMap, typename PotentialMap >
1.64 +bool checkOptimality( const Graph& gr, const LowerMap& lower,
1.65 + const CapacityMap& upper, const CostMap& cost,
1.66 + const FlowMap& flow, const PotentialMap& pi )
1.67 +{
1.68 + GRAPH_TYPEDEFS(typename Graph);
1.69 + // Checking the Complementary Slackness optimality condition
1.70 + bool opt = true;
1.71 + for (EdgeIt e(gr); e != INVALID; ++e) {
1.72 + typename CostMap::Value red_cost =
1.73 + cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
1.74 + opt = red_cost == 0 ||
1.75 + (red_cost > 0 && flow[e] == lower[e]) ||
1.76 + (red_cost < 0 && flow[e] == upper[e]);
1.77 + if (!opt) break;
1.78 + }
1.79 + return opt;
1.80 +}
1.81 +
1.82 +// Runs a minimum cost flow algorithm and checks the results
1.83 +template < typename MinCostFlowImpl, typename Graph,
1.84 + typename LowerMap, typename CapacityMap,
1.85 + typename CostMap, typename SupplyMap >
1.86 +void checkMcf( std::string test_id,
1.87 + const MinCostFlowImpl& mcf, const Graph& gr,
1.88 + const LowerMap& lower, const CapacityMap& upper,
1.89 + const CostMap& cost, const SupplyMap& supply,
1.90 + bool mcf_result, bool result,
1.91 + typename CostMap::Value total )
1.92 +{
1.93 + check(mcf_result == result, "Wrong result " + test_id);
1.94 + if (result) {
1.95 + check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
1.96 + "The flow is not feasible " + test_id);
1.97 + check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
1.98 + check(checkOptimality(gr, lower, upper, cost, mcf.flowMap(), mcf.potentialMap()),
1.99 + "Wrong potentials " + test_id);
1.100 }
1.101 }
1.102 -*/
1.103 -
1.104
1.105 int main()
1.106 {
1.107 - typedef ListGraph Graph;
1.108 - typedef Graph::Node Node;
1.109 - typedef Graph::Edge Edge;
1.110 + // Various tests on a small graph
1.111 + {
1.112 + typedef ListGraph Graph;
1.113 + GRAPH_TYPEDEFS(ListGraph);
1.114
1.115 - Graph graph;
1.116 + // Reading the test graph
1.117 + Graph gr;
1.118 + Graph::EdgeMap<int> c(gr), l1(gr), l2(gr), u(gr);
1.119 + Graph::NodeMap<int> s1(gr), s2(gr), s3(gr);
1.120 + Node v, w;
1.121
1.122 - //Ahuja könyv példája
1.123 + std::string fname;
1.124 + if(getenv("srcdir"))
1.125 + fname = std::string(getenv("srcdir"));
1.126 + else fname = ".";
1.127 + fname += "/test/min_cost_flow_test.lgf";
1.128
1.129 - Node s=graph.addNode();
1.130 - Node v1=graph.addNode();
1.131 - Node v2=graph.addNode();
1.132 - Node v3=graph.addNode();
1.133 - Node v4=graph.addNode();
1.134 - Node v5=graph.addNode();
1.135 - Node t=graph.addNode();
1.136 + std::ifstream input(fname.c_str());
1.137 + check(input, "Input file '" << fname << "' not found");
1.138 + GraphReader<Graph>(input, gr).
1.139 + readEdgeMap("cost", c).
1.140 + readEdgeMap("capacity", u).
1.141 + readEdgeMap("lower1", l1).
1.142 + readEdgeMap("lower2", l2).
1.143 + readNodeMap("supply1", s1).
1.144 + readNodeMap("supply2", s2).
1.145 + readNodeMap("supply3", s3).
1.146 + readNode("source", v).
1.147 + readNode("target", w).
1.148 + run();
1.149 + input.close();
1.150
1.151 - Edge s_v1=graph.addEdge(s, v1);
1.152 - Edge v1_v2=graph.addEdge(v1, v2);
1.153 - Edge s_v3=graph.addEdge(s, v3);
1.154 - Edge v2_v4=graph.addEdge(v2, v4);
1.155 - Edge v2_v5=graph.addEdge(v2, v5);
1.156 - Edge v3_v5=graph.addEdge(v3, v5);
1.157 - Edge v4_t=graph.addEdge(v4, t);
1.158 - Edge v5_t=graph.addEdge(v5, t);
1.159 -
1.160 + // Testing CapacityScaling (scaling enabled)
1.161 + {
1.162 + CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#A1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.163 + CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#A2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.164 + CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#A3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.165 + CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#A4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.166 + CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#A5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.167 + CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#A6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.168 + }
1.169 + // Testing CapacityScaling (scaling disabled)
1.170 + {
1.171 + CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#B1",mcf1,gr,l1,u,c,s1,mcf1.run(false),true, 0);
1.172 + CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#B2",mcf2,gr,l1,u,c,s2,mcf2.run(false),true, 5240);
1.173 + CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#B3",mcf3,gr,l1,u,c,s3,mcf3.run(false),true, 7620);
1.174 + CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#B4",mcf4,gr,l2,u,c,s1,mcf4.run(false),false, 0);
1.175 + CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#B5",mcf5,gr,l2,u,c,s2,mcf5.run(false),true, 5970);
1.176 + CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#B6",mcf6,gr,l2,u,c,s3,mcf6.run(false),true, 8010);
1.177 + }
1.178
1.179 - Graph::EdgeMap<int> length(graph);
1.180 + // Testing CostScaling
1.181 + {
1.182 + CostScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#C1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.183 + CostScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#C2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.184 + CostScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#C3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.185 + CostScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#C4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.186 + CostScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#C5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.187 + CostScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#C6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.188 + }
1.189
1.190 - length.set(s_v1, 6);
1.191 - length.set(v1_v2, 4);
1.192 - length.set(s_v3, 10);
1.193 - length.set(v2_v4, 5);
1.194 - length.set(v2_v5, 1);
1.195 - length.set(v3_v5, 4);
1.196 - length.set(v4_t, 8);
1.197 - length.set(v5_t, 8);
1.198 + // Testing NetworkSimplex (with the default pivot rule)
1.199 + {
1.200 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#D1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.201 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#D2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.202 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#D3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.203 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#D4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.204 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#D5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.205 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#D6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.206 + }
1.207 + // Testing NetworkSimplex (with FIRST_ELIGIBLE_PIVOT)
1.208 + {
1.209 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::FIRST_ELIGIBLE_PIVOT;
1.210 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#E1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.211 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#E2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.212 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#E3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.213 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#E4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.214 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#E5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.215 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#E6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.216 + }
1.217 + // Testing NetworkSimplex (with BEST_ELIGIBLE_PIVOT)
1.218 + {
1.219 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BEST_ELIGIBLE_PIVOT;
1.220 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#F1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.221 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#F2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.222 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#F3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.223 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#F4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.224 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#F5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.225 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#F6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.226 + }
1.227 + // Testing NetworkSimplex (with BLOCK_SEARCH_PIVOT)
1.228 + {
1.229 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BLOCK_SEARCH_PIVOT;
1.230 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#G1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.231 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#G2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.232 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#G3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.233 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#G4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.234 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#G5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.235 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#G6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.236 + }
1.237 + // Testing NetworkSimplex (with LIMITED_SEARCH_PIVOT)
1.238 + {
1.239 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::LIMITED_SEARCH_PIVOT;
1.240 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#H1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.241 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#H2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.242 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#H3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.243 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#H4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.244 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#H5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.245 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#H6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.246 + }
1.247 + // Testing NetworkSimplex (with CANDIDATE_LIST_PIVOT)
1.248 + {
1.249 + NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::CANDIDATE_LIST_PIVOT;
1.250 + NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#I1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0);
1.251 + NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#I2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
1.252 + NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#I3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
1.253 + NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#I4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0);
1.254 + NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#I5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
1.255 + NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#I6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
1.256 + }
1.257
1.258 - Graph::EdgeMap<int> capacity(graph);
1.259 + // Testing CycleCanceling (with BellmanFord)
1.260 + {
1.261 + CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#J1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.262 + CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#J2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.263 + CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#J3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.264 + CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#J4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.265 + CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#J5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.266 + CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#J6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.267 + }
1.268 + // Testing CycleCanceling (with MinMeanCycle)
1.269 + {
1.270 + CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#K1",mcf1,gr,l1,u,c,s1,mcf1.run(true),true, 0);
1.271 + CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#K2",mcf2,gr,l1,u,c,s2,mcf2.run(true),true, 5240);
1.272 + CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#K3",mcf3,gr,l1,u,c,s3,mcf3.run(true),true, 7620);
1.273 + CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#K4",mcf4,gr,l2,u,c,s1,mcf4.run(true),false, 0);
1.274 + CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#K5",mcf5,gr,l2,u,c,s2,mcf5.run(true),true, 5970);
1.275 + CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#K6",mcf6,gr,l2,u,c,s3,mcf6.run(true),true, 8010);
1.276 + }
1.277
1.278 - capacity.set(s_v1, 2);
1.279 - capacity.set(v1_v2, 2);
1.280 - capacity.set(s_v3, 1);
1.281 - capacity.set(v2_v4, 1);
1.282 - capacity.set(v2_v5, 1);
1.283 - capacity.set(v3_v5, 1);
1.284 - capacity.set(v4_t, 1);
1.285 - capacity.set(v5_t, 2);
1.286 + // Testing MinCostFlow
1.287 + {
1.288 + MinCostFlow<Graph> mcf1(gr,u,c,s1); checkMcf("#L1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0);
1.289 + MinCostFlow<Graph> mcf2(gr,u,c,s2); checkMcf("#L2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
1.290 + MinCostFlow<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#L3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
1.291 + MinCostFlow<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#L4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0);
1.292 + MinCostFlow<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#L5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
1.293 + MinCostFlow<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#L6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
1.294 + }
1.295
1.296 - // ConstMap<Edge, int> const1map(1);
1.297 - std::cout << "Mincostflows algorithm test..." << std::endl;
1.298 + // Testing MinCostMaxFlow
1.299 + {
1.300 + MinCostMaxFlow<Graph> mcmf(gr,u,c,v,w);
1.301 + mcmf.run();
1.302 + checkMcf("#M1",mcmf,gr,l1,u,c,s3,true,true,7620);
1.303 + }
1.304 + }
1.305
1.306 - SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.307 - surb_test(graph, length, capacity, s, t);
1.308 + // Benchmark test on a DIMACS network
1.309 + {
1.310 + typedef SmartGraph Graph;
1.311 + GRAPH_TYPEDEFS(SmartGraph);
1.312
1.313 - int k=1;
1.314 + // Reading the test graph
1.315 + Graph graph;
1.316 + Graph::EdgeMap<int> lower(graph), capacity(graph), cost(graph);
1.317 + Graph::NodeMap<int> supply(graph);
1.318
1.319 - surb_test.augment();
1.320 - check( surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
1.321 + std::string fname;
1.322 + if(getenv("srcdir"))
1.323 + fname = std::string(getenv("srcdir"));
1.324 + else fname = ".";
1.325 + fname += "/test/min_cost_flow_test.net";
1.326
1.327 - check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
1.328 + std::ifstream input(fname.c_str());
1.329 + check(input, "Input file '" << fname << "' not found");
1.330 + readDimacs(input, graph, lower, capacity, cost, supply);
1.331 + input.close();
1.332
1.333 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.334 -
1.335 - k=2;
1.336 -
1.337 - check( surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
1.338 + // NetworkSimplex
1.339 + {
1.340 + Timer t;
1.341 + NetworkSimplex<Graph> mcf(graph, lower, capacity, cost, supply);
1.342 + bool res = mcf.run();
1.343 + t.stop();
1.344 + checkMcf("#T3", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.345 + std::cout << "NetworkSimplex";
1.346 + std::cout << std::endl << t << std::endl;
1.347 + }
1.348 + // CapacityScaling
1.349 + {
1.350 + Timer t;
1.351 + CapacityScaling<Graph> mcf(graph, lower, capacity, cost, supply);
1.352 + bool res = mcf.run();
1.353 + t.stop();
1.354 + checkMcf("#T1", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.355 + std::cout << "CapacityScaling";
1.356 + std::cout << std::endl << t << std::endl;
1.357 + }
1.358 + // CostScaling
1.359 + {
1.360 + Timer t;
1.361 + CostScaling<Graph> mcf(graph, lower, capacity, cost, supply);
1.362 + bool res = mcf.run();
1.363 + t.stop();
1.364 + checkMcf("#T2", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.365 + std::cout << "CostScaling";
1.366 + std::cout << std::endl << t << std::endl;
1.367 + }
1.368 + // CycleCanceling
1.369 + {
1.370 + Timer t;
1.371 + CycleCanceling<Graph> mcf(graph, lower, capacity, cost, supply);
1.372 + bool res = mcf.run();
1.373 + t.stop();
1.374 + checkMcf("#T4", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
1.375 + std::cout << "CycleCanceling";
1.376 + std::cout << std::endl << t << std::endl;
1.377 + }
1.378 + }
1.379
1.380 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.381 -
1.382 - surb_test.augment();
1.383 - surb_test.augment();
1.384 - surb_test.augment();
1.385 - k=4;
1.386 -
1.387 - check( surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
1.388 -
1.389 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.390 -
1.391 -
1.392 - std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
1.393 - << std::endl;
1.394 -
1.395 - return passed ? 0 : 1;
1.396 -
1.397 + return 0;
1.398 }