Re: [Boost-users] connected component on a directed graph

From: Doug Gregor (dgregor_at_[hidden])
Date: 2007-09-12 16:13:53

On Sep 12, 2007, at 8:06 AM, gast128 wrote:

> Dear all,
>
> I see that it is already posted a lot of times, but i couldn't find  
> an answer.
> Baiscally we want the connected component given a vertex given a  
> directed
> graph.
>
> So a -> b -> c
>      -> d
>
>     e -> f
>
> would give {a, b, c, d} given b
>
> - for directed graphs there is only the strong component algorithm
> - for undirected graph there is an algorithm
> - there seems no adapter to fool the Bgl for interpreting a  
> directed graph as
> undirected.

You can use the "incremental" connected components approach to  
compute connected components for a directed graph:

        http://www.boost.org/libs/graph/doc/incremental_components.html

        - Doug