On Tue, Aug 3, 2010 at 1:30 PM, Anders Wallin
my previous explanation of my application was maybe not the clearest, so here is another try: http://tinyurl.com/3aoejnd
looking at the BGL-documentation, would a planar_face_traversal of the outermost/innermost face of my graph traverse the edges/vertices in a useful order for producing the output I want?
thanks, Anders
thanks for all replies, I will try writing an exception-throwing visitor or my own depth-limited bfs.
Really, that approach is likely to have very poor performance for your application. You can use the exception approach once for a very large search, but if you use it repeatedly on very short searches, you won't like the result. filtered_graph is your friend.
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Anders, I'm still not really sure what you're asking after reading that post, but let me give it a shot - if you have a graph that looks like: a | b--c--d | e--f--g | h which I think is what you're describing, basically, then you could use planar_face_traversal to create an "outer border" like the red outline in your post. planar_face_traversal will iterate over the edges of the above graph in sequence like (a,c) (c,d) (d,c) (c,f) (f,g) (g,f) (f,h) (h,f) (f,e) (e,f) (f,c) (c,b) (b,c) (c,a). Take that sequence and keep only the pairs of adjacent duplicate edges: (a,c) (c,d) (d,c) (f,g) (g,f) (f,h) (h,f) (f,e) (e,f) (c,b) (b,c) (c,a) (it's a cyclic order, so we keep (a,c) at the beginning and (c,a) at the end.) Now from each pair of duplicate edges, extract any vertex of degree 1 and you get a, d, g, h, e, b, a which defines the sequence of edges you need to add to get the "outer border": (a,d) (d,g) (g,h) (h,e) (e,b), and (b,a). The same argument applies to getting an "inner border" like the orange outline in your post. Regards, Aaron