Re: [Boost-users] dynamic objects (was Re: PBGL / Dynamic Property Maps complexity)

Subject: Re: [Boost-users] dynamic objects (was Re: PBGL / Dynamic Property Maps complexity)
From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2009-10-05 14:09:20

>
> <...>
>> If your graphs aren't static... PBGL doesn't do well with dynamic  
>> graphs at
>> the moment, they'll *sort of* work... *sometimes* :)
>
> What do you mean by that ? What does not work ?
> I am currently trying to understand whether or not I can use dynamic
> objects stored in bundled properties, or will there be an issue in
> PBGL (when the object will be copied over to another machine) ?

As far as copying objects from machine to machine, you just need to  
specify a serialization method that works for your objects.  With  
regard to the graph itself being dynamic, the CSR graph doesn't  
support addition or removal of vertices or edges post-construction at  
all.  The adjacency list will work just fine with monotonically  
increasing graphs, vertex and edge addition work fine so long as  
you're not also trying to access the adjacency list from another  
thread at the same time.  Note that the adjacency list just uses the  
allocators of the underlying vector and edge containers, there's  
nothing  intelligent going on with regard to memory allocation.

With regards to removing vertices/edges, as with addition, vertices/ 
edges can only be removed locally.  Removing edges should work fine,  
but note that removing an edge from the graph has no effect on any  
associated external property maps, the property values for that edge  
will still exist, and may still be accessed if the edge descriptor is  
cached before the edge is deleted.  Depending on what interface you  
use, removing an edge either removes a single edge, or all parallel  
edges between two vertices.  I believe everything should work  
correctly with regards to removing edges multiple times, removing them  
from both endpoints, etc. but this functionality has not been well  
exercised, let me know if you encounter problems and I'll be happy to  
track them down and fix them or help you do so.

Removing vertices is another matter, currently removing a vertex from  
the distributed adjacency list simply removes that vertex in the  
underlying local adjacency list.  If you first remove all edges  
incident to a vertex, then remove that vertex, you'll get the  
functionality you're likely looking for, and no dangling edges laying  
around.

If you stick with bundled properties you can avoid the headache of  
maintaining external property maps with dynamic graphs.  Also be aware  
of whether algorithms are creating external property maps for you  
during dispatch and if so make sure not to mutate the graph during the  
lifespan of that external property map.

Finally, the "don't assume anything happens until the next  
synchronize() call" rules apply as always.

I think that covers all the 'gotchas' associated with dynamic graphs  
and PBGL.  As mentioned this functionality hasn't seen a lot of use  
(at least not by me or my colleagues at IU) in a while, so if you  
encounter problems let me know and I'll be glad to help.

Cheers,
Nick