Changeset 687:6c408d864fa1 in lemon for test/min_cost_flow_test.cc
- Timestamp:
- 04/29/09 03:15:24 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/min_cost_flow_test.cc
r662 r687 19 19 #include <iostream> 20 20 #include <fstream> 21 #include <limits> 21 22 22 23 #include <lemon/list_graph.h> … … 34 35 char test_lgf[] = 35 36 "@nodes\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" 37 "label sup1 sup2 sup3 sup4 sup5 sup6\n" 38 " 1 20 27 0 30 20 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 0 6 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 0 3\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" 50 51 "@arcs\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"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" 73 74 "\n" 74 75 "@attributes\n" … … 77 78 78 79 79 enum ProblemType {80 enum SupplyType { 80 81 EQ, 81 82 GEQ, … … 99 100 .lowerMap(lower) 100 101 .upperMap(upper) 101 .capacityMap(upper)102 .boundMaps(lower, upper)103 102 .costMap(cost) 104 103 .supplyMap(sup) … … 113 112 const typename MCF::PotentialMap &pm = const_mcf.potentialMap(); 114 113 115 v= const_mcf.totalCost();114 c = const_mcf.totalCost(); 116 115 double x = const_mcf.template totalCost<double>(); 117 116 v = const_mcf.flow(a); 118 v = const_mcf.potential(n); 117 c = const_mcf.potential(n); 118 119 v = const_mcf.INF; 119 120 120 121 ignore_unused_variable_warning(fm); … … 138 139 const Flow &k; 139 140 Flow v; 141 Cost c; 140 142 bool b; 141 143 … … 152 154 bool checkFlow( const GR& gr, const LM& lower, const UM& upper, 153 155 const SM& supply, const FM& flow, 154 ProblemType type = EQ )156 SupplyType type = EQ ) 155 157 { 156 158 TEMPLATE_DIGRAPH_TYPEDEFS(GR); … … 209 211 template < typename MCF, typename GR, 210 212 typename LM, typename UM, 211 typename CM, typename SM > 212 void checkMcf( const MCF& mcf, bool mcf_result, 213 typename CM, typename SM, 214 typename PT > 215 void checkMcf( const MCF& mcf, PT mcf_result, 213 216 const GR& gr, const LM& lower, const UM& upper, 214 217 const CM& cost, const SM& supply, 215 bool result, typename CM::Value total,218 PT result, bool optimal, typename CM::Value total, 216 219 const std::string &test_id = "", 217 ProblemType type = EQ )220 SupplyType type = EQ ) 218 221 { 219 222 check(mcf_result == result, "Wrong result " + test_id); 220 if ( result) {223 if (optimal) { 221 224 check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type), 222 225 "The flow is not feasible " + test_id); … … 245 248 // Read the test digraph 246 249 Digraph 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) ;250 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr); 251 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); 249 252 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 250 253 Node v, w; … … 256 259 .arcMap("low1", l1) 257 260 .arcMap("low2", l2) 261 .arcMap("low3", l3) 258 262 .nodeMap("sup1", s1) 259 263 .nodeMap("sup2", s2) … … 261 265 .nodeMap("sup4", s4) 262 266 .nodeMap("sup5", s5) 267 .nodeMap("sup6", s6) 263 268 .node("source", v) 264 269 .node("target", w) 265 270 .run(); 271 272 // Build a test digraph for testing negative costs 273 Digraph ngr; 274 Node n1 = ngr.addNode(); 275 Node n2 = ngr.addNode(); 276 Node n3 = ngr.addNode(); 277 Node n4 = ngr.addNode(); 278 Node n5 = ngr.addNode(); 279 Node n6 = ngr.addNode(); 280 Node n7 = ngr.addNode(); 281 282 Arc a1 = ngr.addArc(n1, n2); 283 Arc a2 = ngr.addArc(n1, n3); 284 Arc a3 = ngr.addArc(n2, n4); 285 Arc a4 = ngr.addArc(n3, n4); 286 Arc a5 = ngr.addArc(n3, n2); 287 Arc a6 = ngr.addArc(n5, n3); 288 Arc a7 = ngr.addArc(n5, n6); 289 Arc a8 = ngr.addArc(n6, n7); 290 Arc a9 = ngr.addArc(n7, n5); 291 292 Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0); 293 ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000); 294 Digraph::NodeMap<int> ns(ngr, 0); 295 296 nl2[a7] = 1000; 297 nl2[a8] = -1000; 298 299 ns[n1] = 100; 300 ns[n4] = -100; 301 302 nc[a1] = 100; 303 nc[a2] = 30; 304 nc[a3] = 20; 305 nc[a4] = 80; 306 nc[a5] = 50; 307 nc[a6] = 10; 308 nc[a7] = 80; 309 nc[a8] = 30; 310 nc[a9] = -120; 266 311 267 312 // A. Test NetworkSimplex with the default pivot rule … … 272 317 mcf.upperMap(u).costMap(c); 273 318 checkMcf(mcf, mcf.supplyMap(s1).run(), 274 gr, l1, u, c, s1, true,5240, "#A1");319 gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1"); 275 320 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 276 gr, l1, u, c, s2, true,7620, "#A2");321 gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2"); 277 322 mcf.lowerMap(l2); 278 323 checkMcf(mcf, mcf.supplyMap(s1).run(), 279 gr, l2, u, c, s1, true,5970, "#A3");324 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3"); 280 325 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 281 gr, l2, u, c, s2, true,8010, "#A4");326 gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4"); 282 327 mcf.reset(); 283 328 checkMcf(mcf, mcf.supplyMap(s1).run(), 284 gr, l1, cu, cc, s1, true,74, "#A5");329 gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5"); 285 330 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), 286 gr, l2, cu, cc, s2, true,94, "#A6");331 gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6"); 287 332 mcf.reset(); 288 333 checkMcf(mcf, mcf.run(), 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"); 334 gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7"); 335 checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(), 336 gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8"); 337 mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); 338 checkMcf(mcf, mcf.run(), 339 gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9"); 292 340 293 341 // Check the GEQ form 294 mcf.reset().upperMap(u).costMap(c).supplyMap(s 4);295 checkMcf(mcf, mcf.run(), 296 gr, l1, u, c, s 4, true, 3530, "#A9", GEQ);297 mcf. problemType(mcf.GEQ);342 mcf.reset().upperMap(u).costMap(c).supplyMap(s5); 343 checkMcf(mcf, mcf.run(), 344 gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ); 345 mcf.supplyType(mcf.GEQ); 298 346 checkMcf(mcf, mcf.lowerMap(l2).run(), 299 gr, l2, u, c, s 4, true, 4540, "#A10", GEQ);300 mcf. problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);301 checkMcf(mcf, mcf.run(), 302 gr, l2, u, c, s 5, false, 0, "#A11", GEQ);347 gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ); 348 mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6); 349 checkMcf(mcf, mcf.run(), 350 gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ); 303 351 304 352 // Check the LEQ form 305 mcf.reset(). problemType(mcf.LEQ);306 mcf.upperMap(u).costMap(c).supplyMap(s 5);307 checkMcf(mcf, mcf.run(), 308 gr, l1, u, c, s 5, true, 5080, "#A12", LEQ);353 mcf.reset().supplyType(mcf.LEQ); 354 mcf.upperMap(u).costMap(c).supplyMap(s6); 355 checkMcf(mcf, mcf.run(), 356 gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ); 309 357 checkMcf(mcf, mcf.lowerMap(l2).run(), 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); 358 gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); 359 mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5); 360 checkMcf(mcf, mcf.run(), 361 gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); 362 363 // Check negative costs 364 NetworkSimplex<Digraph> nmcf(ngr); 365 nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns); 366 checkMcf(nmcf, nmcf.run(), 367 ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16"); 368 checkMcf(nmcf, nmcf.upperMap(nu2).run(), 369 ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17"); 370 nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns); 371 checkMcf(nmcf, nmcf.run(), 372 ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18"); 314 373 } 315 374 … … 317 376 { 318 377 NetworkSimplex<Digraph> mcf(gr); 319 mcf.supplyMap(s1).costMap(c). capacityMap(u).lowerMap(l2);378 mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2); 320 379 321 380 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE), 322 gr, l2, u, c, s1, true,5970, "#B1");381 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1"); 323 382 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE), 324 gr, l2, u, c, s1, true,5970, "#B2");383 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2"); 325 384 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH), 326 gr, l2, u, c, s1, true,5970, "#B3");385 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3"); 327 386 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST), 328 gr, l2, u, c, s1, true,5970, "#B4");387 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4"); 329 388 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST), 330 gr, l2, u, c, s1, true,5970, "#B5");389 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5"); 331 390 } 332 391
Note: See TracChangeset
for help on using the changeset viewer.