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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2003-10-29 12:13:07

Hi David, Volodya,

Thanks for finding this bug, I'll get the fix in later today.

Cheers,
Jeremy

On Wednesday, October 29, 2003, at 05:29 AM, Vladimir Prus wrote:

> 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
> <transitive_closure.hpp.diff>__________________________________________ 
> _____
> Unsubscribe & other changes:  
> http://lists.boost.org/mailman/listinfo.cgi/boost