240 .node("target", w) |
241 .node("target", w) |
241 .run(); |
242 .run(); |
242 |
243 |
243 // A. Test NetworkSimplex with the default pivot rule |
244 // A. Test NetworkSimplex with the default pivot rule |
244 { |
245 { |
245 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), |
246 NetworkSimplex<Digraph> mcf(gr); |
246 mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr); |
247 |
247 |
248 mcf.upperMap(u).costMap(c); |
248 checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(), |
249 checkMcf(mcf, mcf.supplyMap(s1).run(), |
249 gr, l1, u, c, s1, true, 5240, "#A1"); |
250 gr, l1, u, c, s1, true, 5240, "#A1"); |
250 checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(), |
251 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), |
251 gr, l1, u, c, s2, true, 7620, "#A2"); |
252 gr, l1, u, c, s2, true, 7620, "#A2"); |
252 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(), |
253 mcf.lowerMap(l2); |
|
254 checkMcf(mcf, mcf.supplyMap(s1).run(), |
253 gr, l2, u, c, s1, true, 5970, "#A3"); |
255 gr, l2, u, c, s1, true, 5970, "#A3"); |
254 checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(), |
256 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), |
255 gr, l2, u, c, s2, true, 8010, "#A4"); |
257 gr, l2, u, c, s2, true, 8010, "#A4"); |
256 checkMcf(mcf5, mcf5.supplyMap(s1).run(), |
258 mcf.reset(); |
|
259 checkMcf(mcf, mcf.supplyMap(s1).run(), |
257 gr, l1, cu, cc, s1, true, 74, "#A5"); |
260 gr, l1, cu, cc, s1, true, 74, "#A5"); |
258 checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(), |
261 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), |
259 gr, l2, cu, cc, s2, true, 94, "#A6"); |
262 gr, l2, cu, cc, s2, true, 94, "#A6"); |
260 checkMcf(mcf7, mcf7.run(), |
263 mcf.reset(); |
|
264 checkMcf(mcf, mcf.run(), |
261 gr, l1, cu, cc, s3, true, 0, "#A7"); |
265 gr, l1, cu, cc, s3, true, 0, "#A7"); |
262 checkMcf(mcf8, mcf8.boundMaps(l2, u).run(), |
266 checkMcf(mcf, mcf.boundMaps(l2, u).run(), |
263 gr, l2, u, cc, s3, false, 0, "#A8"); |
267 gr, l2, u, cc, s3, false, 0, "#A8"); |
264 } |
268 } |
265 |
269 |
266 // B. Test NetworkSimplex with each pivot rule |
270 // B. Test NetworkSimplex with each pivot rule |
267 { |
271 { |
268 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr); |
272 NetworkSimplex<Digraph> mcf(gr); |
269 NetworkSimplex<Digraph>::PivotRule pr; |
273 mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2); |
270 |
274 |
271 pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE; |
275 checkMcf(mcf, mcf.run(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"); |
276 gr, l2, u, c, s1, true, 5970, "#B1"); |
274 pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE; |
277 checkMcf(mcf, mcf.run(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"); |
278 gr, l2, u, c, s1, true, 5970, "#B2"); |
277 pr = NetworkSimplex<Digraph>::BLOCK_SEARCH; |
279 checkMcf(mcf, mcf.run(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 gr, l2, u, c, s1, true, 5970, "#B3"); |
280 pr = NetworkSimplex<Digraph>::CANDIDATE_LIST; |
281 checkMcf(mcf, mcf.run(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"); |
282 gr, l2, u, c, s1, true, 5970, "#B4"); |
283 pr = NetworkSimplex<Digraph>::ALTERING_LIST; |
283 checkMcf(mcf, mcf.run(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"); |
284 gr, l2, u, c, s1, true, 5970, "#B5"); |
286 } |
285 } |
287 |
286 |
288 return 0; |
287 return 0; |
289 } |
288 } |