With a bidirectional graph, I consider the answer to "Is it a connected graph?" or "Is it a strongly connected graph?" equal. 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. I've attached an example graph that has 3 issolated components as I consider them. 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. Doug Gregor wrote:
On Nov 23, 2004, at 6:24 PM, Jeffrey Holle wrote:
Interesting. I will have to check out the new 1.32.0 stuff.
The subgraph issue that I mentioned may need more of an explaination. I create derived subgraphs with create_subgraph(VertexIterator first, VertexIterator last) method of subgraph. This causes the edges that are "local" to the included vertex descriptors to be added to this derived subgraph.
I find that internal properties of such a graph are not those of the base(root) graph. I know this because my property classes hold an interface pointer which is NULL when constructed with the default constructor. In my application, this is an invalid object which causes segment faults to occur.
That's actually a surprisingly tough problem to solve given the way subgraph is implemented... I'll have to think about it a bit, but it would help me remember if it's in the bug tracker.
I've another issue that I'd really like to see changed. It has to do with the connected_components.hpp algorithm. There is a concept check, at line 99, which insists that the type of graph be undirected. I have to comment this line out every time I update my boost library.
In my application, my graph is bidirectional.
I don't see how that algorithm will work properly with directed graphs, because the DFS could miss part of the component when it chooses the wrong starting vertex in the group. Incremental connected components could work, or we could build a graph adaptor that turns a bidirectional graph into an undirected graph (which might be generally useful).
I am writting a diagram layout procedure and need to split the problem into multiple graphs if there are isolated components in the original graph because my layout algorithm only works on connected graphs.
I've tried the other connected algorithms and they do not provide the proper answer for this application.
You mean strongly connected components? Or the incremental connected components implementation?
I'd like to add both these issues to a bug system.
Thanks!
Can you provide a link?
http://sourceforge.net/tracker/?group_id=7586
Doug
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"]; }