Re: [Boost-users] Re: newbie: Graph library - bundled properties

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-11-23 23:55:11

On Nov 23, 2004, at 9:41 PM, Jeffrey Holle wrote:

> With a bidirectional graph, I consider the answer to "Is it a 
> connected graph?" or "Is it a strongly connected graph?" equal.

So we're talking about strongly connected components, then? I'm a bit 
confused because one could potential think of a bidirectional connected 
graph as a graph that would be connected if the edge directions were 
removed, whereas a strongly connected graph is a different beast.

> Be aware that my graph is necessarly bidirectional because I need both 
> the in and out edges of a graph in two areas of my algorithm.  I 
> consider this artifical because there is a default "direction" of each 
> edge, which is the basis of my layout algorithm.

Okay. A bidirectional graph is just a directed graph with access to the 
in-edges.

> I've attached an example graph that has 3 issolated components as I 
> consider them.

> digraph Components {
>   node [ shape = record ];
>   size="6,6";
>   0[label="0",type="Component"];
>   1[label="1",type="Component"];
>   2[label="2",type="Component"];
>   3[label="3",type="Component"];
>   4[label="4",type="Component"];
>   5[label="5",type="Component"];
>   0 -> 1[type="Association"];
>   1 -> 4[type="Association"];
>   4 -> 0[type="Association"];
>   2 -> 5[type="Association"];
> }

I see four strongly connected components: {0, 1, 4}, {2}, {3}, {5}
If I were to remove edge directions and use standard connected 
components, I would get three components {0, 1, 4}, {2, 5}, {3}.

Which result did you intend?

> Its understandable that the subgraph properties issue is a challenge.
> I hope you understand that a "copy" isn't what's needed in derived 
> subgraphs.  Instead the equivalent to a "reference" is
> what's needed.

Yep, I see the problem. It's "hard" mainly because the subgraph 
contains copies of the underlying graph edges, but it's nontrivial to 
rewrite that underlying graph appropriately to turn copies into 
references. Anyway, we'll just have to dig into the subgraph code to 
see what we can do. I definitely agree that the "reference" semantics 
are the desired semantics.

        Doug