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