# [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
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.
```

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:16 UTC