Boost logo

Boost Users :

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at