241 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
241 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
242 check(!pre.minCut(t), "Wrong min cut (Node t)."); |
242 check(!pre.minCut(t), "Wrong min cut (Node t)."); |
243 } |
243 } |
244 |
244 |
245 template <typename MF, typename SF> |
245 template <typename MF, typename SF> |
246 void checkMaxFlowAlg() { |
246 void checkMaxFlowAlg(const char *input_lgf, typename MF::Value expected) { |
247 typedef SmartDigraph Digraph; |
247 typedef SmartDigraph Digraph; |
248 DIGRAPH_TYPEDEFS(Digraph); |
248 DIGRAPH_TYPEDEFS(Digraph); |
249 |
249 |
250 typedef typename MF::Value Value; |
250 typedef typename MF::Value Value; |
251 typedef Digraph::ArcMap<Value> CapMap; |
251 typedef Digraph::ArcMap<Value> CapMap; |
255 Tolerance<Value> tol; |
255 Tolerance<Value> tol; |
256 |
256 |
257 Digraph g; |
257 Digraph g; |
258 Node s, t; |
258 Node s, t; |
259 CapMap cap(g); |
259 CapMap cap(g); |
260 std::istringstream input(test_lgf); |
260 std::istringstream input(input_lgf); |
261 DigraphReader<Digraph>(g,input) |
261 DigraphReader<Digraph>(g,input) |
262 .arcMap("capacity", cap) |
262 .arcMap("capacity", cap) |
263 .node("source",s) |
263 .node("source",s) |
264 .node("target",t) |
264 .node("target",t) |
265 .run(); |
265 .run(); |
266 |
266 |
267 MF max_flow(g, cap, s, t); |
267 MF max_flow(g, cap, s, t); |
268 max_flow.run(); |
268 max_flow.run(); |
269 |
269 |
|
270 check(!tol.different(expected, max_flow.flowValue()), |
|
271 "Incorrect max flow value."); |
270 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), |
272 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), |
271 "The flow is not feasible."); |
273 "The flow is not feasible."); |
272 |
274 |
273 CutMap min_cut(g); |
275 CutMap min_cut(g); |
274 max_flow.minCutMap(min_cut); |
276 max_flow.minCutMap(min_cut); |
275 Value min_cut_value = cutValue(g, min_cut, cap); |
277 Value min_cut_value = cutValue(g, min_cut, cap); |
276 |
278 |
277 check(!tol.different(max_flow.flowValue(), min_cut_value), |
279 check(!tol.different(expected, min_cut_value), |
278 "The max flow value is not equal to the min cut value."); |
280 "Incorrect min cut value."); |
279 |
281 |
280 FlowMap flow(g); |
282 FlowMap flow(g); |
281 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; |
283 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; |
282 |
|
283 Value flow_value = max_flow.flowValue(); |
|
284 |
|
285 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; |
284 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; |
286 max_flow.init(flow); |
285 max_flow.init(flow); |
287 |
286 |
288 SF::startFirstPhase(max_flow); // start first phase of the algorithm |
287 SF::startFirstPhase(max_flow); // start first phase of the algorithm |
289 |
288 |
290 CutMap min_cut1(g); |
289 CutMap min_cut1(g); |
291 max_flow.minCutMap(min_cut1); |
290 max_flow.minCutMap(min_cut1); |
292 min_cut_value = cutValue(g, min_cut1, cap); |
291 min_cut_value = cutValue(g, min_cut1, cap); |
293 |
292 |
294 check(!tol.different(max_flow.flowValue(), min_cut_value) && |
293 check(!tol.different(2 * expected, max_flow.flowValue()), |
295 !tol.different(min_cut_value, 2 * flow_value), |
294 "Incorrect max flow value."); |
296 "The max flow value or the min cut value is wrong."); |
295 check(!tol.different(2 * expected, min_cut_value), |
|
296 "Incorrect min cut value."); |
297 |
297 |
298 SF::startSecondPhase(max_flow); // start second phase of the algorithm |
298 SF::startSecondPhase(max_flow); // start second phase of the algorithm |
299 |
299 |
300 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), |
300 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), |
301 "The flow is not feasible."); |
301 "The flow is not feasible."); |
302 |
302 |
303 CutMap min_cut2(g); |
303 CutMap min_cut2(g); |
304 max_flow.minCutMap(min_cut2); |
304 max_flow.minCutMap(min_cut2); |
305 min_cut_value = cutValue(g, min_cut2, cap); |
305 min_cut_value = cutValue(g, min_cut2, cap); |
306 |
306 |
307 check(!tol.different(max_flow.flowValue(), min_cut_value) && |
307 check(!tol.different(2 * expected, max_flow.flowValue()), |
308 !tol.different(min_cut_value, 2 * flow_value), |
308 "Incorrect max flow value."); |
309 "The max flow value or the min cut value was not doubled."); |
309 check(!tol.different(2 * expected, min_cut_value), |
|
310 "Incorrect min cut value."); |
310 |
311 |
311 max_flow.flowMap(flow); |
312 max_flow.flowMap(flow); |
312 |
313 |
313 NodeIt tmp1(g, s); |
314 NodeIt tmp1(g, s); |
314 ++tmp1; |
315 ++tmp1; |
378 EdmondsKarp<GR, CM2> >(); |
379 EdmondsKarp<GR, CM2> >(); |
379 |
380 |
380 // Check Preflow |
381 // Check Preflow |
381 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1; |
382 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1; |
382 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; |
383 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2; |
383 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(); |
384 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3; |
384 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(); |
385 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13); |
|
386 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13); |
|
387 checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13); |
385 |
388 |
386 checkInitPreflow(); |
389 checkInitPreflow(); |
387 |
390 |
388 // Check EdmondsKarp |
391 // Check EdmondsKarp |
389 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1; |
392 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1; |
390 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; |
393 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2; |
391 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(); |
394 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3; |
392 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(); |
395 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13); |
|
396 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13); |
|
397 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13); |
393 |
398 |
394 return 0; |
399 return 0; |
395 } |
400 } |