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.