Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] question about connected_components()
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-01-24 16:03:19

On Mon, 23 Jan 2012, Andriy Gapon wrote:

> on 23/01/2012 21:56 Jeremiah Willcock said the following:
>> On Thu, 19 Jan 2012, Andriy Gapon wrote:
>>> This page:
>>> says "The connected_components() functions compute the connected components of
>>> an _undirected_ graph using a DFS-based approach." [emphasis mine]
>>> Looking here:
>>> I see somewhat some unexpected things.
>>> o Only the first variant asserts that the graph is undirected, in the second
>>> variant the assert is commented out - why is that?
>> I don't know for sure, but the likely reason is to allow the use of a directed
>> graph that has each edge inserted in both directions.
> Right. But then, IMO, either both functions should support that or neither.

Yes, they probably should be the same.

>>> o Both variants use depth_first_search() and not undirected_dfs(), which would
>>> seem to be more logical for the undirected case - why?
>> I don't know.
> Fair enough.
>>> Despite the above questions I actually want to use connected_components() [and
>>> not strong_components()] for a directed graph. Should that be possible? Does
>>> it make sense?
>> Do you want to compute the weak components of the graph? I.e., do you want the
>> connected components that would be present if you ignored edge directions?
> Yes, exactly!

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.

-- Jeremiah Willcock

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