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.
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
participants (2)
-
Douglas Gregor -
John Donovan