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.
