Subject: [Boost-bugs] [Boost C++ Libraries] #6033: Lowpoint map calculated by biconnected_components(...) is sometimes wrong
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-10-19 11:50:46
#6033: Lowpoint map calculated by biconnected_components(...) is sometimes wrong
-------------------------------------+--------------------------------------
Reporter: andre.dau@⦠| Owner: jewillco
Type: Bugs | Status: new
Milestone: To Be Determined | Component: graph
Version: Boost Development Trunk | Severity: Problem
Keywords: |
-------------------------------------+--------------------------------------
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).
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/6033> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:07 UTC