
Boost Users : 
Subject: Re: [Boostusers] [BGL] question about connected_components()
From: Andriy Gapon (avg_at_[hidden])
Date: 20120125 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 doublecheck 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net