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:
> 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 [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.
