Re: [Boost-users] [BGL] Problems with planar_face_traversal

Subject: Re: [Boost-users] [BGL] Problems with planar_face_traversal
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2011-05-22 15:16:48

On Sun, May 22, 2011 at 2:39 PM, "Ulrich Küttler"
<ulrich.kuettler_at_[hidden]> wrote:
>>
>>I'd love to help out - can you give a self-contained example that
>>doesn't use read_graphviz and your dot file (e.g., construct the graph
>>in the code)? Or, failing that, maybe just describe what's going wrong
>>and how that differs from what you expect to see?
>>
>
> Hi Aaron,
>
> thanks a lot. Here is a self-contained version of my example. The graph is the same. I used boost 1.46.1 on gcc linux to run it.
>
> The graph contains 22 vertices and is supposed to look like this:
>
>  0--- 4--- 6--- 8---10---12---14---16---18---20--- 1
>  |    |    |    |    |    |    |    |    |    |    |
>  2--- 5--- 7--- 9---11---13---15---17---19---21--- 3
>
> Thus, there are 10 faces with 4 vertices each and one face with 22 vertices. At least that is what I suppose there should be.
>
> However, the face traversal results in the following faces (vertices):
>
> 0 12 17 16
> 12 0 16 18 19 17
> 1 13 14 15
> 13 1 15 14 11 9 8 10
> 2 3 5 7 6 4
> 3 2 20 18 16 17 19 21
> 2 4 5 3 21 20
> 5 4 6 8 9 7
> 6 7 9 11 10 8
> 10 11 14 13
> 19 18 20 21
>

Hi Ulrich,

The diagram you drew above doesn't match the edges you've created in
test_planar2.cpp (for example, test_planar2.cpp adds the edge (0,12),
but that edge doesn't appear in your diagram.) So I'm working off of
the diagram, not the edges you've added in the file, since it's pretty
clear to me what's going on in your diagram.

What you're getting back is a valid face traversal, as far as I can
tell - I drew it out based on the output and it looks correct (I
modified test_planar2.cpp to reflect the graph you drew above.) The
problem is in your assertion that there are 10 faces with 4 vertices
each and one face with 22 vertices.

Recall that a "planar embedding" is any clockwise arrangement of the
adjacent vertices around each vertex in a planar graph. The important
fact to realize is that for any planar graph, there's not necessarily
one unique planar embedding. The set of faces of a planar graph are a
function of the planar embedding, not unique to the graph itself, so
there might also be many correct decompositions of a planar graph into
a set of faces. In your drawing, you've singled out one particular
planar embedding that has 10 faces with 4 vertices each and one face
with 22 vertices, but in your code, you're allowing the BGL to create
a planar embedding for you which is not the same as the planar
embedding you have in mind. If you were to manually create the planar
embedding you have in mind above instead, you'd see the face traversal
output you expect.

-Aaron