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

From: David J. Pearce (djp1_at_[hidden])
Date: 2003-10-29 11:07:51

Vladimir Prus wrote:
> 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.

Hey, I've done that and have found no errors after a reasonable amount 
of effort. Before, I could find error cases almost immediately.  It's 
worth noting, however, that my graph generator only generates DAG's 
and so issues involving cycles cannot be uncovered.

Anyway, thanks very much for your help with this!

David J. Pearce

> 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
> 
> 
> ------------------------------------------------------------------------
> 
> Index: transitive_closure.hpp
> ===================================================================
> RCS file: /cvsroot/boost/boost/boost/graph/transitive_closure.hpp,v
> retrieving revision 1.18
> diff -u -r1.18 transitive_closure.hpp
> --- transitive_closure.hpp	12 Feb 2003 08:50:32 -0000	1.18
> +++ transitive_closure.hpp	29 Oct 2003 15:26:07 -0000
> @@ -174,7 +174,7 @@
>        for (tie(adj, adj_last) = adjacent_vertices(u, CG);
>             adj != adj_last; ++adj) {
>          cg_vertex v = *adj;
> -        if (topo_number[v] < successors[v][chain_number[v]]) {
> +        if (topo_number[v] < successors[u][chain_number[v]]) {
>            // Succ(u) = Succ(u) U Succ(v)
>            detail::union_successor_sets(successors[u], successors[v],
>                                         successors[u]);
> @@ -225,6 +225,22 @@
>              vertex u = components[i][k], v = components[i][l];
>              add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
>            }
> +
> +    {
> +      vertex_iterator i, i_end;
> +      for (tie(i, i_end) = vertices(g); i != i_end; ++i) 
> +      {
> +          adjacency_iterator ab, ae;
> +          for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
> +          {
> +              if (*ab == *i)
> +                  // Found a loopback in original graph. Need to add it to
> +                  // transitive closure.
> +                  if (components[component_number[*i]].size() == 1)
> +                      add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
> +          }
> +      }
> +    }
>  
>    }
>  
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost