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

From: Jeffrey Holle (jeff.holle_at_[hidden])
Date: 2004-11-23 21:41:54

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"];
}