[boost] Re: [BGL] Bug in transitive_closure algorithm?

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-10-29 10:29:32

David J. Pearce wrote:

> I think I've found a bug in the transitive_closure algorithm and I'm
> wondering if people agree it is a bug and/or whether it is already known.

Luckily, I can claim that I'm completely innocent of this bug. It turns out 
that libs/graph/test/transitive_closure_test.cpp was seroiusly changed in 
revision 1.3. It now tests all edges in transitive closure are valid, but it 
does not test that transitive closure has all edges.

When I revert back to version 1.2, the test failes, while it certainly worked 
for me. 

[ time passes ] 

Oh.. my! There are two serious bugs which the buggy testcase did not catch. 
First is the one you've found. Second is that if original graph has a 
loopback, then transitive closure will not have it. Could you grab the fixed 
version from 

     http://zigzag.cs.msu.su:7813/boost/boost/graph/transitive_closure.hpp

and try it. It passes all tests for me. I also attach the diff for reference.

Jeremy, something should be done about it? I think we need to restore the 1.2 
version of the testcase. I'm not sure about code. Could you tell how to 
process transitive_closure.w? I get error from nuweb.

- Volodya