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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-10-30 01:31:43

Hi Jeremy,

> > It now tests all edges in transitive closure are valid,
> > but it
> > does not test that transitive closure has all edges.
>
> I've added the test for all edges.

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

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?

> > 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.
>
> I've checked in your fixes.

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?

> > 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.
>
> It may need my special version of nuweb. I'll look into this later.

Okay.

- Volodya