Lowpoint map calculated by biconnected_components(...) is sometimes wrong

[andre.dau@…]

The lowpoint map calculated by the function biconnected_components(...) is sometimes wrong.

The current implementation seems to relink the predecessor map as an indicator that an articulation point has been found. So even though the real parent in the dfs tree of a node u might be the node v, the predecessor map may temporarily claim that w is u's parent. However, this can lead to instances where the if-statement in line 81 of boost/graph/biconnected_components.hpp fails to recognize tree edges from u to its parent v (since it believes w is the parent). Therefore the body of the if-statement is executed and the lowpoint value is updated when it shouldn't, resulting in wrong lowpoint values.

To reproduce the problem create an undirected graph with 4 vertices (numbered from 0 to 3) and 4 edges, linked in the following way and start the dfs at node 1:

2-3 1-3 1-2 0-1

Clearly, the lowpoint value of node 1 should be 2 but is computed to be 1. I discovered this bug when trying to find bridges in the graph using those lowpoint values.

Attached is working code which exhibits the bug as well as a suggested fix (although in the long term the implementation should not use the hack with the relinking since it could lead to other unwanted behavior).

[andre.dau@…]

Suggested patch

[andre.dau@…]

Small program which shows the bug

[anonymous]

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

[Jeremiah Willcock]

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

[jan.hazla@…]

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@…]

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

[Jan Hazla <jan.hazla@…>]

Counterexample that breaks the fix in rev. 75067

[Jan Hazla <jan.hazla@…>]

Proposed patch for fixing the lowpoint problem

[Jan Hazla <jan.hazla@…>]

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.

[Jeremiah Willcock]

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