
Boost : 
From: Vladimir Prus (ghost_at_[hidden])
Date: 20050617 08:59:23
Hi,
some time ago I've reported a problem with dag_shortest_paths that occurs when
I'm searching for the *longest* path by appropriately changing inf/compare
operators.
I've fixed that problem by change in dag_shortest_paths.hpp, but looks like
it's back after changes to relax.hpp.
I attach my original report, which has a test program. When using version
1.21 of graph/relax.hpp, it produces the expected outcome '2'. When using
version 1.22, I get 2147483647
Revision 1.22 is:
revision 1.22
date: 27/10/2004 18:38; author: dgregor
Merge from graph_devel_1_33_0 branch
And the only commit on that branch does not clarify anything either:
revision 1.21.8.1
date: 15/10/2004 18:54; author: dgregor
Added several algorithms:
 random graph layout
 FruchtermanReingold layout
 A* search
 FloydWarshall allpairs shortest paths
Fixes for several algorithms:
 Documentation for Johnson allpairs shortest paths
 BellmanFord singlesource shortest paths
Any ideas?
 Volodya
attached mail follows:
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 twofold. 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk