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: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2010-08-04 04:12:38

> 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...

thanks,
Anders