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-20 09:20:09

#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:          
--------------------------------------+-------------------------------------
Changes (by jan.hazla@…):

  * status:  closed => reopened
  * resolution:  fixed =>

Comment:

 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.

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