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

From: Gavin Band (gavinband_at_[hidden])
Date: 2006-03-03 04:42:35

> Message: 1
> Date: Thu, 2 Mar 2006 15:53:40 -0500
> From: Doug Gregor <dgregor_at_[hidden]>
> Subject: Re: [Boost-users] BGL connected_components for directed
> 	graphs
> To: boost-users_at_[hidden]
> Message-ID: <a3b58932f7664328bbd614fec82f1a0e_at_[hidden]>
> 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.