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