r884:bc75ee2ad082
Fri, 13 Nov 2009 00:23:07
[Not Reviewed]
0 comments (0 inline)
0
1
0
178
152
| ... | ... |
@@ -32,6 +32,7 @@ |
| 32 | 32 |
|
| 33 | 33 |
using namespace lemon; |
| 34 | 34 |
|
| 35 |
// Test networks |
|
| 35 | 36 |
char test_lgf[] = |
| 36 | 37 |
"@nodes\n" |
| 37 | 38 |
"label sup1 sup2 sup3 sup4 sup5 sup6\n" |
| ... | ... |
@@ -76,6 +77,58 @@ |
| 76 | 77 |
"source 1\n" |
| 77 | 78 |
"target 12\n"; |
| 78 | 79 |
|
| 80 |
char test_neg1_lgf[] = |
|
| 81 |
"@nodes\n" |
|
| 82 |
"label sup\n" |
|
| 83 |
" 1 100\n" |
|
| 84 |
" 2 0\n" |
|
| 85 |
" 3 0\n" |
|
| 86 |
" 4 -100\n" |
|
| 87 |
" 5 0\n" |
|
| 88 |
" 6 0\n" |
|
| 89 |
" 7 0\n" |
|
| 90 |
"@arcs\n" |
|
| 91 |
" cost low1 low2\n" |
|
| 92 |
"1 2 100 0 0\n" |
|
| 93 |
"1 3 30 0 0\n" |
|
| 94 |
"2 4 20 0 0\n" |
|
| 95 |
"3 4 80 0 0\n" |
|
| 96 |
"3 2 50 0 0\n" |
|
| 97 |
"5 3 10 0 0\n" |
|
| 98 |
"5 6 80 0 1000\n" |
|
| 99 |
"6 7 30 0 -1000\n" |
|
| 100 |
"7 5 -120 0 0\n"; |
|
| 101 |
|
|
| 102 |
char test_neg2_lgf[] = |
|
| 103 |
"@nodes\n" |
|
| 104 |
"label sup\n" |
|
| 105 |
" 1 100\n" |
|
| 106 |
" 2 -300\n" |
|
| 107 |
"@arcs\n" |
|
| 108 |
" cost\n" |
|
| 109 |
"1 2 -1\n"; |
|
| 110 |
|
|
| 111 |
|
|
| 112 |
// Test data |
|
| 113 |
typedef ListDigraph Digraph; |
|
| 114 |
DIGRAPH_TYPEDEFS(ListDigraph); |
|
| 115 |
|
|
| 116 |
Digraph gr; |
|
| 117 |
Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr); |
|
| 118 |
Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); |
|
| 119 |
ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); |
|
| 120 |
Node v, w; |
|
| 121 |
|
|
| 122 |
Digraph neg1_gr; |
|
| 123 |
Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr); |
|
| 124 |
ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000); |
|
| 125 |
Digraph::NodeMap<int> neg1_s(neg1_gr); |
|
| 126 |
|
|
| 127 |
Digraph neg2_gr; |
|
| 128 |
Digraph::ArcMap<int> neg2_c(neg2_gr); |
|
| 129 |
ConstMap<Arc, int> neg2_l(0), neg2_u(1000); |
|
| 130 |
Digraph::NodeMap<int> neg2_s(neg2_gr); |
|
| 131 |
|
|
| 79 | 132 |
|
| 80 | 133 |
enum SupplyType {
|
| 81 | 134 |
EQ, |
| ... | ... |
@@ -83,6 +136,7 @@ |
| 83 | 136 |
LEQ |
| 84 | 137 |
}; |
| 85 | 138 |
|
| 139 |
|
|
| 86 | 140 |
// Check the interface of an MCF algorithm |
| 87 | 141 |
template <typename GR, typename Value, typename Cost> |
| 88 | 142 |
class McfClassConcept |
| ... | ... |
@@ -268,30 +322,99 @@ |
| 268 | 322 |
} |
| 269 | 323 |
} |
| 270 | 324 |
|
| 325 |
template < typename MCF, typename Param > |
|
| 326 |
void runMcfGeqTests( Param param, |
|
| 327 |
const std::string &test_str = "", |
|
| 328 |
bool full_neg_cost_support = false ) |
|
| 329 |
{
|
|
| 330 |
MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr); |
|
| 331 |
|
|
| 332 |
// Basic tests |
|
| 333 |
mcf1.upperMap(u).costMap(c).supplyMap(s1); |
|
| 334 |
checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1, |
|
| 335 |
mcf1.OPTIMAL, true, 5240, test_str + "-1"); |
|
| 336 |
mcf1.stSupply(v, w, 27); |
|
| 337 |
checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2, |
|
| 338 |
mcf1.OPTIMAL, true, 7620, test_str + "-2"); |
|
| 339 |
mcf1.lowerMap(l2).supplyMap(s1); |
|
| 340 |
checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1, |
|
| 341 |
mcf1.OPTIMAL, true, 5970, test_str + "-3"); |
|
| 342 |
mcf1.stSupply(v, w, 27); |
|
| 343 |
checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2, |
|
| 344 |
mcf1.OPTIMAL, true, 8010, test_str + "-4"); |
|
| 345 |
mcf1.reset().supplyMap(s1); |
|
| 346 |
checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1, |
|
| 347 |
mcf1.OPTIMAL, true, 74, test_str + "-5"); |
|
| 348 |
mcf1.lowerMap(l2).stSupply(v, w, 27); |
|
| 349 |
checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2, |
|
| 350 |
mcf1.OPTIMAL, true, 94, test_str + "-6"); |
|
| 351 |
mcf1.reset(); |
|
| 352 |
checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3, |
|
| 353 |
mcf1.OPTIMAL, true, 0, test_str + "-7"); |
|
| 354 |
mcf1.lowerMap(l2).upperMap(u); |
|
| 355 |
checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3, |
|
| 356 |
mcf1.INFEASIBLE, false, 0, test_str + "-8"); |
|
| 357 |
mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); |
|
| 358 |
checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4, |
|
| 359 |
mcf1.OPTIMAL, true, 6360, test_str + "-9"); |
|
| 360 |
|
|
| 361 |
// Tests for the GEQ form |
|
| 362 |
mcf1.reset().upperMap(u).costMap(c).supplyMap(s5); |
|
| 363 |
checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5, |
|
| 364 |
mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ); |
|
| 365 |
mcf1.lowerMap(l2); |
|
| 366 |
checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, |
|
| 367 |
mcf1.OPTIMAL, true, 4540, test_str + "-11", GEQ); |
|
| 368 |
mcf1.supplyMap(s6); |
|
| 369 |
checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, |
|
| 370 |
mcf1.INFEASIBLE, false, 0, test_str + "-12", GEQ); |
|
| 371 |
|
|
| 372 |
// Tests with negative costs |
|
| 373 |
mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s); |
|
| 374 |
checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s, |
|
| 375 |
mcf2.UNBOUNDED, false, 0, test_str + "-13"); |
|
| 376 |
mcf2.upperMap(neg1_u2); |
|
| 377 |
checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s, |
|
| 378 |
mcf2.OPTIMAL, true, -40000, test_str + "-14"); |
|
| 379 |
mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s); |
|
| 380 |
checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s, |
|
| 381 |
mcf2.UNBOUNDED, false, 0, test_str + "-15"); |
|
| 382 |
|
|
| 383 |
mcf3.costMap(neg2_c).supplyMap(neg2_s); |
|
| 384 |
if (full_neg_cost_support) {
|
|
| 385 |
checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, |
|
| 386 |
mcf3.OPTIMAL, true, -300, test_str + "-16", GEQ); |
|
| 387 |
} else {
|
|
| 388 |
checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, |
|
| 389 |
mcf3.UNBOUNDED, false, 0, test_str + "-17", GEQ); |
|
| 390 |
} |
|
| 391 |
mcf3.upperMap(neg2_u); |
|
| 392 |
checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, |
|
| 393 |
mcf3.OPTIMAL, true, -300, test_str + "-18", GEQ); |
|
| 394 |
} |
|
| 395 |
|
|
| 396 |
template < typename MCF, typename Param > |
|
| 397 |
void runMcfLeqTests( Param param, |
|
| 398 |
const std::string &test_str = "" ) |
|
| 399 |
{
|
|
| 400 |
// Tests for the LEQ form |
|
| 401 |
MCF mcf1(gr); |
|
| 402 |
mcf1.supplyType(mcf1.LEQ); |
|
| 403 |
mcf1.upperMap(u).costMap(c).supplyMap(s6); |
|
| 404 |
checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6, |
|
| 405 |
mcf1.OPTIMAL, true, 5080, test_str + "-19", LEQ); |
|
| 406 |
mcf1.lowerMap(l2); |
|
| 407 |
checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6, |
|
| 408 |
mcf1.OPTIMAL, true, 5930, test_str + "-20", LEQ); |
|
| 409 |
mcf1.supplyMap(s5); |
|
| 410 |
checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5, |
|
| 411 |
mcf1.INFEASIBLE, false, 0, test_str + "-21", LEQ); |
|
| 412 |
} |
|
| 413 |
|
|
| 414 |
|
|
| 271 | 415 |
int main() |
| 272 | 416 |
{
|
| 273 |
// Check the interfaces |
|
| 274 |
{
|
|
| 275 |
typedef concepts::Digraph GR; |
|
| 276 |
checkConcept< McfClassConcept<GR, int, int>, |
|
| 277 |
NetworkSimplex<GR> >(); |
|
| 278 |
checkConcept< McfClassConcept<GR, double, double>, |
|
| 279 |
NetworkSimplex<GR, double> >(); |
|
| 280 |
checkConcept< McfClassConcept<GR, int, double>, |
|
| 281 |
NetworkSimplex<GR, int, double> >(); |
|
| 282 |
} |
|
| 283 |
|
|
| 284 |
// Run various MCF tests |
|
| 285 |
typedef ListDigraph Digraph; |
|
| 286 |
DIGRAPH_TYPEDEFS(ListDigraph); |
|
| 287 |
|
|
| 288 |
// Read the test digraph |
|
| 289 |
Digraph gr; |
|
| 290 |
Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr); |
|
| 291 |
Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); |
|
| 292 |
ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); |
|
| 293 |
Node v, w; |
|
| 294 |
|
|
| 417 |
// Read the test networks |
|
| 295 | 418 |
std::istringstream input(test_lgf); |
| 296 | 419 |
DigraphReader<Digraph>(gr, input) |
| 297 | 420 |
.arcMap("cost", c)
|
| ... | ... |
@@ -309,141 +432,44 @@ |
| 309 | 432 |
.node("target", w)
|
| 310 | 433 |
.run(); |
| 311 | 434 |
|
| 312 |
// Build test digraphs with negative costs |
|
| 313 |
Digraph neg_gr; |
|
| 314 |
Node n1 = neg_gr.addNode(); |
|
| 315 |
Node n2 = neg_gr.addNode(); |
|
| 316 |
Node n3 = neg_gr.addNode(); |
|
| 317 |
Node n4 = neg_gr.addNode(); |
|
| 318 |
Node n5 = neg_gr.addNode(); |
|
| 319 |
Node n6 = neg_gr.addNode(); |
|
| 320 |
|
|
| 435 |
std::istringstream neg_inp1(test_neg1_lgf); |
|
| 436 |
DigraphReader<Digraph>(neg1_gr, neg_inp1) |
|
| 437 |
.arcMap("cost", neg1_c)
|
|
| 438 |
.arcMap("low1", neg1_l1)
|
|
| 439 |
.arcMap("low2", neg1_l2)
|
|
| 440 |
.nodeMap("sup", neg1_s)
|
|
| 441 |
.run(); |
|
| 321 | 442 |
|
| 322 |
Arc a1 = neg_gr.addArc(n1, n2); |
|
| 323 |
Arc a2 = neg_gr.addArc(n1, n3); |
|
| 324 |
Arc a3 = neg_gr.addArc(n2, n4); |
|
| 325 |
Arc a4 = neg_gr.addArc(n3, n4); |
|
| 326 |
Arc a5 = neg_gr.addArc(n3, n2); |
|
| 327 |
Arc a6 = neg_gr.addArc(n5, n3); |
|
| 328 |
Arc a7 = neg_gr.addArc(n5, n6); |
|
| 329 |
Arc a8 = neg_gr.addArc(n6, n7); |
|
| 330 |
|
|
| 443 |
std::istringstream neg_inp2(test_neg2_lgf); |
|
| 444 |
DigraphReader<Digraph>(neg2_gr, neg_inp2) |
|
| 445 |
.arcMap("cost", neg2_c)
|
|
| 446 |
.nodeMap("sup", neg2_s)
|
|
| 447 |
.run(); |
|
| 331 | 448 |
|
| 332 |
Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0); |
|
| 333 |
ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000); |
|
| 334 |
Digraph::NodeMap<int> neg_s(neg_gr, 0); |
|
| 335 |
|
|
| 336 |
neg_l2[a7] = 1000; |
|
| 337 |
neg_l2[a8] = -1000; |
|
| 338 |
|
|
| 339 |
neg_s[n1] = 100; |
|
| 340 |
neg_s[n4] = -100; |
|
| 341 |
|
|
| 342 |
neg_c[a1] = 100; |
|
| 343 |
neg_c[a2] = 30; |
|
| 344 |
neg_c[a3] = 20; |
|
| 345 |
neg_c[a4] = 80; |
|
| 346 |
neg_c[a5] = 50; |
|
| 347 |
neg_c[a6] = 10; |
|
| 348 |
neg_c[a7] = 80; |
|
| 349 |
neg_c[a8] = 30; |
|
| 350 |
neg_c[a9] = -120; |
|
| 351 |
|
|
| 352 |
Digraph negs_gr; |
|
| 353 |
Digraph::NodeMap<int> negs_s(negs_gr); |
|
| 354 |
Digraph::ArcMap<int> negs_c(negs_gr); |
|
| 355 |
ConstMap<Arc, int> negs_l(0), negs_u(1000); |
|
| 356 |
n1 = negs_gr.addNode(); |
|
| 357 |
n2 = negs_gr.addNode(); |
|
| 358 |
negs_s[n1] = 100; |
|
| 359 |
negs_s[n2] = -300; |
|
| 360 |
negs_c[negs_gr.addArc(n1, n2)] = -1; |
|
| 361 |
|
|
| 362 |
|
|
| 363 |
// A. Test NetworkSimplex with the default pivot rule |
|
| 449 |
// Check the interface of NetworkSimplex |
|
| 364 | 450 |
{
|
| 365 |
NetworkSimplex<Digraph> mcf(gr); |
|
| 366 |
|
|
| 367 |
// Check the equality form |
|
| 368 |
mcf.upperMap(u).costMap(c); |
|
| 369 |
checkMcf(mcf, mcf.supplyMap(s1).run(), |
|
| 370 |
gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1"); |
|
| 371 |
checkMcf(mcf, mcf.stSupply(v, w, 27).run(), |
|
| 372 |
gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2"); |
|
| 373 |
mcf.lowerMap(l2); |
|
| 374 |
checkMcf(mcf, mcf.supplyMap(s1).run(), |
|
| 375 |
gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3"); |
|
| 376 |
checkMcf(mcf, mcf.stSupply(v, w, 27).run(), |
|
| 377 |
gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4"); |
|
| 378 |
mcf.reset(); |
|
| 379 |
checkMcf(mcf, mcf.supplyMap(s1).run(), |
|
| 380 |
gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5"); |
|
| 381 |
checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), |
|
| 382 |
gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6"); |
|
| 383 |
mcf.reset(); |
|
| 384 |
checkMcf(mcf, mcf.run(), |
|
| 385 |
gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7"); |
|
| 386 |
checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(), |
|
| 387 |
gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8"); |
|
| 388 |
mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); |
|
| 389 |
checkMcf(mcf, mcf.run(), |
|
| 390 |
gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9"); |
|
| 391 |
|
|
| 392 |
// Check the GEQ form |
|
| 393 |
mcf.reset().upperMap(u).costMap(c).supplyMap(s5); |
|
| 394 |
checkMcf(mcf, mcf.run(), |
|
| 395 |
gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ); |
|
| 396 |
mcf.supplyType(mcf.GEQ); |
|
| 397 |
checkMcf(mcf, mcf.lowerMap(l2).run(), |
|
| 398 |
gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ); |
|
| 399 |
mcf.supplyMap(s6); |
|
| 400 |
checkMcf(mcf, mcf.run(), |
|
| 401 |
gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ); |
|
| 402 |
|
|
| 403 |
// Check the LEQ form |
|
| 404 |
mcf.reset().supplyType(mcf.LEQ); |
|
| 405 |
mcf.upperMap(u).costMap(c).supplyMap(s6); |
|
| 406 |
checkMcf(mcf, mcf.run(), |
|
| 407 |
gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ); |
|
| 408 |
checkMcf(mcf, mcf.lowerMap(l2).run(), |
|
| 409 |
gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); |
|
| 410 |
mcf.supplyMap(s5); |
|
| 411 |
checkMcf(mcf, mcf.run(), |
|
| 412 |
gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); |
|
| 413 |
|
|
| 414 |
// Check negative costs |
|
| 415 |
NetworkSimplex<Digraph> neg_mcf(neg_gr); |
|
| 416 |
neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s); |
|
| 417 |
checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1, |
|
| 418 |
neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16"); |
|
| 419 |
neg_mcf.upperMap(neg_u2); |
|
| 420 |
checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2, |
|
| 421 |
neg_c, neg_s, neg_mcf.OPTIMAL, true, -40000, "#A17"); |
|
| 422 |
neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s); |
|
| 423 |
checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1, |
|
| 424 |
neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18"); |
|
| 425 |
|
|
| 426 |
NetworkSimplex<Digraph> negs_mcf(negs_gr); |
|
| 427 |
negs_mcf.costMap(negs_c).supplyMap(negs_s); |
|
| 428 |
checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u, |
|
| 429 |
|
|
| 451 |
typedef concepts::Digraph GR; |
|
| 452 |
checkConcept< McfClassConcept<GR, int, int>, |
|
| 453 |
NetworkSimplex<GR> >(); |
|
| 454 |
checkConcept< McfClassConcept<GR, double, double>, |
|
| 455 |
NetworkSimplex<GR, double> >(); |
|
| 456 |
checkConcept< McfClassConcept<GR, int, double>, |
|
| 457 |
NetworkSimplex<GR, int, double> >(); |
|
| 430 | 458 |
} |
| 431 | 459 |
|
| 432 |
// B. Test NetworkSimplex with each pivot rule |
|
| 433 |
{
|
|
| 434 |
NetworkSimplex<Digraph> mcf(gr); |
|
| 435 |
mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2); |
|
| 436 |
|
|
| 437 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE), |
|
| 438 |
gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1"); |
|
| 439 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE), |
|
| 440 |
gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2"); |
|
| 441 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH), |
|
| 442 |
gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3"); |
|
| 443 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST), |
|
| 444 |
gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4"); |
|
| 445 |
checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST), |
|
| 446 |
|
|
| 460 |
// Test NetworkSimplex |
|
| 461 |
{
|
|
| 462 |
typedef NetworkSimplex<Digraph> MCF; |
|
| 463 |
runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true); |
|
| 464 |
runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE"); |
|
| 465 |
runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE", true); |
|
| 466 |
runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE"); |
|
| 467 |
runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS", true); |
|
| 468 |
runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS"); |
|
| 469 |
runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true); |
|
| 470 |
runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL"); |
|
| 471 |
runMcfGeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL", true); |
|
| 472 |
runMcfLeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL"); |
|
| 447 | 473 |
} |
| 448 | 474 |
|
| 449 | 475 |
return 0; |
0 comments (0 inline)