graph.trace_faces() gives me inconsistent results

[Christa Brelsford]

for a simple graph, trace_faces() gives the expected answer for the faces of a planar graph, as shown below.

import networkx as nx

lat = nx.Graph()
lat.add_edge(1,2)
lat.add_edge(2,3)
lat.add_edge(2,5)
lat.add_edge(3,4)
lat.add_edge(3,5)
lat.add_edge(4,5)

nodes_dict = {}
nodes_dict[1]=(0,0)
nodes_dict[2]=(0,1)
nodes_dict[3]=(0,2)
nodes_dict[4]=(0,3)
nodes_dict[5]=(1,2)


S = Graph(lat)
S.show(vertex_size = 600, pos = nodes_dict)
S.is_planar(set_embedding = True)
s_emb = S.get_embedding()
faces = S.trace_faces(s_emb)

print faces:

[[(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (2, 1)], [(5, 4), (4, 3), (3,
5)], [(2, 5), (5, 3), (3, 2)]]

There are three faces: one between nodes 2,3 and 5, another between nodes 3,4 and 5,and the outside face of all nodes.

but when I extend the graph:

lat = nx.Graph()
lat.add_edge(1,2)
lat.add_edge(2,3)
lat.add_edge(2,5)
lat.add_edge(3,4)
lat.add_edge(3,5)
lat.add_edge(3,9)
lat.add_edge(4,5)
lat.add_edge(4,6)
lat.add_edge(4,7)
lat.add_edge(4,8)
lat.add_edge(4,9)
lat.add_edge(5,6)
lat.add_edge(6,7)
lat.add_edge(7,8)
lat.add_edge(8,9)

nodes_dict = {}
nodes_dict[1]=(0,0)
nodes_dict[2]=(0,1)
nodes_dict[3]=(0,2)
nodes_dict[4]=(0,3)
nodes_dict[5]=(1,2)
nodes_dict[6]=(1,3)
nodes_dict[7]=(0,4)
nodes_dict[8]=(-1,4)
nodes_dict[9]=(-1,3)

S = Graph(lat)
S.show(vertex_size = 600, pos = nodes_dict)
S.is_planar(set_embedding = True)
s_emb = S.get_embedding()
faces = S.trace_faces(s_emb)

print faces

[[(6, 4), (4, 7), (7, 6)], [(3, 2), (2, 5), (5, 3)], [(5, 4), (4, 6),
(6, 5)], [(7, 8), (8, 9), (9, 3), (3, 5), (5, 6), (6, 7)], [(1, 2), (2,
3), (3, 4), (4, 5), (5, 2), (2, 1)], [(4, 9), (9, 8), (8, 4)], [(7, 4),
(4, 8), (8, 7)], [(3, 9), (9, 4), (4, 3)]]

the face that should exist between just nodes 3,4 and 5 is not found, it's replaced with a face around nodes 1,2,3,4,5. Any ideas what is wrong, or other ways of getting an accurate list of the faces in a planar graph?

I'm using 'Sage Version 5.13, Release Date: 2013-12-15'

I realize that trace_faces has been deprecated to just faces() per this discussion: http://trac.sagemath.org/ticket/15551

but when I run
S.faces()

I get the error
AttributeError: 'Graph' object has no attribute 'faces'

[etc...@gmail.com]

The problem is not in the trace_faces() method, but in the is_planar() calculation. The embedding of the second graph is not correct:

S = Graph(lat)
S.show(vertex_size = 600, pos = nodes_dict)
S.is_planar(set_embedding = True)
s_emb = S.get_embedding()

print s_emb

{1: [2], 2: [1, 3, 5], 3: [4, 9, 5, 2], 4: [5, 6, 7, 8, 9, 3], 5: [2, 3,
6, 4], 6: [7, 4, 5], 7: [8, 4, 6], 8: [9, 4, 7], 9: [3, 4, 8]}

This should be a clockwise listing of the neighbors of each node, i.e. node 1 has one neighbor, 2, node 2 has 3 neighbors that are (clockwise) 1,3,5. Node 3, however, has the correct nodes but are not in a clockwise ordering.

[etc...@gmail.com]

On Wednesday, March 26, 2014 5:34:53 PM UTC-6, Christa Brelsford wrote:

[etc...@gmail.com]

On Wednesday, March 26, 2014 5:34:53 PM UTC-6, Christa Brelsford wrote:

[etc...@gmail.com]

Haha, apologies for screwing up the review process. To continue from the previous posts, if you first re-order the embedding to actually be clockwise, then the trace_faces() method works as expected:

import numpy

def reorder_embedding(emb, locs):
new_emb = {}
for i,neighbors in emb.iteritems():
def angle(b):
dx = locs[b][0] - locs[i][0]
dy = locs[b][1] - locs[i][1]
return numpy.arctan2(dx,dy)

reorder_neighbors = sorted(neighbors, key=angle)
new_emb[i] = reorder_neighbors
return new_emb

S = Graph(lat)
S.show(vertex_size = 600, pos = nodes_dict)
S.is_planar(set_embedding = True)
s_emb = S.get_embedding()

s_emb_r = reorder_embedding(s_emb, nodes_dict)

print "SAGE embedding:", s_emb
print "Reordered:", s_emb_r

faces = S.trace_faces(s_emb)
print "SAGE faces:", faces

faces_r = S.trace_faces(s_emb_r)
print "Reordered:", faces_r

SAGE embedding: {1: [2], 2: [1, 3, 5], 3: [4, 9, 5, 2], 4: [5, 6, 7, 8, 9, 3], 5: [2, 3, 6, 4], 6: [7, 4, 5], 7: [8, 4, 6], 8: [9, 4, 7], 9: [3, 4, 8]}
Reordered: {1: [2], 2: [3, 5, 1], 3: [9, 4, 5, 2], 4: [9, 8, 7, 6, 5, 3], 5: [2, 3, 4, 6], 6: [4, 7, 5], 7: [8, 6, 4], 8: [7, 4, 9], 9: [8, 4, 3]}
SAGE faces: [[(6, 4), (4, 7), (7, 6)], [(3, 2), (2, 5), (5, 3)], [(5, 4), (4, 6), (6, 5)], [(7, 8), (8, 9), (9, 3), (3, 5), (5, 6), (6, 7)], [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (2, 1)], [(4, 9), (9, 8), (8, 4)], [(7, 4), (4, 8), (8, 7)], [(3, 9), (9, 4), (4, 3)]]
Reordered: [[(6, 4), (4, 5), (5, 6)], [(4, 7), (7, 8), (8, 4)], [(3, 2), (2, 5), (5, 3)], [(5, 4), (4, 3), (3, 5)], [(8, 7), (7, 6), (6, 5), (5, 2), (2, 1), (1, 2), (2, 3), (3, 9), (9, 8)], [(8, 9), (9, 4), (4, 8)], [(7, 4), (4, 6), (6, 7)], [(3, 4), (4, 9), (9, 3)]]

On Wednesday, March 26, 2014 5:34:53 PM UTC-6, Christa Brelsford wrote:

[Nathann Cohen]

Hellooooooooooooo !

 

for a simple graph, trace_faces()  gives the expected answer for the faces of a planar graph

That's a good news :-D

the face that should exist between just nodes 3,4 and 5  is not found, it's replaced with a face around nodes 1,2,3,4,5.   Any ideas what is wrong, or other ways of getting an accurate list of the faces in a planar graph?

What makes you think that the faces returned by Sage are wrong ? A planar graph can have different planar embeddings, and so different sets of faces.

If you call .show() with a specific position for the vertices, this may result in a planar graph and you may see some faces defined, but there is no reason why .trace_faces() should return the faces using the positions you defined earlier for the plot !

In the documentation, .trace_faces() tells you that it can either find the embedding by itself, or use an "embedding" argument. In you case you did not define the embedding, so trace_faces() finds its own.

As, just before, you called .is_planar(set_embedding=True), the embedding used by traces_faces() is the one that has been found by is_planar. But as you did not give to is_planar() the position of your vertices (and it does not accept positions of vertices as an input anyway),then is computes its own embedding. That's all.

So unless you think that the faces returned by Sage do not correspond to a planar embedding, technically Sage makes no error.

Now, if you want Sage to work with the position of the vertices you used for the plot, what you should do is write a short function which transforms (x,y) positions for the vertices into a combinatorial embedding. Then, you will be able to call .set_embedding() with that embedding, and then trace_faces() will give you the result that you expect, i.e. the faces defined by your embedding.

And if you do that, please contribute to Sage by submitting your code, as I guess this would definitely be useful to others :-)

