| 1 | r""" |
|---|
| 2 | A module for computing the genus and possible embeddings of a graph. |
|---|
| 3 | |
|---|
| 4 | AUTHOR: |
|---|
| 5 | -- Emily A. Kirkman (2007-07-21): initial version |
|---|
| 6 | |
|---|
| 7 | """ |
|---|
| 8 | |
|---|
| 9 | #***************************************************************************** |
|---|
| 10 | # Copyright (C) 2007 Emily A. Kirkman |
|---|
| 11 | # |
|---|
| 12 | # Distributed under the terms of the GNU General Public License (GPL) |
|---|
| 13 | # http://www.gnu.org/licenses/ |
|---|
| 14 | #***************************************************************************** |
|---|
| 15 | |
|---|
| 16 | def nice_copy(g): |
|---|
| 17 | """ |
|---|
| 18 | Creates a 'nice' copy of the graph (with vertices labeled |
|---|
| 19 | 0 through n-1). Also copies the boundary to be in the |
|---|
| 20 | same order with (possibly) new vertex labels. |
|---|
| 21 | |
|---|
| 22 | INPUT: |
|---|
| 23 | graph -- the graph to make a nice copy of |
|---|
| 24 | |
|---|
| 25 | EXAMPLES: |
|---|
| 26 | sage: from sage.graphs import graph_genus1 |
|---|
| 27 | sage: G = graphs.PetersenGraph() |
|---|
| 28 | sage: G.set_boundary([0,1,2,3,4]) |
|---|
| 29 | sage: H = graph_genus1.nice_copy(G) |
|---|
| 30 | sage: H == G |
|---|
| 31 | True |
|---|
| 32 | sage: J = Graph({'alpha':['beta', 'epsilon'], 'gamma':['beta', 'epsilon']}) |
|---|
| 33 | sage: K = graph_genus1.nice_copy(J) |
|---|
| 34 | sage: K == J |
|---|
| 35 | False |
|---|
| 36 | sage: J.set_boundary(['beta','alpha']) |
|---|
| 37 | sage: L = graph_genus1.nice_copy(J) |
|---|
| 38 | sage: L.get_boundary() |
|---|
| 39 | [1, 0] |
|---|
| 40 | """ |
|---|
| 41 | boundary = g.get_boundary() |
|---|
| 42 | graph = g.copy() |
|---|
| 43 | |
|---|
| 44 | newboundary = [] |
|---|
| 45 | relabeldict = {} |
|---|
| 46 | i = 0 |
|---|
| 47 | for v in graph.vertices(): |
|---|
| 48 | relabeldict[v] = i |
|---|
| 49 | i += 1 |
|---|
| 50 | if boundary is not None: |
|---|
| 51 | for v in boundary: |
|---|
| 52 | newboundary.append(relabeldict[v]) |
|---|
| 53 | graph.relabel(relabeldict) |
|---|
| 54 | graph.set_boundary(newboundary) |
|---|
| 55 | if hasattr(g,'__embedding__'): |
|---|
| 56 | emb = g.__embedding__ |
|---|
| 57 | for vertex in emb: |
|---|
| 58 | for nbr in emb[vertex]: |
|---|
| 59 | nbr = relabeldict[nbr] |
|---|
| 60 | vertex = relabeldict[nbr] |
|---|
| 61 | graph.__embedding__ = emb |
|---|
| 62 | return graph |
|---|
| 63 | |
|---|
| 64 | def trace_faces(graph, rot_sys): |
|---|
| 65 | """ |
|---|
| 66 | A helper function for finding the genus of a graph. |
|---|
| 67 | Given a graph and a combinatorial embedding (rot_sys), |
|---|
| 68 | this function will compute the faces (returned as a list |
|---|
| 69 | of lists of edges (tuples) of the particular embedding. |
|---|
| 70 | |
|---|
| 71 | Note -- rot_sys is an ordered list based on the hash order |
|---|
| 72 | of the vertices of graph. To avoid confusion, it might be |
|---|
| 73 | best to set the rot_sys based on a 'nice_copy' of the graph. |
|---|
| 74 | |
|---|
| 75 | INPUT: |
|---|
| 76 | graph -- a graph to compute the faces of |
|---|
| 77 | rot_sys -- the combinatorial embedding of graph (an |
|---|
| 78 | ordered list by vertex hash order) |
|---|
| 79 | |
|---|
| 80 | EXAMPLES: |
|---|
| 81 | sage: from sage.graphs import graph_genus1 |
|---|
| 82 | sage: J = Graph({'alpha':['beta', 'epsilon'], 'gamma':['beta', 'epsilon']}) |
|---|
| 83 | sage: J.set_boundary(['beta','alpha']) |
|---|
| 84 | sage: K = graph_genus1.nice_copy(J) |
|---|
| 85 | sage: rot = [] |
|---|
| 86 | sage: for node in K.vertices(): |
|---|
| 87 | ... rot.append(K[node]) |
|---|
| 88 | sage: rot |
|---|
| 89 | [[1, 2], [0, 3], [0, 3], [1, 2]] |
|---|
| 90 | sage: graph_genus1.trace_faces(K,rot) |
|---|
| 91 | [[(0, 1), (1, 3), (3, 2), (2, 0)], [(1, 0), (0, 2), (2, 3), (3, 1)]] |
|---|
| 92 | """ |
|---|
| 93 | from sage.sets.set import Set |
|---|
| 94 | |
|---|
| 95 | # Make dict of node labels embedding |
|---|
| 96 | comb_emb = {} |
|---|
| 97 | labels = graph.vertices() |
|---|
| 98 | for i in range(len(rot_sys)): |
|---|
| 99 | comb_emb[labels[i]] = rot_sys[i] |
|---|
| 100 | |
|---|
| 101 | # Establish set of possible edges |
|---|
| 102 | edgeset = Set([]) |
|---|
| 103 | for edge in graph.edges(): |
|---|
| 104 | edgeset = edgeset.union(Set([(edge[0],edge[1]),(edge[1],edge[0])])) |
|---|
| 105 | |
|---|
| 106 | # Storage for face paths |
|---|
| 107 | faces = [] |
|---|
| 108 | path = [] |
|---|
| 109 | for edge in edgeset: |
|---|
| 110 | path.append(edge) |
|---|
| 111 | edgeset -= Set([edge]) |
|---|
| 112 | break # (Only one iteration) |
|---|
| 113 | |
|---|
| 114 | # Trace faces |
|---|
| 115 | while (len(edgeset) > 0): |
|---|
| 116 | neighbors = comb_emb[path[-1][-1]] |
|---|
| 117 | next_node = neighbors[(neighbors.index(path[-1][-2])+1)%(len(neighbors))] |
|---|
| 118 | tup = (path[-1][-1],next_node) |
|---|
| 119 | if tup == path[0]: |
|---|
| 120 | faces.append(path) |
|---|
| 121 | path = [] |
|---|
| 122 | for edge in edgeset: |
|---|
| 123 | path.append(edge) |
|---|
| 124 | edgeset -= Set([edge]) |
|---|
| 125 | break # (Only one iteration) |
|---|
| 126 | else: |
|---|
| 127 | path.append(tup) |
|---|
| 128 | edgeset -= Set([tup]) |
|---|
| 129 | |
|---|
| 130 | if (len(path) != 0): faces.append(path) |
|---|
| 131 | return faces |
|---|
