[Boost-users] [Graph] A minor bug of the max-flow algorithm?

From: Da Wang (myinfostation_at_[hidden])
Date: 2007-08-01 13:46:17

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