From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-03-17 22:58:00
On Mar 17, 2005, at 2:08 PM, John Donovan wrote:
> [snip quadtree search explanation]
> What I'm thinking is writing a custom visitor, and overriding
> discover_vertex() to do the test. If the test fails, colour the vertex
> to fool the algorithm into thinking it's searched this vertex's
> children. If the test succeeds, then I add the vertex to a list. When
> the search is over, I can play around with the list to my heart's
> content.
Interesting approach. I have another potential algorithm; see below.
> 1) Should I use depth_first_visit to handle the early termination?
Sure.
> 2) If so, how can I determine if a vertex has children before they're
> visited?
>
> 3) Can I colour the vertices before the algorithm does, thus fooling it
> into skipping the vertex's children?
It's a dirty trick, but you can do that :)
> 4) Which colour should I use?
"Gray" would mean that the vertex is in the process of being visited
(probably not what you want), "Black" would mean that the vertex has
already been visited (probably exactly what you want).
The search you described sounds like a depth-first search that actively
filters out vertices that don't meet particular criteria. So, the
easiest solution is I think to use the filtered_graph<> adaptor, where
your vertex predicate tests to see if each vertex (or target of an
edge) meets the criteria you mentioned above. Just pass the adapted
graph to depth_first_visit, and the algorithm will essentially go
directly to the node you are looking for, because all other nodes have
been filtered out completely.
Doug