
Boost Users : 
From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 20070529 11:16:15
Hello Cigdem,
On Tue, 20070529 at 15:27 +0100, Cigdem Gueler wrote:
> I have sent one more email previously. I 've got my little example for
> which BellmanFord fails to detect an existing negative cycle. This
> occurs after I modify the graph!
>
> I would be glad if you could help me. BellmanFors 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 shortestpaths 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;
}
};
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net