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-04 08:00:40

On Wed, Aug 4, 2010 at 4:12 AM, Anders Wallin
<anders.e.e.wallin_at_[hidden]> wrote:
>> 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.
>
> yes, this is exactly what I want. However I suspect that the planar
> embedding is not unique (?).
> As drawn above if we proceed clockwise the output would indeed be
>  a, d, g, h, e, b, a
> but another planar embedding could for example have the degree-1
> adjacent vertices of c in a completely different order and the output
> would be different.
>
> which means I should probably create the planar embedding myself, and
> not delegate to boyer_myrvold_planarity_test as is done in the
> example. Are there any examples out there of how create a planar
> embedding?
> from the example it looks like a std::vector< std::vector<EdgeDescriptor> >
> would something like this work:
> [ [(a,c)] ]    the row for vertex a. a has only one edge (a,c)
> [ [ (b,c) ] ]       same thing for b
> [ [ (c,b) , (c,a) , (c,d), (c,f)  ]  ]  the row for vertex c. edges
> should be traversed in the order (c,b) then (c,a) then (c,d) then
> (c,f)
> ... and so on...

Yeah, you're right - there can be many planar embeddings for a graph,
and there's no way to specify which one you want
boyer_myrvold_planarity_test to generate. So if you already have an
implicit ordering in the 2D plane on the edges around each vertex in
the graph, you'll want to create the embedding yourself. And yes,
you're on the right track in your example to create a planar embedding
- using a vector of vectors of edges, each edge should appear twice in
the planar embedding, once in the clockwise cyclic order around each
vertex the edge is adjacent to. The planar embedding concept
documentation (http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/PlanarEmbedding.html)
has some more information about what a planar embedding means to the
BGL, although I can't find a link to any code that manually constructs
a planar embedding.

-Aaron