[Graph] A minor bug of the max-flow algorithm?
Hi there, It seems that when searching a network maxflow, if the source and sink are the same vertex, the max-flow function in BGL will create some invalid data and cause the program to crash. To reproduce, simply change the "max_flow.dat" in libs\graph\example, and change the "s" and "t" to be the same vertex. Then compile the " edmunds-karp-eg.cpp". When run "edmunds-karp-eg < max_flow.dat", Windows will give me a crash message. I am using boost 1.34.0 with MS Visual Studio Express 2005 on Win XP2. It seems that the following line 62 of edmunds_karp_max_flow.hpp is having an error: delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[e]) I admit that generally it doesn't make sense to have the source and sink at the same vertex, but I think it will be nicer if the program can check for this simple case... Just to point this out so the author could fix it if s/he thinks it is necessary. Thanks, Da
On 8/1/07, Da Wang
Hi there,
It seems that when searching a network maxflow, if the source and sink are the same vertex, the max-flow function in BGL will create some invalid data and cause the program to crash.
I could reproduce the crash with edmunds_karp_max_flow, but it asserts with kolmogorov_max_flow. My proposal is to add an assertion on src!=sink. Jeremy? Cheers, Stephan
participants (2)
-
Da Wang
-
Stephan Diederich