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