Changeset 652:5232721b3f14 in lemon for test/min_cost_flow_test.cc
 Timestamp:
 03/25/09 15:58:44 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/min_cost_flow_test.cc
r648 r652 21 21 22 22 #include <lemon/list_graph.h> 23 #include <lemon/smart_graph.h>24 23 #include <lemon/lgf_reader.h> 25 24 26 //#include <lemon/cycle_canceling.h>27 //#include <lemon/capacity_scaling.h>28 //#include <lemon/cost_scaling.h>29 25 #include <lemon/network_simplex.h> 30 //#include <lemon/min_cost_flow.h>31 //#include <lemon/min_cost_max_flow.h>32 26 33 27 #include <lemon/concepts/digraph.h> … … 94 88 checkConcept<concepts::Digraph, GR>(); 95 89 96 MCF mcf _test1(g, lower, upper, cost, sup);97 MCF mcf_test2(g, upper, cost, sup); 98 MCF mcf_test3(g, lower, upper, cost, n, n, k);99 MCF mcf_test4(g, upper, cost, n, n, k);100 101 // TODO: This part should be enabled and the next part102 // should be removed if map copying is supported103 /* 104 flow = mcf_test1.flowMap();105 mcf_test1.flowMap(flow);106 107 pot = mcf_test1.potentialMap();108 mcf_test1.potentialMap(pot);109 */ 110 /**/ 111 const typename MCF::FlowMap &fm =112 mcf_test1.flowMap();113 mcf_test1.flowMap(flow);114 const typename MCF::PotentialMap &pm =115 mcf_test1.potentialMap();116 mcf_test1.potentialMap(pot); 90 MCF mcf(g); 91 92 b = mcf.lowerMap(lower) 93 .upperMap(upper) 94 .capacityMap(upper) 95 .boundMaps(lower, upper) 96 .costMap(cost) 97 .supplyMap(sup) 98 .stSupply(n, n, k) 99 .run(); 100 101 const typename MCF::FlowMap &fm = mcf.flowMap(); 102 const typename MCF::PotentialMap &pm = mcf.potentialMap(); 103 104 v = mcf.totalCost(); 105 double x = mcf.template totalCost<double>(); 106 v = mcf.flow(a); 107 v = mcf.potential(n); 108 mcf.flowMap(flow); 109 mcf.potentialMap(pot); 110 117 111 ignore_unused_variable_warning(fm); 118 112 ignore_unused_variable_warning(pm); 119 /**/ 120 121 mcf_test1.run(); 122 123 v = mcf_test1.totalCost(); 124 v = mcf_test1.flow(a); 125 v = mcf_test1.potential(n); 113 ignore_unused_variable_warning(x); 126 114 } 127 115 … … 140 128 const Value &k; 141 129 Value v; 130 bool b; 142 131 143 132 typename MCF::FlowMap &flow; … … 173 162 174 163 // Check the feasibility of the given potentials (dual soluiton) 175 // using the Complementary Slacknessoptimality condition164 // using the "Complementary Slackness" optimality condition 176 165 template < typename GR, typename LM, typename UM, 177 166 typename CM, typename FM, typename PM > … … 218 207 { 219 208 typedef int Value; 220 // This typedef should be enabled if the standard maps are 221 // reference maps in the graph concepts 209 // TODO: This typedef should be enabled if the standard maps are 210 // reference maps in the graph concepts (See #190). 211 /**/ 222 212 //typedef concepts::Digraph GR; 223 213 typedef ListDigraph GR; 224 typedef concepts::ReadMap<GR::Node, Value> NM; 225 typedef concepts::ReadMap<GR::Arc, Value> AM; 226 227 //checkConcept< McfClassConcept<GR, Value>, 228 // CycleCanceling<GR, AM, AM, AM, NM> >(); 229 //checkConcept< McfClassConcept<GR, Value>, 230 // CapacityScaling<GR, AM, AM, AM, NM> >(); 231 //checkConcept< McfClassConcept<GR, Value>, 232 // CostScaling<GR, AM, AM, AM, NM> >(); 214 /**/ 233 215 checkConcept< McfClassConcept<GR, Value>, 234 NetworkSimplex<GR, AM, AM, AM, NM> >(); 235 //checkConcept< MinCostFlow<GR, Value>, 236 // NetworkSimplex<GR, AM, AM, AM, NM> >(); 216 NetworkSimplex<GR, Value> >(); 237 217 } 238 218 … … 245 225 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr); 246 226 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr); 227 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 247 228 Node v, w; 248 229 … … 260 241 .run(); 261 242 262 /* 263 // A. Test CapacityScaling with scaling 243 // A. Test NetworkSimplex with the default pivot rule 264 244 { 265 CapacityScaling<Digraph> mcf1(gr, u, c, s1); 266 CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); 267 CapacityScaling<Digraph> mcf3(gr, u, c, s3); 268 CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); 269 CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 270 CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); 271 272 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#A1"); 273 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#A2"); 274 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#A3"); 275 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#A4"); 276 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#A5"); 277 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#A6"); 278 } 279 280 // B. Test CapacityScaling without scaling 245 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), 246 mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr); 247 248 checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(), 249 gr, l1, u, c, s1, true, 5240, "#A1"); 250 checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(), 251 gr, l1, u, c, s2, true, 7620, "#A2"); 252 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(), 253 gr, l2, u, c, s1, true, 5970, "#A3"); 254 checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(), 255 gr, l2, u, c, s2, true, 8010, "#A4"); 256 checkMcf(mcf5, mcf5.supplyMap(s1).run(), 257 gr, l1, cu, cc, s1, true, 74, "#A5"); 258 checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(), 259 gr, l2, cu, cc, s2, true, 94, "#A6"); 260 checkMcf(mcf7, mcf7.run(), 261 gr, l1, cu, cc, s3, true, 0, "#A7"); 262 checkMcf(mcf8, mcf8.boundMaps(l2, u).run(), 263 gr, l2, u, cc, s3, false, 0, "#A8"); 264 } 265 266 // B. Test NetworkSimplex with each pivot rule 281 267 { 282 CapacityScaling<Digraph> mcf1(gr, u, c, s1); 283 CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); 284 CapacityScaling<Digraph> mcf3(gr, u, c, s3); 285 CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); 286 CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 287 CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); 288 289 checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#B1"); 290 checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#B2"); 291 checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#B3"); 292 checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#B4"); 293 checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#B5"); 294 checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#B6"); 295 } 296 297 // C. Test CostScaling using partial augmentrelabel method 298 { 299 CostScaling<Digraph> mcf1(gr, u, c, s1); 300 CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); 301 CostScaling<Digraph> mcf3(gr, u, c, s3); 302 CostScaling<Digraph> mcf4(gr, l2, u, c, s1); 303 CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 304 CostScaling<Digraph> mcf6(gr, l2, u, c, s3); 305 306 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#C1"); 307 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#C2"); 308 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#C3"); 309 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#C4"); 310 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#C5"); 311 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#C6"); 312 } 313 314 // D. Test CostScaling using pushrelabel method 315 { 316 CostScaling<Digraph> mcf1(gr, u, c, s1); 317 CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); 318 CostScaling<Digraph> mcf3(gr, u, c, s3); 319 CostScaling<Digraph> mcf4(gr, l2, u, c, s1); 320 CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 321 CostScaling<Digraph> mcf6(gr, l2, u, c, s3); 322 323 checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#D1"); 324 checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#D2"); 325 checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#D3"); 326 checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#D4"); 327 checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#D5"); 328 checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#D6"); 329 } 330 */ 331 332 // E. Test NetworkSimplex with FIRST_ELIGIBLE_PIVOT 333 { 334 NetworkSimplex<Digraph>::PivotRuleEnum pr = 335 NetworkSimplex<Digraph>::FIRST_ELIGIBLE_PIVOT; 336 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 337 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 338 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 339 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 340 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 341 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 342 343 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#E1"); 344 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#E2"); 345 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#E3"); 346 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#E4"); 347 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#E5"); 348 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#E6"); 349 } 350 351 // F. Test NetworkSimplex with BEST_ELIGIBLE_PIVOT 352 { 353 NetworkSimplex<Digraph>::PivotRuleEnum pr = 354 NetworkSimplex<Digraph>::BEST_ELIGIBLE_PIVOT; 355 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 356 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 357 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 358 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 359 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 360 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 361 362 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#F1"); 363 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#F2"); 364 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#F3"); 365 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#F4"); 366 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#F5"); 367 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#F6"); 368 } 369 370 // G. Test NetworkSimplex with BLOCK_SEARCH_PIVOT 371 { 372 NetworkSimplex<Digraph>::PivotRuleEnum pr = 373 NetworkSimplex<Digraph>::BLOCK_SEARCH_PIVOT; 374 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 375 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 376 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 377 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 378 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 379 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 380 381 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#G1"); 382 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#G2"); 383 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#G3"); 384 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#G4"); 385 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#G5"); 386 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#G6"); 387 } 388 389 // H. Test NetworkSimplex with CANDIDATE_LIST_PIVOT 390 { 391 NetworkSimplex<Digraph>::PivotRuleEnum pr = 392 NetworkSimplex<Digraph>::CANDIDATE_LIST_PIVOT; 393 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 394 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 395 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 396 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 397 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 398 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 399 400 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#H1"); 401 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#H2"); 402 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#H3"); 403 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#H4"); 404 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#H5"); 405 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#H6"); 406 } 407 408 // I. Test NetworkSimplex with ALTERING_LIST_PIVOT 409 { 410 NetworkSimplex<Digraph>::PivotRuleEnum pr = 411 NetworkSimplex<Digraph>::ALTERING_LIST_PIVOT; 412 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 413 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 414 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 415 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 416 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 417 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 418 419 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#I1"); 420 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#I2"); 421 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#I3"); 422 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#I4"); 423 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#I5"); 424 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#I6"); 425 } 426 427 /* 428 // J. Test MinCostFlow 429 { 430 MinCostFlow<Digraph> mcf1(gr, u, c, s1); 431 MinCostFlow<Digraph> mcf2(gr, u, c, v, w, 27); 432 MinCostFlow<Digraph> mcf3(gr, u, c, s3); 433 MinCostFlow<Digraph> mcf4(gr, l2, u, c, s1); 434 MinCostFlow<Digraph> mcf5(gr, l2, u, c, v, w, 27); 435 MinCostFlow<Digraph> mcf6(gr, l2, u, c, s3); 436 437 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#J1"); 438 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#J2"); 439 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#J3"); 440 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#J4"); 441 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#J5"); 442 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#J6"); 443 } 444 */ 445 /* 446 // K. Test MinCostMaxFlow 447 { 448 MinCostMaxFlow<Digraph> mcmf(gr, u, c, v, w); 449 mcmf.run(); 450 checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1"); 451 } 452 */ 268 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr); 269 NetworkSimplex<Digraph>::PivotRule pr; 270 271 pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE; 272 checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 273 gr, l2, u, c, s1, true, 5970, "#B1"); 274 pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE; 275 checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 276 gr, l2, u, c, s1, true, 5970, "#B2"); 277 pr = NetworkSimplex<Digraph>::BLOCK_SEARCH; 278 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 279 gr, l2, u, c, s1, true, 5970, "#B3"); 280 pr = NetworkSimplex<Digraph>::CANDIDATE_LIST; 281 checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 282 gr, l2, u, c, s1, true, 5970, "#B4"); 283 pr = NetworkSimplex<Digraph>::ALTERING_LIST; 284 checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 285 gr, l2, u, c, s1, true, 5970, "#B5"); 286 } 453 287 454 288 return 0;
Note: See TracChangeset
for help on using the changeset viewer.