Good luuuuuuuuuuuuuuuuuuuuuuuuuuuck !

Nathann

[Nathann Cohen]

Oh, I forgot : it is indeed weird that "faces" may not exist in your
version of Sage even though trace_faces is already deprecated,but
everything seems to be fine in Sage 6.2.beta5. Sorry for that, I don't
know where it comes from, but it will be fixed if you update your
install :-)

Nathann

> --
> You received this message because you are subscribed to a topic in the
> Google Groups "sage-support" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/sage-support/X8hc0AlTCB8/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Christa Brelsford]

Nathann,

Thanks for your help!  I'm fairly new to both Sage and graph theory, but I understand the difference you point out, and it looks like the trace faces function is giving me accurate faces for some valid planar embedding- just not the one I thought it was working on.  I spoke with a colleague yesterday, and he helped come up with a solution.  He tried to post his results on this board, but I'm not seeing it, so I'm copy/pasting his solution here.   This is not the most efficient solution, but I've tested in on a variety of real planar graphs, and it does work.

Ethans answer:
the problem is not their algorithm for finding faces, but the embedding.  The embedding should be a clockwise ordering of nodes, but if you look, node 3's neighbors list in the embedding (s_emb[3]) is not clockwise.  If you reorder the nodes, it seems to work.  See below.

import numpy

def reorder_embedding(emb, locs):
    new_emb = {}
    for i,neighbors in emb.iteritems():
        def angle(b):
            dx = locs[b][0] - locs[i][0]
            dy = locs[b][1] - locs[i][1]
            return numpy.arctan2(dx,dy)
       
        reorder_neighbors = sorted(neighbors, key=angle)
        new_emb[i] = reorder_neighbors
    return new_emb

S = Graph(lat)
S.show(vertex_size = 600, pos = nodes_dict)
S.is_planar(set_embedding = True)
s_emb = S.get_embedding()

[Tom Boothby]

Christa,

The problem is not with the code, but your expectations of it (which
may be valid, but that would be a feature request and not a bug). You
expect the code to look at your planar position dictionary, and gin up
an embedding from that. That is not a bad idea, and possibly a good
feature to request.

What is actually happening is that you are asking the code to make a
new embedding, and compute the faces from that embedding. It is not
the same embedding as the one you want. If you gave it a 3-connected
planar graph, of course, the embedding (hence faces) would be unique
(up to orientation)... but your graph is not 3-connected.

To see the embedding those faces correspond to, try

S.is_planar(set_embedding = True, set_pos=True)
S.show()


Regards,
Tom

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an

[Nathann Cohen]

> The problem is not in the trace_faces() method, but in the is_planar() calculation. The embedding of the second graph is not correct:

The is_planar method does not take the nodes_dict dictionary as an
input. Why do you say that its output is incorrect ?

Nathann