Re: [Boost-users] BGL: Early out search

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