Re: [Boost-users] BGL: interrupting breadth_first_search() at a certain distance/predicate?

Subject: Re: [Boost-users] BGL: interrupting breadth_first_search() at a certain distance/predicate?
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2010-08-03 15:51:34

On Tue, Aug 3, 2010 at 1:30 PM, Anders Wallin
<anders.e.e.wallin_at_[hidden]> wrote:
> 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_at_[hidden]
> 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