id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
10222,root map not correctly computed by strong_components,Alex <alxlaus@…>,Jeremiah Willcock,"
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]]
",Bugs,new,To Be Determined,graph,Boost 1.56.0,Problem,,,alxlaus@…