[BGL] Problems with planar_face_traversal

[Ulrich Küttler]

Hi all,

I'm new to BGL and I already like it a lot. Right now I'm searching for faces in a planar graph. I use boost::planar_face_traversal, however the results I get are confusing. The example I tested consists of 10 faces of 4 vertices each. See side-graph.dot:

dot side-graph.dot -Tps > side-graph.ps

My test code reads that file and calls both boyer_myrvold_planarity_test and planar_face_traversal. The graph itself seems to be fine, the face traversal fails. Is there anything I do wrong here?

Thanks a lot for your help.

Ulrich

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

[Aaron Windsor]

On Sun, May 22, 2011 at 8:41 AM, "Ulrich Küttler"

Post by Ulrich Küttler
Hi all,
dot side-graph.dot -Tps > side-graph.ps
My test code reads that file and calls both boyer_myrvold_planarity_test and planar_face_traversal. The graph itself seems to be fine, the face traversal fails. Is there anything I do wrong here?

Hi Ulrich,

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?

-Aaron

[Ulrich Küttler]

Post by Aaron Windsor
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 
 
Maybe it is a misinterpretation on my part, maybe I did make a mistake. I just don't see it.
 
Ulrich
 
PS: My first example lacked the edge index initialization. The above problem, however, occurs with an initialized edge index.
 
___________________________________________________________
Schon gehört? WEB.DE hat einen genialen Phishing-Filter in die
Toolbar eingebaut! http://produkte.web.de/go/toolbar

[Aaron Windsor]

On Sun, May 22, 2011 at 2:39 PM, "Ulrich Küttler"

Post by Ulrich Küttler

Post by Aaron Windsor
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.
 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.
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

[Ulrich Küttler]

Post by Aaron Windsor
On Sun, May 22, 2011 at 2:39 PM, "Ulrich Küttler"

Post by Ulrich Küttler

Post by Aaron Windsor
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.
 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.
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