# source:sage/graphs/graph_genus1.py@8734:d84d24c8d5bb

Revision 8734:d84d24c8d5bb, 4.1 KB checked in by Emily Kirkman, 5 years ago (diff)

genus improvements and bm planarity

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(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
64def 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
Note: See TracBrowser for help on using the repository browser.