Boost logo

Boost Users :

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


on 23/01/2012 21:56 Jeremiah Willcock said the following:
> On Thu, 19 Jan 2012, Andriy Gapon wrote:
>
>>
>> This page:
>> http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/connected_components.html
>> says "The connected_components() functions compute the connected components of
>> an _undirected_ graph using a DFS-based approach." [emphasis mine]
>>
>> Looking here:
>> http://www.boost.org/doc/libs/1_48_0/boost/graph/connected_components.hpp
>> 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.

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

Thank you for your interest.

-- 
Andriy Gapon

Boost-users 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