From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2007-05-29 11:16:15
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;
}
};