Modify

Ticket #6033 (closed Bugs: fixed)

Opened 2 years ago

Last modified 2 years ago

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

Reported by: andre.dau@… Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost Development Trunk Severity: Problem
Keywords: Cc:

Description

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).

Attachments

biconnected_components.patch Download (789 bytes) - added by andre.dau@… 2 years ago.
Suggested patch
bug_biconnected_components.cpp Download (953 bytes) - added by andre.dau@… 2 years ago.
Small program which shows the bug
75067_counterexample.cpp Download (458 bytes) - added by Jan Hazla <jan.hazla@…> 2 years ago.
Counterexample that breaks the fix in rev. 75067
patchfile.patch Download (5.0 KB) - added by Jan Hazla <jan.hazla@…> 2 years ago.
Proposed patch for fixing the lowpoint problem

Change History

Changed 2 years ago by andre.dau@…

Suggested patch

Changed 2 years ago by andre.dau@…

Small program which shows the bug

comment:1 Changed 2 years ago by anonymous

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

comment:2 Changed 2 years ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

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

comment:3 Changed 2 years ago by jan.hazla@…

  • Status changed from closed to reopened
  • Resolution fixed deleted

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.

comment:4 Changed 2 years ago by jan.hazla@…

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

Changed 2 years ago by Jan Hazla <jan.hazla@…>

Counterexample that breaks the fix in rev. 75067

Changed 2 years ago by Jan Hazla <jan.hazla@…>

Proposed patch for fixing the lowpoint problem

comment:5 Changed 2 years ago by 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.

comment:6 Changed 2 years ago by jewillco

  • Status changed from reopened to closed
  • Resolution set to fixed

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

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.