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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2003-10-30 20:32:27

Hi Vladimir,

On Wednesday, October 29, 2003, at 08:31 PM, Vladimir Prus wrote:
> That's good. However, I think that the test can be simplified. 
> Consider the
> following (pseudo)code.
>
>     for i in vertices(g)
> 	for j in vertices(g)
> 	    bool tc_has_edge;
> 	    tie(..., tc_has_edge) = edge(i, j, tc);
>  	    bool should_have_edge = is_reachable(i, j, g)
>             if (tc_has_edge != should_have_edge)
> 	        return false;
>
> I believe it's equivivalent to the current test.
>

Yes, that is nicer.

> Also, there's still a problem with is_reachable(i, i), which always 
> returns
> true -- I'm not sure how real it is, yet.

Ok, I think I can solve that...

>
> Also if I remove
>
>     if (components[component_number[*i]].size() == 1)
>
> check from my new code, the test still passes. Revision 1.2 did not 
> pass.
> The reason is that the new code only cares if there's edge in 
> transitive
> closure, but allows 2 parallel edges -- that's precisely what the "if"
> statement tries to avoid. How can we test for this problem?
>

I just checked in a new version of the test that tries to solve this.

> Great! The only nit is that the code now have tabs. I've removed them 
> in *.w
> source, maybe I'll commit the change and you'll regenerate hpp?
>

Sure.

Cheers,
Jeremy