[sage-support] Re: graph.trace_faces() gives me inconsistent results
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 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] Re: graph.trace_faces() gives me inconsistent results
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 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] Re: graph.trace_faces() gives me inconsistent results
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 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] Re: graph.trace_faces() gives me inconsistent results
The problem is not in the trace_faces() method, but in the is_planar() calculation. The embedding of the second graph is not correct: S = Graph(lat) S.show(vertex_size = 600, pos = nodes_dict) S.is_planar(set_embedding = True) s_emb = S.get_embedding() print s_emb {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]} This should be a clockwise listing of the neighbors of each node, i.e. node 1 has one neighbor, 2, node 2 has 3 neighbors that are (clockwise) 1,3,5. Node 3, however, has the correct nodes but are not in a clockwise ordering. 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 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.