Changes in test/min_cost_flow_test.cc [642:111698359429:615:e3d9bff447ed] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/min_cost_flow_test.cc
r642 r615 19 19 #include <iostream> 20 20 #include <fstream> 21 #include <limits>22 21 23 22 #include <lemon/list_graph.h> … … 35 34 char test_lgf[] = 36 35 "@nodes\n" 37 "label sup1 sup2 sup3 sup4 sup5 sup6\n"38 " 1 20 27 0 3020 30\n"39 " 2 -4 0 0 0-8 -3\n"40 " 3 0 0 0 0 0 0\n"41 " 4 0 0 0 0 0 0\n"42 " 5 9 0 0 06 11\n"43 " 6 -6 0 0 0-5 -6\n"44 " 7 0 0 0 0 0 0\n"45 " 8 0 0 0 0 03\n"46 " 9 3 0 0 0 0 0\n"47 " 10 -2 0 0 0-7 -2\n"48 " 11 0 0 0 0-10 0\n"49 " 12 -20 -27 0 -30 - 30 -20\n"50 "\n" 36 "label sup1 sup2 sup3 sup4 sup5\n" 37 " 1 20 27 0 20 30\n" 38 " 2 -4 0 0 -8 -3\n" 39 " 3 0 0 0 0 0\n" 40 " 4 0 0 0 0 0\n" 41 " 5 9 0 0 6 11\n" 42 " 6 -6 0 0 -5 -6\n" 43 " 7 0 0 0 0 0\n" 44 " 8 0 0 0 0 3\n" 45 " 9 3 0 0 0 0\n" 46 " 10 -2 0 0 -7 -2\n" 47 " 11 0 0 0 -10 0\n" 48 " 12 -20 -27 0 -30 -20\n" 49 "\n" 51 50 "@arcs\n" 52 " cost cap low1 low2 low3\n"53 " 1 2 70 11 0 8 8\n"54 " 1 3 150 3 0 1 0\n"55 " 1 4 80 15 0 2 2\n"56 " 2 8 80 12 0 0 0\n"57 " 3 5 140 5 0 3 1\n"58 " 4 6 60 10 0 1 0\n"59 " 4 7 80 2 0 0 0\n"60 " 4 8 110 3 0 0 0\n"61 " 5 7 60 14 0 0 0\n"62 " 5 11 120 12 0 0 0\n"63 " 6 3 0 3 0 0 0\n"64 " 6 9 140 4 0 0 0\n"65 " 6 10 90 8 0 0 0\n"66 " 7 1 30 5 0 0 -5\n"67 " 8 12 60 16 0 4 3\n"68 " 9 12 50 6 0 0 0\n"69 "10 12 70 13 0 5 2\n"70 "10 2 100 7 0 0 0\n"71 "10 7 60 10 0 0 -3\n"72 "11 10 20 14 0 6 -20\n"73 "12 11 30 10 0 0 -10\n"51 " cost cap low1 low2\n" 52 " 1 2 70 11 0 8\n" 53 " 1 3 150 3 0 1\n" 54 " 1 4 80 15 0 2\n" 55 " 2 8 80 12 0 0\n" 56 " 3 5 140 5 0 3\n" 57 " 4 6 60 10 0 1\n" 58 " 4 7 80 2 0 0\n" 59 " 4 8 110 3 0 0\n" 60 " 5 7 60 14 0 0\n" 61 " 5 11 120 12 0 0\n" 62 " 6 3 0 3 0 0\n" 63 " 6 9 140 4 0 0\n" 64 " 6 10 90 8 0 0\n" 65 " 7 1 30 5 0 0\n" 66 " 8 12 60 16 0 4\n" 67 " 9 12 50 6 0 0\n" 68 "10 12 70 13 0 5\n" 69 "10 2 100 7 0 0\n" 70 "10 7 60 10 0 0\n" 71 "11 10 20 14 0 6\n" 72 "12 11 30 10 0 0\n" 74 73 "\n" 75 74 "@attributes\n" … … 78 77 79 78 80 enum SupplyType {79 enum ProblemType { 81 80 EQ, 82 81 GEQ, … … 85 84 86 85 // Check the interface of an MCF algorithm 87 template <typename GR, typename Value, typename Cost>86 template <typename GR, typename Flow, typename Cost> 88 87 class McfClassConcept 89 88 { … … 96 95 97 96 MCF mcf(g); 98 const MCF& const_mcf = mcf;99 97 100 98 b = mcf.reset() 101 99 .lowerMap(lower) 102 100 .upperMap(upper) 101 .capacityMap(upper) 102 .boundMaps(lower, upper) 103 103 .costMap(cost) 104 104 .supplyMap(sup) 105 105 .stSupply(n, n, k) 106 .flowMap(flow) 107 .potentialMap(pot) 106 108 .run(); 107 108 c = const_mcf.totalCost(); 109 x = const_mcf.template totalCost<double>(); 109 110 const MCF& const_mcf = mcf; 111 112 const typename MCF::FlowMap &fm = const_mcf.flowMap(); 113 const typename MCF::PotentialMap &pm = const_mcf.potentialMap(); 114 115 v = const_mcf.totalCost(); 116 double x = const_mcf.template totalCost<double>(); 110 117 v = const_mcf.flow(a); 111 c = const_mcf.potential(n); 112 const_mcf.flowMap(fm); 113 const_mcf.potentialMap(pm); 118 v = const_mcf.potential(n); 119 120 ignore_unused_variable_warning(fm); 121 ignore_unused_variable_warning(pm); 122 ignore_unused_variable_warning(x); 114 123 } 115 124 116 125 typedef typename GR::Node Node; 117 126 typedef typename GR::Arc Arc; 118 typedef concepts::ReadMap<Node, Value> NM;119 typedef concepts::ReadMap<Arc, Value> VAM;127 typedef concepts::ReadMap<Node, Flow> NM; 128 typedef concepts::ReadMap<Arc, Flow> FAM; 120 129 typedef concepts::ReadMap<Arc, Cost> CAM; 121 typedef concepts::WriteMap<Arc, Value> FlowMap;122 typedef concepts::WriteMap<Node, Cost> PotMap;123 130 124 131 const GR &g; 125 const VAM &lower;126 const VAM &upper;132 const FAM &lower; 133 const FAM &upper; 127 134 const CAM &cost; 128 135 const NM ⊃ 129 136 const Node &n; 130 137 const Arc &a; 131 const Value &k; 132 FlowMap fm; 133 PotMap pm; 138 const Flow &k; 139 Flow v; 134 140 bool b; 135 double x; 136 typename MCF:: Value v;137 typename MCF:: Cost c;141 142 typename MCF::FlowMap &flow; 143 typename MCF::PotentialMap &pot; 138 144 }; 139 145 … … 146 152 bool checkFlow( const GR& gr, const LM& lower, const UM& upper, 147 153 const SM& supply, const FM& flow, 148 SupplyType type = EQ )154 ProblemType type = EQ ) 149 155 { 150 156 TEMPLATE_DIGRAPH_TYPEDEFS(GR); … … 203 209 template < typename MCF, typename GR, 204 210 typename LM, typename UM, 205 typename CM, typename SM, 206 typename PT > 207 void checkMcf( const MCF& mcf, PT mcf_result, 211 typename CM, typename SM > 212 void checkMcf( const MCF& mcf, bool mcf_result, 208 213 const GR& gr, const LM& lower, const UM& upper, 209 214 const CM& cost, const SM& supply, 210 PT result, bool optimal, typename CM::Value total,215 bool result, typename CM::Value total, 211 216 const std::string &test_id = "", 212 SupplyType type = EQ )217 ProblemType type = EQ ) 213 218 { 214 219 check(mcf_result == result, "Wrong result " + test_id); 215 if (optimal) { 216 typename GR::template ArcMap<typename SM::Value> flow(gr); 217 typename GR::template NodeMap<typename CM::Value> pi(gr); 218 mcf.flowMap(flow); 219 mcf.potentialMap(pi); 220 check(checkFlow(gr, lower, upper, supply, flow, type), 220 if (result) { 221 check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type), 221 222 "The flow is not feasible " + test_id); 222 223 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); 223 check(checkPotential(gr, lower, upper, cost, supply, flow, pi), 224 check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(), 225 mcf.potentialMap()), 224 226 "Wrong potentials " + test_id); 225 227 } … … 230 232 // Check the interfaces 231 233 { 234 typedef int Flow; 235 typedef int Cost; 232 236 typedef concepts::Digraph GR; 233 checkConcept< McfClassConcept<GR, int, int>, 234 NetworkSimplex<GR> >(); 235 checkConcept< McfClassConcept<GR, double, double>, 236 NetworkSimplex<GR, double> >(); 237 checkConcept< McfClassConcept<GR, int, double>, 238 NetworkSimplex<GR, int, double> >(); 237 checkConcept< McfClassConcept<GR, Flow, Cost>, 238 NetworkSimplex<GR, Flow, Cost> >(); 239 239 } 240 240 … … 245 245 // Read the test digraph 246 246 Digraph gr; 247 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr),u(gr);248 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr) , s6(gr);247 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr); 248 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr); 249 249 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 250 250 Node v, w; … … 256 256 .arcMap("low1", l1) 257 257 .arcMap("low2", l2) 258 .arcMap("low3", l3)259 258 .nodeMap("sup1", s1) 260 259 .nodeMap("sup2", s2) … … 262 261 .nodeMap("sup4", s4) 263 262 .nodeMap("sup5", s5) 264 .nodeMap("sup6", s6)265 263 .node("source", v) 266 264 .node("target", w) 267 265 .run(); 268 269 // Build a test digraph for testing negative costs270 Digraph ngr;271 Node n1 = ngr.addNode();272 Node n2 = ngr.addNode();273 Node n3 = ngr.addNode();274 Node n4 = ngr.addNode();275 Node n5 = ngr.addNode();276 Node n6 = ngr.addNode();277 Node n7 = ngr.addNode();278 279 Arc a1 = ngr.addArc(n1, n2);280 Arc a2 = ngr.addArc(n1, n3);281 Arc a3 = ngr.addArc(n2, n4);282 Arc a4 = ngr.addArc(n3, n4);283 Arc a5 = ngr.addArc(n3, n2);284 Arc a6 = ngr.addArc(n5, n3);285 Arc a7 = ngr.addArc(n5, n6);286 Arc a8 = ngr.addArc(n6, n7);287 Arc a9 = ngr.addArc(n7, n5);288 289 Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);290 ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);291 Digraph::NodeMap<int> ns(ngr, 0);292 293 nl2[a7] = 1000;294 nl2[a8] = -1000;295 296 ns[n1] = 100;297 ns[n4] = -100;298 299 nc[a1] = 100;300 nc[a2] = 30;301 nc[a3] = 20;302 nc[a4] = 80;303 nc[a5] = 50;304 nc[a6] = 10;305 nc[a7] = 80;306 nc[a8] = 30;307 nc[a9] = -120;308 266 309 267 // A. Test NetworkSimplex with the default pivot rule … … 314 272 mcf.upperMap(u).costMap(c); 315 273 checkMcf(mcf, mcf.supplyMap(s1).run(), 316 gr, l1, u, c, s1, mcf.OPTIMAL, true,5240, "#A1");274 gr, l1, u, c, s1, true, 5240, "#A1"); 317 275 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 318 gr, l1, u, c, s2, mcf.OPTIMAL, true,7620, "#A2");276 gr, l1, u, c, s2, true, 7620, "#A2"); 319 277 mcf.lowerMap(l2); 320 278 checkMcf(mcf, mcf.supplyMap(s1).run(), 321 gr, l2, u, c, s1, mcf.OPTIMAL, true,5970, "#A3");279 gr, l2, u, c, s1, true, 5970, "#A3"); 322 280 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 323 gr, l2, u, c, s2, mcf.OPTIMAL, true,8010, "#A4");281 gr, l2, u, c, s2, true, 8010, "#A4"); 324 282 mcf.reset(); 325 283 checkMcf(mcf, mcf.supplyMap(s1).run(), 326 gr, l1, cu, cc, s1, mcf.OPTIMAL, true,74, "#A5");284 gr, l1, cu, cc, s1, true, 74, "#A5"); 327 285 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), 328 gr, l2, cu, cc, s2, mcf.OPTIMAL, true,94, "#A6");286 gr, l2, cu, cc, s2, true, 94, "#A6"); 329 287 mcf.reset(); 330 288 checkMcf(mcf, mcf.run(), 331 gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7"); 332 checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(), 333 gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8"); 334 mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); 335 checkMcf(mcf, mcf.run(), 336 gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9"); 289 gr, l1, cu, cc, s3, true, 0, "#A7"); 290 checkMcf(mcf, mcf.boundMaps(l2, u).run(), 291 gr, l2, u, cc, s3, false, 0, "#A8"); 337 292 338 293 // Check the GEQ form 339 mcf.reset().upperMap(u).costMap(c).supplyMap(s 5);340 checkMcf(mcf, mcf.run(), 341 gr, l1, u, c, s 5, mcf.OPTIMAL, true, 3530, "#A10", GEQ);342 mcf. supplyType(mcf.GEQ);294 mcf.reset().upperMap(u).costMap(c).supplyMap(s4); 295 checkMcf(mcf, mcf.run(), 296 gr, l1, u, c, s4, true, 3530, "#A9", GEQ); 297 mcf.problemType(mcf.GEQ); 343 298 checkMcf(mcf, mcf.lowerMap(l2).run(), 344 gr, l2, u, c, s 5, mcf.OPTIMAL, true, 4540, "#A11", GEQ);345 mcf. supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);346 checkMcf(mcf, mcf.run(), 347 gr, l2, u, c, s 6, mcf.INFEASIBLE, false, 0, "#A12", GEQ);299 gr, l2, u, c, s4, true, 4540, "#A10", GEQ); 300 mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5); 301 checkMcf(mcf, mcf.run(), 302 gr, l2, u, c, s5, false, 0, "#A11", GEQ); 348 303 349 304 // Check the LEQ form 350 mcf.reset(). supplyType(mcf.LEQ);351 mcf.upperMap(u).costMap(c).supplyMap(s 6);352 checkMcf(mcf, mcf.run(), 353 gr, l1, u, c, s 6, mcf.OPTIMAL, true, 5080, "#A13", LEQ);305 mcf.reset().problemType(mcf.LEQ); 306 mcf.upperMap(u).costMap(c).supplyMap(s5); 307 checkMcf(mcf, mcf.run(), 308 gr, l1, u, c, s5, true, 5080, "#A12", LEQ); 354 309 checkMcf(mcf, mcf.lowerMap(l2).run(), 355 gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); 356 mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5); 357 checkMcf(mcf, mcf.run(), 358 gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); 359 360 // Check negative costs 361 NetworkSimplex<Digraph> nmcf(ngr); 362 nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns); 363 checkMcf(nmcf, nmcf.run(), 364 ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16"); 365 checkMcf(nmcf, nmcf.upperMap(nu2).run(), 366 ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17"); 367 nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns); 368 checkMcf(nmcf, nmcf.run(), 369 ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18"); 310 gr, l2, u, c, s5, true, 5930, "#A13", LEQ); 311 mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4); 312 checkMcf(mcf, mcf.run(), 313 gr, l2, u, c, s4, false, 0, "#A14", LEQ); 370 314 } 371 315 … … 373 317 { 374 318 NetworkSimplex<Digraph> mcf(gr); 375 mcf.supplyMap(s1).costMap(c). upperMap(u).lowerMap(l2);319 mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2); 376 320 377 321 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE), 378 gr, l2, u, c, s1, mcf.OPTIMAL, true,5970, "#B1");322 gr, l2, u, c, s1, true, 5970, "#B1"); 379 323 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE), 380 gr, l2, u, c, s1, mcf.OPTIMAL, true,5970, "#B2");324 gr, l2, u, c, s1, true, 5970, "#B2"); 381 325 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH), 382 gr, l2, u, c, s1, mcf.OPTIMAL, true,5970, "#B3");326 gr, l2, u, c, s1, true, 5970, "#B3"); 383 327 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST), 384 gr, l2, u, c, s1, mcf.OPTIMAL, true,5970, "#B4");328 gr, l2, u, c, s1, true, 5970, "#B4"); 385 329 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST), 386 gr, l2, u, c, s1, mcf.OPTIMAL, true,5970, "#B5");330 gr, l2, u, c, s1, true, 5970, "#B5"); 387 331 } 388 332
Note: See TracChangeset
for help on using the changeset viewer.