Ticket #6033 (closed Bugs: fixed)
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|
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).
- Status changed from closed to reopened
- Resolution fixed deleted