boost::graph adding verticies and edges whilst performing a dfs
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. ) 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 !
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
On Sep 1, 2004, at 9:00 AM, Vladimir Prus wrote:
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.
Or use internal properties. With depth_first_search the only property you need is a vertex color property. I didn't even know about vector_property_map before now :) Doug
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
On Sep 1, 2004, at 11:26 AM, Daren Grant wrote:
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.
Be sure to check the chart in the adjacency list documentation to be sure that inserting edges/vertices won't invalidate vertex descriptors and edge descriptors. Otherwise, I think it _should_ work fine. Doug
participants (3)
-
Daren Grant -
Doug Gregor -
Vladimir Prus