[Boost-bugs] [Boost C++ Libraries] #6033: Lowpoint map calculated by biconnected_components(...) is sometimes wrong

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.