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 16:42:12

on 25/01/2012 23:27 Jeremiah Willcock said the following:
> 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.

Thank you!

>> 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.

Oh, I see, thank you again.

-- 
Andriy Gapon