Boost logo

Boost Users :

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

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at