[boost] [BGL] dag_shortest_paths broken?

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-10-07 10:00:00

Hello,
it appears that the dag_shortest_paths algorithm is broken. The attached 
program tries to find the longest path by changing inf/comparison operators. 
The graph is

0  ----->   1  ------>  2
                ^
                |
3 ----------/

The edge weights are 1 for  0->1 and 1->2 and 2 for 3->1 and I'm searching for 
the longest path starting from '0'. The final result for '2' is 0x7FFFFFFF, 
while I'd expect to get '2'.

The problem is two-fold. First, the algorithm runs topological sort on the 
graph, and process the vertices in topological order -- which include the '3' 
vertex. That vertex is not reachable from '0', so it should not be included 
in the search at all.

The second problem is that the distance to that vertex is set to -inf. When 
combining that distance with edge weight, due to a bug we get +inf. Here's 
the code:

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

When 'a' is -inf (as is for '3') inf - a overflows and gives -1, and when b is 
greater than 1, "inf" is returned.

I think that the right solution is to change the algorithm so that it does not 
traverse the vertices not reachable from the start one. Besides fixing my 
problem, this will also speed up the algorithm. For example, if you have a 
forest and call dag_shortest_path on the root of just one tree, the algorithm 
will travese all trees, setting pretty useless values for all of them.

I would like to commit the attached patch. All tests still pass on gcc when 
it's applied. Comments? 

- Volodya