Re: [Boost-users] [BGL] Problems with planar_face_traversal
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
On Sun, May 22, 2011 at 2:39 PM, "Ulrich Küttler" <ulrich.kuettler@web.de> 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
participants (2)
-
"Ulrich Küttler" -
Aaron Windsor