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

Subject: Re: [Boost-users] [BGL] question about connected_components()
From: Andriy Gapon (avg_at_[hidden])
Date: 2012-01-25 15:35:56

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.
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.
And thus it should find the weekly connected components that I want.
What do you think?

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

-- 
Andriy Gapon