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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-11-23 20:56:27

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