Re: [Boost-users] [BGL] question about connected_components()

Subject: Re: [Boost-users] [BGL] question about connected_components()
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-01-25 16:27:45

On Wed, 25 Jan 2012, Andriy Gapon wrote:

> on 24/01/2012 23:03 Jeremiah Willcock said the following:
>> In order to do that, the easiest way is to create a new undirected graph from
>> your original graph, adding each directed edge as an undirected edge in the new
>> graph.  If you have very large graphs, there are (more complicated) ways to do
>> that without extra memory utilization, but this approach involves the least
>> effort and works unless your graphs are very large or you are doing this
>> operation many times.
>
> My graph is actually a quite large (directed) adjacency_matrix.
> Actually, I need to run connected_components() on a filtered_graph of the said
> graph (based on edge weight).  So I think that I found a way to achieve what I
> wanted, but I would like to double-check my approach with you.
>
> I arranged my filter to be such that each edge of the filtered graph has an
> opposite edge - for each (u, v) there is a (v, u).  And then I use exactly the
> same approach as boost::connected_components(), but without any limitations on a
> directionality of a graph.

If you have both directions of each edge, the normal connected_components 
code (possibly with the directionality check commented out) should work 
just fine.

> That is, I also use depth_first_search().
> I think that since depth_first_search() colors only the vertices, then it should
> work on my graph in the same way as it would work on an undirected graph.

Yes, I think so.

> And thus it should find the weekly connected components that I want.
> What do you think?

That's the way I would recommend doing it.

> P.S.
> It seems that the connected_components documentation mentions only the first
> version of the connected_components function.

Having two versions is an implementation detail; the second one implements 
the "= all defaults" part of the signature given in the documentation.

-- Jeremiah Willcock