Re: [Boost-users] BGL connected_components for directed graphs
Message: 1 Date: Thu, 2 Mar 2006 15:53:40 -0500 From: Doug Gregor <dgregor@cs.indiana.edu> Subject: Re: [Boost-users] BGL connected_components for directed graphs To: boost-users@lists.boost.org Message-ID: <a3b58932f7664328bbd614fec82f1a0e@cs.indiana.edu> 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.
On Mar 3, 2006, at 4:42 AM, Gavin Band wrote:
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.
Mathematically, that is correct. In practice there are real issues that make it a bit harder to do with most existing graph data structures. For instance, when storing a directed graph, one only stores the edge (u, v) as part of the vertex u; however, an undirected graph needs to be able to access (u, v) from v as well. That requires some extra storage and computation.
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
I'm not sure where to draw the formal/informal line. Concepts are by nature very informal. The discussion of directedness should probably mention explicitly that directed_category will be either convertible to directed_tag (for directed graphs) or undirected_tag (for undirected graphs).
2) to write a graph adaptor undirected_graph<> which turns a directed graph G into its corresponding undirected graph H?
It is doable. The adaptor would need to scan the graph to build in- edge lists, then deal with flipping the source/target of the underlying descriptors as necessary.
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.
This is definitely possible. Connected components, for instance, will have a different implementation for directed graphs as for undirected graphs, but both would have the same interface. It's definitely doable, and we would love to integrate that functionality into the BGL. I'm not sure when or if we'll find the time to write it ourselves. Doug
participants (2)
-
Douglas Gregor -
Gavin Band