limiting searches in BGL
Hello, I am just starting to use the BGL, and have been beating my head upon a problem. I am needing to find an irregularly bounded set of points in three dimensional space. The points are within a convex hull and the graph edges are edges in a delaunay triangulation. I want to start at a node known to be on the hull, and crawl through the inside with either depth first or breadth first search. If you are on the hull, you would not allow the search to continue outside the hull. I thought of doing this with a simple visitor, and color the unwanted vertices black. However, from inside the scope of the visitor, I do not believe I can have access to the colors. Several ugly hacks come to mind, but I would like to know if there is an easy way of doing this first? -Jason Crosswhite
Hi Jason, To access the colors, store a color property map in the visitor (pass it into the constructor). Take a look at libs/boost/example/bfs-example2.cpp to see how to access property maps and store them in a visitor. Cheers, Jeremy On Jun 15, 2004, at 4:38 PM, Jason Crosswhite wrote:
Hello,
I am just starting to use the BGL, and have been beating my head upon a problem. I am needing to find an irregularly bounded set of points in three dimensional space. The points are within a convex hull and the graph edges are edges in a delaunay triangulation. I want to start at a node known to be on the hull, and crawl through the inside with either depth first or breadth first search. If you are on the hull, you would not allow the search to continue outside the hull.
I thought of doing this with a simple visitor, and color the unwanted vertices black. However, from inside the scope of the visitor, I do not believe I can have access to the colors. Several ugly hacks come to mind, but I would like to know if there is an easy way of doing this first?
-Jason Crosswhite _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________
Jeremy Siek
On Tue, 15 Jun 2004, Jason Crosswhite wrote:
Hello,
I am just starting to use the BGL, and have been beating my head upon a problem. I am needing to find an irregularly bounded set of points in three dimensional space. The points are within a convex hull and the graph edges are edges in a delaunay triangulation. I want to start at a node known to be on the hull, and crawl through the inside with either depth first or breadth first search. If you are on the hull, you would not allow the search to continue outside the hull.
I thought of doing this with a simple visitor, and color the unwanted vertices black. However, from inside the scope of the visitor, I do not believe I can have access to the colors. Several ugly hacks come to mind, but I would like to know if there is an easy way of doing this first?
I suspect you want a filtered_graph. Just give it predicates that filter out any points outside the hull. The filtered_graph docs are here: http://www.boost.org/libs/graph/doc/filtered_graph.html Doug
Douglas Paul Gregor wrote:
I suspect you want a filtered_graph. Just give it predicates that filter
out any points outside the hull. The filtered_graph docs are here:
http://www.boost.org/libs/graph/doc/filtered_graph.html
Doug
I am not certain, but when I looked at the filtered graph docs, it seemed that a filter was run on every point in the graph. If that is true, it is exactly what I want to avoid. Hopefully I'm wrong. -Jason
On Tue, 15 Jun 2004, Jason Crosswhite wrote:
Douglas Paul Gregor wrote:
I suspect you want a filtered_graph. Just give it predicates that filter
out any points outside the hull. The filtered_graph docs are here:
http://www.boost.org/libs/graph/doc/filtered_graph.html
Doug
I am not certain, but when I looked at the filtered graph docs, it seemed that a filter was run on every point in the graph. If that is true, it is exactly what I want to avoid. Hopefully I'm wrong.
Then you probably don't want to use filtered_graph, at least not directly :) Essentially, filtered_graph will apply the given predicates to lists of vertices and edges in the graph in a lazy manner. So if you have filtered_graph<...> g(...); for (tie(v, v_end) = vertices(g); v != v_end; ++v) { // ... } then the predicate will be called once for each vertex in the underlying list of vertices. If you just need to do a depth-first search, then just marking black the vertices that you don't want to touch works fine. If you have other graph operations that you need to do, you might want to use filtered_graph to make those vertices invisible. You could store the in hull/out of hull flag in a vertex property and access that from the filtered_graph predicates, if you wanted to compute the information only once but use filtered_graph. Doug
participants (3)
-
Douglas Paul Gregor -
Jason Crosswhite -
Jeremy Graham Siek