Re: [Boost-users] [BGL] Modifying graph in BFS

Subject: Re: [Boost-users] [BGL] Modifying graph in BFS
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-04-16 15:43:06

On Sat, 16 Apr 2011, Michal Sekletar wrote:

> Hello everyove,
>
> I have a question about BGL. I want to traverse through graph using BFS 
> and before actual algorithm I want to remove from graph structure 
> (adjacency_list) some vertices and all edges connected to these 
> vertices, so I wrote my own visitor class and implemented 
> initliaze_vertex method to do check on every vertex (it's property) if 
> it's satisfied then I iterate through all edges in graph and i store 
> iterators to edges - edge must be connected to current vertex. Then I 
> want to remove these edges and vertex itself. I store edge iterators for 
> edges connected to vertex I want to remove, because I understand that 
> calling remove_edge directly, while iterating through edges will lead to 
> undefined behavior (if edges are stored in vector - removing invalidates 
> iterators). My problem is that I can't compile source file, compiler is 
> complaining about template instantiation(error message is very long and 
> I don't understand what is cause of the problem) Any ideas, suggestions, 
> code snippets, how to solve this issue would be much appreciated.

It will be hard to do what you want because of the iterator invalidation 
issues you mention.  Is it possible to use a filtered_graph to remove the 
vertices instead?  Do you need to have the vertices filtered out during 
the BFS, or just afterwards?  The task will be fairly easy if the latter 
is true, since you can just keep a property map of vertices to remove and 
then apply the filter after BFS.  If you do need to change the graph 
during the BFS, I do not remember all of the invalidation issues with 
filtered_graph and changing the filter during a traversal, but it is 
likely to work better than remove_vertex and remove_edge on a mutable 
graph.

-- Jeremiah Willcock