# source:sage/graphs/graph_genus1.py@6439:d5047c175cf3

Revision 6439:d5047c175cf3, 9.3 KB checked in by Mike Hansen <mhansen@…>, 6 years ago (diff)

Initial commit of combinat/ files and bug fixes.

Line
1r"""
2A module for computing the genus and possible embeddings of a graph.
3
4AUTHOR:
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)
14#*****************************************************************************
15
16def nice_copy(graph):
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 = graph.get_boundary()
42    graph = graph.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    return graph
56
57def trace_faces(graph, rot_sys):
58    """
59    A helper function for finding the genus of a graph.
60    Given a graph and a combinatorial embedding (rot_sys),
61    this function will compute the faces (returned as a list
62    of lists of edges (tuples) of the particular embedding.
63
64    Note -- rot_sys is an ordered list based on the hash order
65    of the vertices of graph.  To avoid confusion, it might be
66    best to set the rot_sys based on a 'nice_copy' of the graph.
67
68    INPUT:
69        graph -- a graph to compute the faces of
70        rot_sys -- the combinatorial embedding of graph (an
71                   ordered list by vertex hash order)
72
73    EXAMPLES:
74        sage: from sage.graphs import graph_genus1
75        sage: J = Graph({'alpha':['beta', 'epsilon'], 'gamma':['beta', 'epsilon']})
76        sage: J.set_boundary(['beta','alpha'])
77        sage: K = graph_genus1.nice_copy(J)
78        sage: rot = []
79        sage: for node in K.vertices():
80        ...     rot.append(K[node])
81        sage: rot
82        [[1, 2], [0, 3], [0, 3], [1, 2]]
83        sage: graph_genus1.trace_faces(K,rot)
84        [[(0, 1), (1, 3), (3, 2), (2, 0)], [(1, 0), (0, 2), (2, 3), (3, 1)]]
85    """
86    from sage.sets.set import Set
87
88    # Make dict of node labels embedding
89    comb_emb = {}
90    labels = graph.vertices()
91    for i in range(len(rot_sys)):
92        comb_emb[labels[i]] = rot_sys[i]
93
94    # Establish set of possible edges
95    edgeset = Set([])
96    for edge in graph.edges():
97        edgeset = edgeset.union(Set([(edge[0],edge[1]),(edge[1],edge[0])]))
98
99    # Storage for face paths
100    faces = []
101    path = []
102    for edge in edgeset:
103        path.append(edge)
104        edgeset -= Set([edge])
105        break  # (Only one iteration)
106
107    # Trace faces
108    while (len(edgeset) > 0):
109        neighbors = comb_emb[path[-1][-1]]
110        next_node = neighbors[(neighbors.index(path[-1][-2])+1)%(len(neighbors))]
111        tup = (path[-1][-1],next_node)
112        if tup == path[0]:
113            faces.append(path)
114            path = []
115            for edge in edgeset:
116                path.append(edge)
117                edgeset -= Set([edge])
118                break  # (Only one iteration)
119        else:
120            path.append(tup)
121            edgeset -= Set([tup])
122
123    if (len(path) != 0): faces.append(path)
124    return faces
125
126def all_embeddings(graph):
127    """
128    Returns a list of tuples, one for each possible embedding.
129    The tuples have the minimal genus of the particular
130    embedding as the first entry.  The second entry is a list
131    of lists of edges (tuples) that represent the embedding
132    via face traces.  Each inner list represents one face in
133    the embedding.
134
135    Note -- returns list of tuples:
136        (genus,[list of lists representing face traces])
137
138    INPUT:
139        graph -- the graph to find all possible embeddings of
140
141    EXAMPLES:
142        sage: from sage.graphs import graph_genus1
143        sage: J = Graph({'alpha':['beta', 'epsilon'], 'gamma':['beta', 'epsilon']})
144        sage: J.set_boundary(['beta','alpha'])
145        sage: graph_genus1.all_embeddings(J)
146        [(0, [[(0, 1), (1, 3), (3, 2), (2, 0)], [(1, 0), (0, 2), (2, 3), (3, 1)]])]
147        sage: K23 = graphs.CompleteBipartiteGraph(2,3)
148        sage: graph_genus1.all_embeddings(K23)
149        [(1,
150          [[(1, 2),
151            (2, 0),
152            (0, 3),
153            (3, 1),
154            (1, 4),
155            (4, 0),
156            (0, 2),
157            (2, 1),
158            (1, 3),
159            (3, 0),
160            (0, 4),
161            (4, 1)]]),
162         (0,
163          [[(1, 2), (2, 0), (0, 4), (4, 1)],
164           [(1, 3), (3, 0), (0, 2), (2, 1)],
165           [(0, 3), (3, 1), (1, 4), (4, 0)]]),
166         (0,
167          [[(1, 2), (2, 0), (0, 3), (3, 1)],
168           [(1, 3), (3, 0), (0, 4), (4, 1)],
169           [(1, 4), (4, 0), (0, 2), (2, 1)]]),
170         (1,
171          [[(1, 2),
172            (2, 0),
173            (0, 4),
174            (4, 1),
175            (1, 3),
176            (3, 0),
177            (0, 2),
178            (2, 1),
179            (1, 4),
180            (4, 0),
181            (0, 3),
182            (3, 1)]])]
183    """
184    from sage.combinat.all import CyclicPermutationsOfPartition
185
186    graph = nice_copy(graph)
187
188    verts = len(graph.vertices())
189    edges = len(graph.edges())
190
191    # Construct a list of all rotation systems for graph
192    part = []
193    for node in graph.vertices():
194        part.append(graph.neighbors(node))
195    all_perms = []
196    for p in CyclicPermutationsOfPartition(part):
197        all_perms.append(p)
198
199    embeddings = []
200    for p in all_perms:
201        t = trace_faces(graph, p)
202        faces = len(t)
203
204        g = (2-verts+edges-faces)/2
205        embeddings.append((g,t))
206
207    return embeddings
208
209def planar_embeddings(graph):
210    """
211    Returns a list of lists of lists of edges (tuples), where
212    each inner inner list of edges represents the tracing of
213    one face in the embedding, and each inner list of lists
214    represents one planar embedding.  The list is an
215    exhaustive list of all embeddings of graph with genus=0.
216    Returns an empty list if there are no planar embeddings
217    of the graph.
218
219    INPUT:
220        graph -- the graph to find all planar embeddings of
221
222    EXAMPLES:
223        sage: from sage.graphs import graph_genus1
224        sage: K5 = graphs.CompleteGraph(5)
225        sage: graph_genus1.planar_embeddings(K5)
226        []
227
228        sage: K23 = graphs.CompleteBipartiteGraph(2,3)
229        sage: graph_genus1.planar_embeddings(K23)
230        [[[(1, 2), (2, 0), (0, 4), (4, 1)],
231          [(1, 3), (3, 0), (0, 2), (2, 1)],
232          [(0, 3), (3, 1), (1, 4), (4, 0)]],
233         [[(1, 2), (2, 0), (0, 3), (3, 1)],
234          [(1, 3), (3, 0), (0, 4), (4, 1)],
235          [(1, 4), (4, 0), (0, 2), (2, 1)]]]
236        sage: graph_genus1.all_embeddings(K23)
237        [(1,
238          [[(1, 2),
239            (2, 0),
240            (0, 3),
241            (3, 1),
242            (1, 4),
243            (4, 0),
244            (0, 2),
245            (2, 1),
246            (1, 3),
247            (3, 0),
248            (0, 4),
249            (4, 1)]]),
250         (0,
251          [[(1, 2), (2, 0), (0, 4), (4, 1)],
252           [(1, 3), (3, 0), (0, 2), (2, 1)],
253           [(0, 3), (3, 1), (1, 4), (4, 0)]]),
254         (0,
255          [[(1, 2), (2, 0), (0, 3), (3, 1)],
256           [(1, 3), (3, 0), (0, 4), (4, 1)],
257           [(1, 4), (4, 0), (0, 2), (2, 1)]]),
258         (1,
259          [[(1, 2),
260            (2, 0),
261            (0, 4),
262            (4, 1),
263            (1, 3),
264            (3, 0),
265            (0, 2),
266            (2, 1),
267            (1, 4),
268            (4, 0),
269            (0, 3),
270            (3, 1)]])]
271
272        sage: g = graphs.CycleGraph(9)
273        sage: graph_genus1.planar_embeddings(g)
274        [[[(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 0), (0, 1)],
275          [(5, 4), (4, 3), (3, 2), (2, 1), (1, 0), (0, 8), (8, 7), (7, 6), (6, 5)]]]
276        sage: graph_genus1.all_embeddings(g)
277        [(0,
278          [[(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 0), (0, 1)],
279           [(5, 4), (4, 3), (3, 2), (2, 1), (1, 0), (0, 8), (8, 7), (7, 6), (6, 5)]])]
280    """
281    from sage.combinat.all import CyclicPermutationsOfPartition
282
283    graph = nice_copy(graph)
284
285    verts = len(graph.vertices())
286    edges = len(graph.edges())
287
288    # Construct a list of all rotation systems for graph
289    part = []
290    for node in graph.vertices():
291        part.append(graph.neighbors(node))
292    all_perms = []
293    for p in CyclicPermutationsOfPartition(part):
294        all_perms.append(p)
295
296    # planar embeddings
297    plan_emb = []
298
299    for p in all_perms:
300        t = trace_faces(graph, p)
301        faces = len(t)
302
303        # return planar embeddings
304        if ((2-verts+edges-faces)/2 == 0):
305            plan_emb.append(t)
306
307    return plan_emb
Note: See TracBrowser for help on using the repository browser.