Changeset 2584:84ef3c5b3698 in lemon-0.x
- Timestamp:
- 02/28/08 03:58:26 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3466
- Location:
- test
- Files:
-
- 2 added
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/min_cost_flow_test.cc
r2553 r2584 18 18 19 19 #include <iostream> 20 #include <fstream> 21 22 #include <lemon/list_graph.h> 23 #include <lemon/smart_graph.h> 24 #include <lemon/graph_reader.h> 25 #include <lemon/dimacs.h> 26 #include <lemon/time_measure.h> 27 28 #include <lemon/cycle_canceling.h> 29 #include <lemon/capacity_scaling.h> 30 #include <lemon/cost_scaling.h> 31 #include <lemon/network_simplex.h> 32 33 #include <lemon/min_cost_flow.h> 34 #include <lemon/min_cost_max_flow.h> 35 20 36 #include "test_tools.h" 21 #include <lemon/list_graph.h>22 #include <lemon/ssp_min_cost_flow.h>23 //#include <path.h>24 //#include <maps.h>25 37 26 38 using namespace lemon; 27 39 28 29 bool passed = true; 30 /* 31 void check(bool rc, char *msg="") { 32 passed = passed && rc; 33 if(!rc) { 34 std::cerr << "Test failed! ("<< msg << ")" << std::endl; \ 35 36 37 } 40 // Checks the feasibility of a flow 41 template < typename Graph, typename LowerMap, typename CapacityMap, 42 typename SupplyMap, typename FlowMap > 43 bool checkFlow( const Graph& gr, 44 const LowerMap& lower, const CapacityMap& upper, 45 const SupplyMap& supply, const FlowMap& flow ) 46 { 47 GRAPH_TYPEDEFS(typename Graph); 48 for (EdgeIt e(gr); e != INVALID; ++e) 49 if (flow[e] < lower[e] || flow[e] > upper[e]) return false; 50 51 for (NodeIt n(gr); n != INVALID; ++n) { 52 typename SupplyMap::Value sum = 0; 53 for (OutEdgeIt e(gr, n); e != INVALID; ++e) 54 sum += flow[e]; 55 for (InEdgeIt e(gr, n); e != INVALID; ++e) 56 sum -= flow[e]; 57 if (sum != supply[n]) return false; 58 } 59 60 return true; 38 61 } 39 */ 40 62 63 // Checks the optimalitiy of a flow 64 template < typename Graph, typename LowerMap, typename CapacityMap, 65 typename CostMap, typename FlowMap, typename PotentialMap > 66 bool checkOptimality( const Graph& gr, const LowerMap& lower, 67 const CapacityMap& upper, const CostMap& cost, 68 const FlowMap& flow, const PotentialMap& pi ) 69 { 70 GRAPH_TYPEDEFS(typename Graph); 71 // Checking the Complementary Slackness optimality condition 72 bool opt = true; 73 for (EdgeIt e(gr); e != INVALID; ++e) { 74 typename CostMap::Value red_cost = 75 cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; 76 opt = red_cost == 0 || 77 (red_cost > 0 && flow[e] == lower[e]) || 78 (red_cost < 0 && flow[e] == upper[e]); 79 if (!opt) break; 80 } 81 return opt; 82 } 83 84 // Runs a minimum cost flow algorithm and checks the results 85 template < typename MinCostFlowImpl, typename Graph, 86 typename LowerMap, typename CapacityMap, 87 typename CostMap, typename SupplyMap > 88 void checkMcf( std::string test_id, 89 const MinCostFlowImpl& mcf, const Graph& gr, 90 const LowerMap& lower, const CapacityMap& upper, 91 const CostMap& cost, const SupplyMap& supply, 92 bool mcf_result, bool result, 93 typename CostMap::Value total ) 94 { 95 check(mcf_result == result, "Wrong result " + test_id); 96 if (result) { 97 check(checkFlow(gr, lower, upper, supply, mcf.flowMap()), 98 "The flow is not feasible " + test_id); 99 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); 100 check(checkOptimality(gr, lower, upper, cost, mcf.flowMap(), mcf.potentialMap()), 101 "Wrong potentials " + test_id); 102 } 103 } 41 104 42 105 int main() 43 106 { 44 typedef ListGraph Graph; 45 typedef Graph::Node Node; 46 typedef Graph::Edge Edge; 47 48 Graph graph; 49 50 //Ahuja könyv példája 51 52 Node s=graph.addNode(); 53 Node v1=graph.addNode(); 54 Node v2=graph.addNode(); 55 Node v3=graph.addNode(); 56 Node v4=graph.addNode(); 57 Node v5=graph.addNode(); 58 Node t=graph.addNode(); 59 60 Edge s_v1=graph.addEdge(s, v1); 61 Edge v1_v2=graph.addEdge(v1, v2); 62 Edge s_v3=graph.addEdge(s, v3); 63 Edge v2_v4=graph.addEdge(v2, v4); 64 Edge v2_v5=graph.addEdge(v2, v5); 65 Edge v3_v5=graph.addEdge(v3, v5); 66 Edge v4_t=graph.addEdge(v4, t); 67 Edge v5_t=graph.addEdge(v5, t); 68 69 70 Graph::EdgeMap<int> length(graph); 71 72 length.set(s_v1, 6); 73 length.set(v1_v2, 4); 74 length.set(s_v3, 10); 75 length.set(v2_v4, 5); 76 length.set(v2_v5, 1); 77 length.set(v3_v5, 4); 78 length.set(v4_t, 8); 79 length.set(v5_t, 8); 80 81 Graph::EdgeMap<int> capacity(graph); 82 83 capacity.set(s_v1, 2); 84 capacity.set(v1_v2, 2); 85 capacity.set(s_v3, 1); 86 capacity.set(v2_v4, 1); 87 capacity.set(v2_v5, 1); 88 capacity.set(v3_v5, 1); 89 capacity.set(v4_t, 1); 90 capacity.set(v5_t, 2); 91 92 // ConstMap<Edge, int> const1map(1); 93 std::cout << "Mincostflows algorithm test..." << std::endl; 94 95 SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 96 surb_test(graph, length, capacity, s, t); 97 98 int k=1; 99 100 surb_test.augment(); 101 check( surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19"); 102 103 check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19"); 104 105 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); 106 107 k=2; 108 109 check( surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41"); 110 111 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); 112 113 surb_test.augment(); 114 surb_test.augment(); 115 surb_test.augment(); 116 k=4; 117 118 check( surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64"); 119 120 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); 121 122 123 std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!") 124 << std::endl; 125 126 return passed ? 0 : 1; 127 107 // Various tests on a small graph 108 { 109 typedef ListGraph Graph; 110 GRAPH_TYPEDEFS(ListGraph); 111 112 // Reading the test graph 113 Graph gr; 114 Graph::EdgeMap<int> c(gr), l1(gr), l2(gr), u(gr); 115 Graph::NodeMap<int> s1(gr), s2(gr), s3(gr); 116 Node v, w; 117 118 std::string fname; 119 if(getenv("srcdir")) 120 fname = std::string(getenv("srcdir")); 121 else fname = "."; 122 fname += "/test/min_cost_flow_test.lgf"; 123 124 std::ifstream input(fname.c_str()); 125 check(input, "Input file '" << fname << "' not found"); 126 GraphReader<Graph>(input, gr). 127 readEdgeMap("cost", c). 128 readEdgeMap("capacity", u). 129 readEdgeMap("lower1", l1). 130 readEdgeMap("lower2", l2). 131 readNodeMap("supply1", s1). 132 readNodeMap("supply2", s2). 133 readNodeMap("supply3", s3). 134 readNode("source", v). 135 readNode("target", w). 136 run(); 137 input.close(); 138 139 // Testing CapacityScaling (scaling enabled) 140 { 141 CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#A1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); 142 CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#A2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); 143 CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#A3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); 144 CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#A4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); 145 CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#A5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); 146 CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#A6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); 147 } 148 // Testing CapacityScaling (scaling disabled) 149 { 150 CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#B1",mcf1,gr,l1,u,c,s1,mcf1.run(false),true, 0); 151 CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#B2",mcf2,gr,l1,u,c,s2,mcf2.run(false),true, 5240); 152 CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#B3",mcf3,gr,l1,u,c,s3,mcf3.run(false),true, 7620); 153 CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#B4",mcf4,gr,l2,u,c,s1,mcf4.run(false),false, 0); 154 CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#B5",mcf5,gr,l2,u,c,s2,mcf5.run(false),true, 5970); 155 CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#B6",mcf6,gr,l2,u,c,s3,mcf6.run(false),true, 8010); 156 } 157 158 // Testing CostScaling 159 { 160 CostScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#C1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); 161 CostScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#C2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); 162 CostScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#C3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); 163 CostScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#C4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); 164 CostScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#C5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); 165 CostScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#C6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); 166 } 167 168 // Testing NetworkSimplex (with the default pivot rule) 169 { 170 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#D1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); 171 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#D2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); 172 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#D3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); 173 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#D4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); 174 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#D5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); 175 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#D6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); 176 } 177 // Testing NetworkSimplex (with FIRST_ELIGIBLE_PIVOT) 178 { 179 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::FIRST_ELIGIBLE_PIVOT; 180 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#E1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); 181 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#E2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); 182 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#E3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); 183 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#E4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); 184 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#E5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); 185 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#E6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); 186 } 187 // Testing NetworkSimplex (with BEST_ELIGIBLE_PIVOT) 188 { 189 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BEST_ELIGIBLE_PIVOT; 190 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#F1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); 191 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#F2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); 192 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#F3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); 193 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#F4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); 194 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#F5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); 195 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#F6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); 196 } 197 // Testing NetworkSimplex (with BLOCK_SEARCH_PIVOT) 198 { 199 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BLOCK_SEARCH_PIVOT; 200 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#G1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); 201 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#G2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); 202 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#G3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); 203 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#G4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); 204 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#G5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); 205 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#G6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); 206 } 207 // Testing NetworkSimplex (with LIMITED_SEARCH_PIVOT) 208 { 209 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::LIMITED_SEARCH_PIVOT; 210 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#H1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); 211 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#H2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); 212 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#H3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); 213 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#H4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); 214 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#H5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); 215 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#H6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); 216 } 217 // Testing NetworkSimplex (with CANDIDATE_LIST_PIVOT) 218 { 219 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::CANDIDATE_LIST_PIVOT; 220 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#I1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); 221 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#I2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); 222 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#I3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); 223 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#I4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); 224 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#I5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); 225 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#I6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); 226 } 227 228 // Testing CycleCanceling (with BellmanFord) 229 { 230 CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#J1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); 231 CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#J2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); 232 CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#J3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); 233 CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#J4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); 234 CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#J5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); 235 CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#J6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); 236 } 237 // Testing CycleCanceling (with MinMeanCycle) 238 { 239 CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#K1",mcf1,gr,l1,u,c,s1,mcf1.run(true),true, 0); 240 CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#K2",mcf2,gr,l1,u,c,s2,mcf2.run(true),true, 5240); 241 CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#K3",mcf3,gr,l1,u,c,s3,mcf3.run(true),true, 7620); 242 CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#K4",mcf4,gr,l2,u,c,s1,mcf4.run(true),false, 0); 243 CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#K5",mcf5,gr,l2,u,c,s2,mcf5.run(true),true, 5970); 244 CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#K6",mcf6,gr,l2,u,c,s3,mcf6.run(true),true, 8010); 245 } 246 247 // Testing MinCostFlow 248 { 249 MinCostFlow<Graph> mcf1(gr,u,c,s1); checkMcf("#L1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); 250 MinCostFlow<Graph> mcf2(gr,u,c,s2); checkMcf("#L2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); 251 MinCostFlow<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#L3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); 252 MinCostFlow<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#L4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); 253 MinCostFlow<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#L5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); 254 MinCostFlow<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#L6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); 255 } 256 257 // Testing MinCostMaxFlow 258 { 259 MinCostMaxFlow<Graph> mcmf(gr,u,c,v,w); 260 mcmf.run(); 261 checkMcf("#M1",mcmf,gr,l1,u,c,s3,true,true,7620); 262 } 263 } 264 265 // Benchmark test on a DIMACS network 266 { 267 typedef SmartGraph Graph; 268 GRAPH_TYPEDEFS(SmartGraph); 269 270 // Reading the test graph 271 Graph graph; 272 Graph::EdgeMap<int> lower(graph), capacity(graph), cost(graph); 273 Graph::NodeMap<int> supply(graph); 274 275 std::string fname; 276 if(getenv("srcdir")) 277 fname = std::string(getenv("srcdir")); 278 else fname = "."; 279 fname += "/test/min_cost_flow_test.net"; 280 281 std::ifstream input(fname.c_str()); 282 check(input, "Input file '" << fname << "' not found"); 283 readDimacs(input, graph, lower, capacity, cost, supply); 284 input.close(); 285 286 // NetworkSimplex 287 { 288 Timer t; 289 NetworkSimplex<Graph> mcf(graph, lower, capacity, cost, supply); 290 bool res = mcf.run(); 291 t.stop(); 292 checkMcf("#T3", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); 293 std::cout << "NetworkSimplex"; 294 std::cout << std::endl << t << std::endl; 295 } 296 // CapacityScaling 297 { 298 Timer t; 299 CapacityScaling<Graph> mcf(graph, lower, capacity, cost, supply); 300 bool res = mcf.run(); 301 t.stop(); 302 checkMcf("#T1", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); 303 std::cout << "CapacityScaling"; 304 std::cout << std::endl << t << std::endl; 305 } 306 // CostScaling 307 { 308 Timer t; 309 CostScaling<Graph> mcf(graph, lower, capacity, cost, supply); 310 bool res = mcf.run(); 311 t.stop(); 312 checkMcf("#T2", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); 313 std::cout << "CostScaling"; 314 std::cout << std::endl << t << std::endl; 315 } 316 // CycleCanceling 317 { 318 Timer t; 319 CycleCanceling<Graph> mcf(graph, lower, capacity, cost, supply); 320 bool res = mcf.run(); 321 t.stop(); 322 checkMcf("#T4", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); 323 std::cout << "CycleCanceling"; 324 std::cout << std::endl << t << std::endl; 325 } 326 } 327 328 return 0; 128 329 }
Note: See TracChangeset
for help on using the changeset viewer.