Boost C++ Libraries: Ticket #6033: Lowpoint map calculated by biconnected_components(...) is sometimes wrong

attachment set

andre.dau@… — Wed, 19 Oct 2011 11:51:24 GMT

attachment → biconnected_components.patch

Suggested patch

attachment set

andre.dau@… — Wed, 19 Oct 2011 11:51:48 GMT

attachment → bug_biconnected_components.cpp

Small program which shows the bug

anonymous — Wed, 19 Oct 2011 17:31:01 GMT

Someone jsut pointed out, that my fix is not working for multigraphs. Therefore I revoke the fix. But the issue still remains.

status changed; resolution set

Jeremiah Willcock — Wed, 19 Oct 2011 20:04:00 GMT

status new → closed
resolution → fixed

(In [75067]) Fixed strange use of pred map, and changed algorithm to be more similar to Tarjan paper cited in bibliography; fixes #6033

status changed; resolution deleted

jan.hazla@… — Thu, 20 Oct 2011 09:20:08 GMT

status closed → reopened
resolution fixed

I don't think you fixed it correctly.

Note that when a non-root articulation vertex separates more than two biconnected components, it will be sent to the output iterator more than once. I believe this weird predecessor trick was there exactly to avoid this.

I see two possible fixes to this: 1) I believe that if you

a) change underlying traversal algorithm from depth_first_search to undirected_dfs (why do you use a directed version for undirected algorithm anyway?), b) completely delete the if statement that Andre modified in his patch, since now undirected_dfs magically takes care of that for us;

then the predecessor trick will work correctly. 2) The whole problem stems from the output format insisting on outputting the range of articulation points instead of a map (vertex -> bool) indicating if the vertex is articulating. I guess you won't like changing the interface now, but what you can do is to implement such a map internally and compute the range from it at the very end. In that case you can also get rid of predecessor map, since it's not really necessary in classical Tarjan algorithm implementation. I believe it to be a cleaner solution, but both those changes would be visible in the public interface.

jan.hazla@… — Thu, 20 Oct 2011 09:21:55 GMT

Sorry for broken formatting, hope it's still readable.

attachment set

Sun, 23 Oct 2011 22:26:52 GMT

attachment → 75067_counterexample.cpp

Counterexample that breaks the fix in rev. 75067

attachment set

Sun, 23 Oct 2011 22:27:36 GMT

attachment → patchfile.patch

Proposed patch for fixing the lowpoint problem

Sun, 23 Oct 2011 22:39:31 GMT

I attached: 1) The minimal counterexample that breaks the fix from revision 75067 2) The patch which fixes the problem correctly.

It implements the second idea from my comment above - the algorithm creates internally boolean map indicating if the given point is articulating. When the vertex's processing is finished, the map is checked and the vertex is output at most once. The map is implemented as a vector utilizing vertex_index_map, which is needed anyway for the purpose of depth_first_search. Therefore, the change is invisible for the user.

This is still incorrect in case of multigraph (ie. parallel edges), which is a shame, because Tarjan's algorithm naturally extends to this case. This issue could be solved with implementation using undirected_dfs instead of depth_first_search. Unfortunately, this would require the user to provide the algorithm with the edge color map, which would be a significant interface change breaking most of the existing user code.

status changed; resolution set

Jeremiah Willcock — Sat, 03 Mar 2012 20:06:17 GMT

status reopened → closed
resolution → fixed

(In [77186]) Applied new patch from #6033 from Jan Hazla; fixes #6033