[sage-support] Re: graph.trace_faces() gives me inconsistent results

[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()
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

-- 
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 email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] 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'

-- 
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 email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.