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