Hello Cigdem, On Tue, 2007-05-29 at 15:27 +0100, Cigdem Gueler wrote:

I have sent one more email previously. I 've got my little example for which Bellman-Ford fails to detect an existing negative cycle. This occurs after I modify the graph!

I would be glad if you could help me. Bellman-Fors shortest paths is a very important routine for my code, which I have to call several times. And it has to work reliably so that the rest of the code also does...

Thank you for reporting this bug with such a concise program and test graph! It turns out that the BGL code meant to handle overflow when relaxing edges in the shortest-paths algorithms was incorrect. It concluded that, for example, -3 + 1 = infinity. The patch below can be applied in the boost/graph subdirectory to correct the error in relax.hpp. Or, just replace the definition of closed_plus in that file with: template <class T> struct closed_plus { T operator()(const T& a, const T& b) const { using namespace std; T zero(0); T result = a + b; if (result < zero && a >= zero && b >= zero) return (numeric_limits<T>::max)(); return result; } }; It is probably too late to get this fix into Boost 1.34.1, but I'll try. Thank you again for the excellent bug report... it made tracking down this particular bug far simpler. - Doug Index: relax.hpp =================================================================== RCS file: /cvsroot/boost/boost/boost/graph/relax.hpp,v retrieving revision 1.25 diff -u -r1.25 relax.hpp --- relax.hpp 6 Feb 2006 22:12:57 -0000 1.25 +++ relax.hpp 29 May 2007 15:09:28 -0000 @@ -22,15 +22,12 @@ template <class T> struct closed_plus { - // std::abs just isn't portable :( - template <class X> - inline X my_abs(const X& x) const { return x < 0 ? -x : x; } - T operator()(const T& a, const T& b) const { using namespace std; - T inf = (numeric_limits<T>::max)(); - if (b > 0 && my_abs(inf - a) < b) - return inf; - return a + b; + T zero(0); + T result = a + b; + if (result < zero && a >= zero && b >= zero) + return (numeric_limits<T>::max)(); + return result; } };