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 On Fri, Mar 28, 2014 at 9:24 AM, Christa Brelsford <christa.brelsf...@gmail.com> wrote: > 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. -- 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.