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

Subject: Re: [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-23 22:39:31

#6033: Lowpoint map calculated by biconnected_components(...) is sometimes wrong
--------------------------------------+-------------------------------------
  Reporter:  andre.dau@…              |       Owner:  jewillco
      Type:  Bugs                     |      Status:  reopened
 Milestone:  To Be Determined         |   Component:  graph   
   Version:  Boost Development Trunk  |    Severity:  Problem 
Resolution:                           |    Keywords:          
--------------------------------------+-------------------------------------

Comment (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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/6033#comment:5>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.