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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-03-09 10:51:42

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