[Boost-users] BGL: Early out search

From: John Donovan (JohnD_at_[hidden])
Date: 2005-03-17 14:08:59

Hi,
I'm using the BGL to store a quadtree*. What I want to do is search the
tree, testing each vertex against some criteria. If the test fails, then
I want to ignore all its children for the duration of the search,
because if the parent fails; all its children will fail. If a leaf
vertex passes the test, then the search should finish, otherwise
continue the search. Eventually there will be a path through the tree of
vertices that matched the criteria, and it's this deepest vertex (which
isn't necessarily a leaf vertex) that I want.
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.

1) Should I use depth_first_visit to handle the early termination?

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?

4) Which colour should I use?

*a quadtree is a way of dividing 2D space. Start with a rectangle, which
is represented by the root node. Divide this rectangle into four equal,
non-overlapping quadrants, these become the children of the root node.
Repeat this process for each child until you start paraphrasing Jonathan
Swift. Each node will have either exactly 0 or exactly 4 children.

-John Donovan

The content of this message and any attached file are confidential and/or privileged and are for the intended recipient only. If you are not the intended recipient, any unauthorised use, disclosure, copying, distribution or other dissemination is strictly prohibited. If you receive this message in error please notify the sender immediately by email, telephone or fax and then delete this email. Any attachment with this message should be checked for viruses before it is opened. Magenta Software Limited cannot be held responsible for any failure by the recipient to check for viruses before opening any attachment. Copyright in this email and attachments created by us belongs to Magenta Software Limited. Should you communicate with anyone at Magenta Software Limited by email you consent to us monitoring and reading any such correspondence.