Re: [Boost-users] Bellman-Ford Example

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;
       }
     };