[Boost-bugs] [Boost C++ Libraries] #10222: root map not correctly computed by strong_components

Subject: [Boost-bugs] [Boost C++ Libraries] #10222: root map not correctly computed by strong_components
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-07-21 19:52:23

#10222: root map not correctly computed by strong_components
------------------------------+----------------------
 Reporter:  Alex <alxlaus@…>  |      Owner:  jewillco
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  graph
  Version:  Boost 1.56.0      |   Severity:  Problem
 Keywords:                    |
------------------------------+----------------------
 I think in boost::graph strong_components does not compute the root map as
 claimed in the documentation, i.e., that it maps each vertex to the  root
 of the corresponding scc.

 For a counter-example consider the following graph (attached as a MWE):

   a <-> b <-> c

 Suppose the algorithm starts with node a. The protocol of the algorithm is
 as follows, the first column being the discovery time, the second being
 the content of the root map, and * indicating uninitialized values:

 1) a -> (0, a), b -> (*, *), c -> (*, *)  // discovered a

 2) a -> (0, a), b -> (1, b), c -> (*, *)  // discovered b

 3) a -> (0, a), b -> (1, b), c -> (2, c)  // discovered c

 4) a -> (0, a), b -> (1, b), c -> (1, b)  // finished c

 5) a -> (0, a), b -> (0, b), c -> (1, b)  // finished b

 6) a -> (0, a), b -> (0, a), c -> (1, b)  // finished a

 The value of the root map for c is 1, correct would be 0.

 The output of the example is as follows:[[BR]]
 The example graph:[[BR]]
 a --> b [[BR]]
 b --> a c [[BR]]
 c --> b [[BR]]
 [[BR]]
 Vertex a is in component 0 and has root 0[[BR]]
 Vertex b is in component 0 and has root 0[[BR]]
 Vertex c is in component 0 and has root 1[[BR]]

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