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

From: Daren Grant (d.grant_at_[hidden])
Date: 2004-09-01 11:26:10

Hi Vladmir ,

> 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?
> 

The answer to this is Yes and No , all but 1 of the edges added will be 
between veticies that have not been visited yet , the 1 edge that is 
added is an in_edge to the node that is currently being processed.

> 
>>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.
> 

Thanks I'll give that a try ....

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