[Boost-users] Graph: "extra" edge processing during BFS

From: Eric Fowler (eric.fowler_at_[hidden])
Date: 2007-08-29 00:41:12

I have an algorithm that just screams breadth first search. After some
thrashing around in the graph library I am confident in about 90% of the
implementation. However there is one little snag:

When I examine a grey vertex, I want to do some basic logic on the vertex
and the "candidate" next edge to see if what I want to do with this edge and
this vertex is "legitimate", according to my own definition of
legitimacy(*). If the edge is good, I use it, perhaps relaxing it, if not, I
just pass on it and go on to the next one.

I would like to do this without tweaking or rewriting the BFS algo. Can this
be done with just visitors and the various template parameters or must I
write my own BFS variant (not that hard to do of course)?

Eric

* My idea of "legitimate" is to check to see if a path to a given vertex
already contains a certain vertex. The path is built as I run the algorithm.
"Parent" vertices are stored as the algorithm runs so I can follow a chain
up from the examined vertex back to the root.

So the basic logic is:
Vertex u = Q.top(); Q.pop();            vis.examine_vertex(u, g); //this is
already in BFS

if(has_certain_property(u, g)) add_to_tree(u, g);
else do_not_add(u, g);

.... etc.