[Boost-users] Re: boost::graph adding verticies and edges whilst performing a dfs

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-09-01 09:00:52

Hi Daren,

> Greetings all ,
> 
> I have a quick question regarding the boost graph library and depth
> first search operations.
> 
> I have a very large graph , which has a visitor attached to the
> depth_first_search routine.  The Visitor may add in more verticies /
> Edges when visiting an existing vertex in the Graph. (NOTE :: All the
> added verticies / edges from the visitor are guaranteed to be higher in
> the graph structure!  i.e. the DFS algorithm would not have processed
> them at time of insertion. )

What's 'higher'. You mean that all the edges are from vertices that dfs has
not visited yet?

> My question is can the depth_first_search handle changes to the Graph
> whilst it is performing its operation ?  From my observations of the
> colour map used I dont think this is possible with the core
> depth_first_search routine in the library , could someone confirm this ,
> and if anyone has ideas on how this can be performed I would be most
> grateful to hear their thoughts !

I think that if you add new vertices, the algorithm may crash when accessing
property maps. You can use vector_property_map which resized automatically
and so don't have this problem.

For new edges, if the answer to the question above is "yet", then it should
work. 

- Volodya