Re: [Boost-users] BGL connected_components for directed graphs

Message: 1 Date: Thu, 2 Mar 2006 15:53:40 -0500 From: Doug Gregor Subject: Re: [Boost-users] BGL connected_components for directed graphs To: boost-users@lists.boost.org Message-ID: Content-Type: text/plain; charset=US-ASCII; format=flowed

On Feb 28, 2006, at 4:28 AM, Gavin Band wrote: <snip>

...

Presumably this is some meta-program's way of telling me that my graph isn't undirected.

Yes, that's what it's doing. connected_components() only works on undirected graphs.

...

Is there any way to make this work for an directed graph?

You can use the facilities for incremental connected components. Those will work on an undirected graph. In truth, our connected_components() should be modified to decide between the DFS-based algorithm for undirected graphs and the incremental algorithm for directed graphs.

Doug

Thank you for your answer - I will try that. However, I have some comments - forgive me if these have been made before or are just wishful thinking. As a mathematician, I tend to think of a directed graph as being also an undirected graph, just by forgetting the orientation of the edges. Then it should make sense to take connected_components() of any graph, directed or undirected, just by treating it as an undirected graph. However, I realise this conception may be naive in the context of the BGL, which has to deal with ways to store edges and their directions. Still - my graph seems to meet all of the formal requirements for connected_components, but to fail the (apparently informal) requirement that it be undirected (Under "Graph Concepts" in the documentation there is a discussion of directed vs. undirected graphs, but this stops short of a formal definition, unless I have misunderstood). Do think it is possible 1) to formalise the requirements for directed and undirected graphs, and 2) to write a graph adaptor undirected_graph<> which turns a directed graph G into its corresponding undirected graph H? Better yet, to use this (or some other method) to make the algorithms work for all graphs that they make (mathematical) sense for? Perhaps there are good reasons why this is not possible. Anyway, thanks again, Gavin.