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

Subject: Re: [Boost-users] [BGL] Problems with planar_face_traversal
From: Ulrich Küttler (ulrich.kuettler_at_[hidden])
Date: 2011-05-23 05:42:31

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

Hi Aaron,

thank you very much. The diagram is indeed the graph I expected. I did not realize that the planar embedding of the graph is not unique. Now this gives me another problem to solve, since I'm looking for a certain set of faces. My current attempt is to add vertices and edges in order to obtain an unique embedding. However, I'm still working on that.

Thanks for your advice.

Ulrich

___________________________________________________________
Schon gehört? WEB.DE hat einen genialen Phishing-Filter in die
Toolbar eingebaut! http://produkte.web.de/go/toolbar