Source code for surface_dynamics.topology.fat_graph

r"""
Fat graph.

This module is experimental.
"""

from __future__ import absolute_import, print_function
from six.moves import range, map, zip

from sage.misc.cachefunc import cached_function
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ

from array import array
from collections import deque
from surface_dynamics.misc.permutation import *

###########################
# Miscellaneous functions #
###########################

[docs]def num_and_weighted_num(it): from sage.rings.integer_ring import ZZ from sage.rings.rational_field import QQ s = QQ.zero() n = ZZ.zero() for _,aut in it: n += ZZ.one() if aut is None: s += QQ.one() else: s += QQ((1,aut.group_cardinality())) return n,s
[docs]def list_extrems(l, n): if not n: raise ValueError vdmin = vdmax = l[0] for i in range(1, n): if l[i] > vdmax: vdmax = l[i] if l[i] < vdmin: vdmin = l[i] return (vdmin, vdmax)
##################### # Fat graph # ##################### # # For Abelian strata we should use constellations (= bipartite stuff)
[docs]class FatGraph(object): r""" EXAMPLES: The once punctured torus:: sage: from surface_dynamics import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: FatGraph(vp, ep, fp) FatGraph('(0,2,1,3)', '(0,1)(2,3)', '(0,2,1,3)') Actually it is enough to specify 2 of the 3 permutations:: sage: vp = '(0,3,1)(4)(2,5,6,7)' sage: ep = '(0,1)(2,3)(4,5)(6,7)' sage: fp = '(0,3,7,5,4,2)(1)(6)' sage: F0 = FatGraph(vp=vp, ep=ep, fp=fp) sage: F1 = FatGraph(ep=ep, fp=fp) sage: F2 = FatGraph(vp=vp, fp=fp) sage: F3 = FatGraph(vp=vp, ep=ep) sage: F0 == F1 and F0 == F2 and F0 == F3 True """ __slots__ = ['_n', # number of darts (non-negative integer) '_vp', # vertex permutation (array of length _n) '_ep', # edge permutation (array of length _n) '_fp', # face permutation (array of length _n) # labels # TODO: add _el and care about folded edges!! '_vl', # vertex labels (array of length _n) '_fl', # face labels (array of length _n) # numbers # TODO: add _ne '_nv', # number of vertices (non-negative integer) '_nf', # number of faces (non-negative integer) # degrees # TODO: add _ed '_vd', # vertex degrees (array of length _nv) '_fd'] # face degrees (array of length _nf) def __init__(self, vp=None, ep=None, fp=None, max_num_dart=None, check=True): vp, ep, fp = constellation_init(vp, ep, fp) self._vp = vp self._ep = ep self._fp = fp if len(vp) != len(ep) or len(vp) != len(fp): raise ValueError("invalid permutations") self._n = len(vp) # number of darts self._nf = 0 # number of faces self._vl, self._vd = perm_dense_cycles(vp, self._n) self._nv = len(self._vd) # number of vertices self._fl, self._fd = perm_dense_cycles(fp, self._n) self._nf = len(self._fd) # number of faces if max_num_dart is not None: if max_num_dart < self._n: raise ValueError self._realloc(max_num_dart) if check: self._check() def __hash__(self): raise TypeError("FatGraph not hashable") def _realloc(self, max_num_dart): if max_num_dart < self._n: return self._vp.extend([-1] * (max_num_dart - self._n)) self._ep.extend([-1] * (max_num_dart - self._n)) self._fp.extend([-1] * (max_num_dart - self._n)) self._vl.extend([-1] * (max_num_dart - self._n)) self._fl.extend([-1] * (max_num_dart - self._n)) self._vd.extend([-1] * (max_num_dart - self._nv)) self._fd.extend([-1] * (max_num_dart - self._nf))
[docs] def copy(self): """ EXAMPLES:: sage: from surface_dynamics import FatGraph sage: F = FatGraph.from_unicellular_word([0,1,0,2,3,4,1,4,3,2]) sage: G = F.copy() sage: G._check() """ F = FatGraph.__new__(FatGraph) F._vp = self._vp[:] F._ep = self._ep[:] F._fp = self._fp[:] F._n = self._n F._nf = self._nf F._nv = self._nv F._vl = self._vl[:] F._vd = self._vd[:] F._fl = self._fl[:] F._fd = self._fd[:] return F
[docs] @staticmethod def from_unicellular_word(X): r""" Build a fat graph from a word on the letters {0, ..., n-1} where each letter appears exactly twice. EXAMPLES:: sage: from surface_dynamics import FatGraph sage: FatGraph.from_unicellular_word([0,1,0,2,3,4,1,4,3,2]) FatGraph('(0,3)(1,2,6,7)(4,9)(5,8)', '(0,2)(1,6)(3,9)(4,8)(5,7)', '(0,1,2,3,4,5,6,7,8,9)') sage: FatGraph.from_unicellular_word([0,1,2,0,3,2,4,1,3,4]) FatGraph('(0,6,2,7,9,4)(1,3,5,8)', '(0,3)(1,7)(2,5)(4,8)(6,9)', '(0,1,2,3,4,5,6,7,8,9)') """ n = len(X) m = n // 2 ep = [None] * n vp = [None] * n fp = list(range(1,n)) + [0] symb_to_pos = [None] * m for i,k in enumerate(X): j = symb_to_pos[k] if j is not None: ep[i] = j ep[j] = i vp[(j + 1) % n] = i vp[(i + 1) % n] = j else: symb_to_pos[k] = i return FatGraph(vp, ep, fp)
[docs] @staticmethod def from_string(s): r""" Build a fat graph from a serialized string. See also :meth:`to_string`. EXAMPLES:: sage: from surface_dynamics import FatGraph sage: s = '20_i23017546b98jchedfag_2301547698badcfehgji_12346758ab9igdhfejc0' sage: F = FatGraph.from_string(s) sage: F.to_string() == s True sage: FatGraph.from_string('0___') FatGraph('()', '()', '()') """ if not isinstance(s, str) or s.count('_') != 3: raise ValueError("invalid input") n, vp, ep, fp = s.split('_') n = int(n) vp = perm_from_base64_str(vp, n) ep = perm_from_base64_str(ep, n) fp = perm_from_base64_str(fp, n) return FatGraph(vp, ep, fp)
[docs] def to_string(self): r""" Serialization to string. EXAMPLES:: sage: from surface_dynamics import FatGraph sage: FatGraph.from_unicellular_word([0,1,0,2,3,4,1,4,3,2]).to_string() '10_3260987154_2609871543_1234567890' sage: FatGraph('', '', '').to_string() '0___' """ n = self._n return str(n) + "_" + \ perm_base64_str(self._vp, n) + "_" + \ perm_base64_str(self._ep, n) + "_" + \ perm_base64_str(self._fp, n)
def _check(self, error=RuntimeError): vp = self._vp vl = self._vl vd = self._vd ep = self._ep fp = self._fp fl = self._fl fd = self._fd n = self._n nf = self._nf nv = self._nv m = sum(vp[i] != -1 for i in range(n)) if not perm_check(vp, n): raise ValueError("invalid vertex permutation: %s" % vp) if not perm_check(ep, n): raise ValueError("invalid edge permutation: %s" % ep) if not perm_check(fp, n): raise ValueError("invalid face permutation: %s" % fp) if perm_num_cycles(vp, n) != self._nv: raise error("wrong number of vertices") if perm_num_cycles(fp, n) != self._nf: raise error("wrong number of faces") if len(vl) < n or len(fl) < n or len(vd) < nv or len(fd) < nf: raise error("inconsistent lengths") if any(x < 0 or x > n for x in vd[:nv]) or sum(vd[:nv]) != m: raise error("invalid vertex degrees") if any(x < 0 or x > n for x in fd[:nf]) or sum(fd[:nf]) != m: raise error("invalid face degrees") ffd = [0] * nf vvd = [0] * nv for i in range(n): if vp[i] == -1: if ep[i] != -1 or fp[i] != -1: raise ValueError("inconsistent dart activity for i={}".format(i)) continue elif ep[i] == -1 or fp[i] == -1: raise ValueError("inconsistent dart activity for i={}".format(i)) if fp[ep[vp[i]]] != i: raise error("fp[ep[vp[%d]]] = %d" % (i, fp[ep[vp[i]]])) if fl[i] < 0 or fl[i] >= nf: raise error("face label out of range: fl[%d] = %d" % (i, fl[i])) if vl[i] < 0 or vl[i] >= nv: raise error("vertex label out of range: vl[%d] = %d" % (i, vl[i])) if fl[fp[i]] != fl[i]: raise error("fl[fp[%d]] = %d while fl[%d] = %d" %(i, fl[fp[i]], i, fl[i])) if vl[vp[i]] != vl[i]: raise error("vl[vp[%d]] = vl[%d] = %d while vl[%d] = %d" %(i, vp[i], vl[vp[i]], i, vl[i])) ffd[fl[i]] += 1 vvd[vl[i]] += 1 if vvd != vd[:nv]: raise error("inconsistent face labels/degrees, got %s instead of vd = %s" % (vvd, vd[:nv])) if ffd != fd[:nf]: raise error("inconsistent vertex labels/degrees, got %s instead of fd = %s" %(ffd, fd[:nf]))
[docs] def is_face_bipartite(self): r""" Test whether the faces admit a bi-coloring. EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import * sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: F = FatGraph(vp, ep, fp, 6) sage: F.is_face_bipartite() False sage: F.split_face(0,1) sage: F.is_face_bipartite() True sage: vp = '(0,5,1,2,3,4)' sage: ep = '(0,2)(1,3)(4,5)' sage: fp = '(0,1,2,4)(3,5)' sage: FatGraph(vp, ep, fp).is_face_bipartite() False sage: from surface_dynamics.topology.fat_graph_exhaustive_generation import FatGraphs_g_nf_nv sage: F = FatGraphs_g_nf_nv(1, 3, 3, vertex_min_degree=3) sage: F.cardinality_and_weighted_cardinality(filter=lambda x,a: x.is_face_bipartite()) (3, 5/3) """ # trivial cases if self._nf == 0: return True elif self._nf == 1: return False n = self._n ep = self._ep fp = self._fp fl = self._fl nf = self._nf colors = [-1] * nf edge_seen = [False] * n to_test = perm_orbit(fp, 0) colors[self._fl[0]] = 1 while to_test: e1 = to_test.pop() if edge_seen[e1]: continue e2 = ep[e1] f1 = fl[e1] f2 = fl[e2] if colors[f1] == -1: raise RuntimeError elif colors[f2] == -1: # discover a new face colors[f2] = 1 - colors[f1] to_test.extend(perm_orbit(fp, e2)) elif colors[f1] == colors[f2]: # contradiction in colors return False edge_seen[e1] = edge_seen[e2] = True return True
def __copy__(self): r""" EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: cm = FatGraph(vp, ep, fp) sage: cm2 = cm.__copy__() sage: cm2._check() """ cm = FatGraph.__new__(FatGraph) cm._vp = self._vp[:] cm._ep = self._ep[:] cm._fp = self._fp[:] cm._n = self._n cm._nf = self._nf cm._nv = self._nv cm._vl = self._vl[:] cm._fl = self._fl[:] cm._vd = self._vd[:] cm._fd = self._fd[:] return cm def __repr__(self): n = self._n fd = self._fd[:self._nf] vd = self._vd[:self._nv] fd.sort(reverse=True) vd.sort(reverse=True) return "FatGraph('%s', '%s', '%s')" % (perm_cycle_string(self._vp, True, n), perm_cycle_string(self._ep, True, n), perm_cycle_string(self._fp, True, n)) def __eq__(self, other): r""" TESTS:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: cm1 = FatGraph(vp, ep, fp) sage: cm2 = FatGraph(vp, ep, fp, 100) sage: cm1 == cm2 True """ if type(self) != type(other): raise TypeError if self._n != other._n or self._nf != other._nf or self._nv != other._nv: return False for i in range(self._n): if self._vp[i] != other._vp[i] or \ self._ep[i] != other._ep[i] or \ self._fp[i] != other._fp[i]: return False # here we ignore the vertex and face labels... return True def __ne__(self, other): return not self == other
[docs] def vertex_permutation(self, copy=True): if copy: return self._vp[:self._n] else: return self._vp
[docs] def edge_permutation(self, copy=True): if copy: return self._ep[:self._n] else: return self._ep
[docs] def face_permutation(self, copy=True): if copy: return self._fp[:self._n] else: return self._fp
[docs] def vertex_profile(self): return perm_cycle_type(self._vp, self._n)
[docs] def edge_profile(self): return perm_cycle_type(self._ep, self._n)
[docs] def face_profile(self): return perm_cycle_type(self._fp, self._n)
[docs] def profile(self): return (self.vertex_profile(), self.edge_profile(), self.face_profile())
[docs] def num_darts(self): return self._n
[docs] def num_folded_edges(self): return sum(self._ep[i] == 1 for i in range(self._n))
[docs] def num_faces(self): return self._nf
[docs] def num_vertices(self): return self._nv
[docs] def vertices(self): return perm_cycles(self._vp, True, n)
[docs] def vertex_degrees(self): return self._vd[:self._nv]
[docs] def vertex_degree_extrems(self): return list_extrems(self._vd, self._nv)
[docs] def vertex_degree_min(self): return list_extrems(self._vd, self._nv)[0]
[docs] def vertex_degree_max(self): return list_extrems(self._vd, self._nv)[1]
[docs] def face_degree_extrems(self): return list_extrems(self._fd, self._nf)
def face_degree_min(self): return list_extrems(self._fd, self._nf)[0]
[docs] def face_degree_max(self): return list_extrems(Self._fd, self._nf)[1]
[docs] def face_degree_min(self): return s
[docs] def edges(self): return perm_cycles(self._ep, True, n)
[docs] def num_edges(self): return self._n // 2
[docs] def faces(self): return self._nf
[docs] def face_degrees(self): return self._fd[:self._nf]
[docs] def euler_characteristic(self): return self._nf - self._n//2 + self._nv
[docs] def dual(self): r""" Return the dual fat graph. EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: F = FatGraph(vp=None,ep='(0,1)',fp='(0)(1)') sage: F.dual() sage: F FatGraph('(0)(1)', '(0,1)', '(0,1)') sage: F._check() sage: s = '20_i23017546b98jchedfag_2301547698badcfehgji_12346758ab9igdhfejc0' sage: F = FatGraph.from_string(s) sage: F.dual() sage: F._check() sage: F.dual() sage: F._check() sage: F == FatGraph.from_string(s) True """ # TODO: invert in place !!!! self._vp, self._fp = perm_invert(self._fp, self._n), perm_invert(self._vp, self._n) self._nv, self._nf = self._nf, self._nv self._vl, self._fl = self._fl, self._vl self._vd, self._fd = self._fd, self._vd
[docs] def kontsevich_volume_rational_function(self, R=None): r""" This is not under an appropriate form... """ raise NotImplementedError print('This is not quite the form under which we would like it... it should remains factorized') from sage.rings.rational_field import QQ from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing nf = self._nf fl = self._fl n = self._n ep = self._ep if R is None: R = PolynomialRing(QQ, 'b', nf) gens = R.gens() res = R.one() for i in range(self._n): j = ep[i] if j < i: continue res *= 1 / self.automorphism_group().group_cardinality() / (gens[fl[i]] + gens[fl[j]]) return res
############################## # Augmentation and reduction # ############################## def _check_alloc(self, n, nv, nf): if len(self._vp) < n or \ len(self._ep) < n or \ len(self._fp) < n or \ len(self._vl) < n or \ len(self._fl) < n or \ len(self._fd) < nf or \ len(self._vd) < nv: raise TypeError("reallocation needed")
[docs] def split_face(self, i, j): r""" Insert an edge between the darts ``i`` and ``j`` to split the face. One of the face will contains i, fp[i], ..., (the x-face) and the other one will contain j, fp[j], ... In the special case i=j, a monogon (= face with only one edge) is created. The converse operation is implemented in :meth:`remove_edge`. EXAMPLES: The once punctured torus:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: eps = '(0,1)(2,3)(4,5)' sage: vp20 = '(0,4,2,5,1,3)' sage: fp20 = '(0,5)(1,3,4,2)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_face(2,0) sage: cm == FatGraph(vp20, eps, fp20) True sage: vp10 = '(0,4,2,1,5,3)' sage: fp10 = '(0,2,5)(1,3,4)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_face(1,0) sage: cm == FatGraph(vp10, eps, fp10) True sage: vp30 = '(0,4,2,1,3,5)' sage: fp30 = '(0,2,1,5)(3,4)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_face(3,0) sage: cm == FatGraph(vp30, eps, fp30) True sage: vp00 = '(0,5,4,2,1,3)' sage: fp00 = '(0,2,1,3,4)(5)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_face(0,0) sage: cm == FatGraph(vp00, eps, fp00) True sage: vp22 = '(0,2,5,4,1,3)' sage: fp22 = '(0,4,2,1,3)(5)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_face(2,2) sage: cm == FatGraph(vp22, eps, fp22) True A genus 2 surface:: sage: vp = '(0,3,6,8)(1,10,9,12,5)(2,7,4,11)(13)' sage: ep = '(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)' sage: fp = '(0,5,7,3,11,1,8,10,4,12,13,9,6,2)' sage: cm = FatGraph(vp, ep, fp, 21) sage: cm.split_face(0,1); cm._check() sage: cm.split_face(4,13); cm._check() sage: cm.split_face(5,14); cm._check() sage: cm.remove_edge(18); cm._check() sage: cm.remove_edge(16); cm._check() sage: cm.remove_edge(14); cm._check() sage: cm == FatGraph(vp, ep, fp, 21) True """ vp = self._vp vl = self._vl vd = self._vd ep = self._ep fp = self._fp fl = self._fl fd = self._fd n = self._n nf = self._nf nv = self._nv i = int(i) j = int(j) if i < 0 or i >= self._n or j < 0 or j >= n or fl[i] != fl[j]: raise ValueError("invalid darts i=%d and j=%d for face splitting" %(i, j)) self._check_alloc(n + 2, nv, nf + 1) x = self._n y = self._n + 1 ii = ep[vp[i]] # = fp^-1(i) jj = ep[vp[j]] # = fp^-1(j) ep[x] = y ep[y] = x self._n += 2 self._nf += 1 if i == j: # add a monogon # fp (i A) -> (i A x)(y) # vp (... i ...) -> (... i y x ...) fp[ii] = x fp[x] = i fp[y] = y vp[x] = vp[i] vp[y] = x vp[i] = y vl[x] = vl[y] = vl[i] fl[x] = fl[i] fl[y] = nf fd[fl[i]] += 1 fd[nf] = 1 vd[vl[i]] += 2 else: # general case # update permutations: # fp (i A j B) -> (i A x) (j B y) # ep -> (x y) # vp (... i ...) (... j ...) -> (... i y ...) (... j x ...) fp[jj] = x fp[x] = i fp[ii] = y fp[y] = j vp[y] = vp[i] vp[i] = y vp[x] = vp[j] vp[j] = x # update labels and degrees vl[x] = vl[j] vl[y] = vl[i] fl[x] = fl[i] fl[y] = fl[j] dfy = 0 # degree of the y-face while fl[y] != nf: fl[y] = nf y = fp[y] dfy += 1 dfx = fd[fl[x]] + 2 - dfy fd[fl[x]] = dfx fd[fl[y]] = dfy vd[vl[x]] += 1 vd[vl[y]] += 1
[docs] def remove_edge(self, i): r""" Remove an edge. If the edge has the same face on both sides, then the genus drops by 1. Inverse operation of :meth:`split_face` or :meth:`trisect_face`. EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: cm = FatGraph(vp, ep, fp) sage: eps = '(0,1)(2,3)(4,5)' sage: vp20 = '(0,5,4,2,1,3)' sage: fp20 = '(0,2,1,3,4)(5)' sage: cm2 = FatGraph(vp20, eps, fp20, 6) sage: cm2.remove_edge(4) sage: cm2 == cm True sage: cm2 = FatGraph(vp20, eps, fp20, 6) sage: cm2.remove_edge(5) sage: cm2 == cm True sage: vp10 = '(0,4,2,5,1,3)' sage: fp10 = '(0,5)(1,3,4,2)' sage: cm2 = FatGraph(vp10, eps, fp10) sage: cm2.remove_edge(4) sage: cm2 == cm True sage: cm2 = FatGraph(vp10, eps, fp10) sage: cm2.remove_edge(5) sage: cm2 == cm True sage: vp30 = '(0,4,2,1,5,3)' sage: fp30 = '(0,2,5)(1,3,4)' sage: cm2 = FatGraph(vp30, eps, fp30) sage: cm2.remove_edge(4) sage: cm2 == cm True sage: cm2 = FatGraph(vp30, eps, fp30) sage: cm2.remove_edge(5) sage: cm2 == cm True sage: vp00 = '(0,5,4,2,1,3)' sage: fp00 = '(0,2,1,3,4)(5)' sage: cm2 = FatGraph(vp00, eps, fp00) sage: cm2.remove_edge(4) sage: cm2 == cm True sage: vp22 = '(0,2,5,4,1,3)' sage: fp22 = '(0,4,2,1,3)(5)' sage: cm2 = FatGraph(vp00, eps, fp00) sage: cm2.remove_edge(4) sage: cm2 == cm True """ vp = self._vp ep = self._ep fp = self._fp vl = self._vl fl = self._fl vd = self._vd fd = self._fd n = self._n nf = self._nf nv = self._nv i = int(i) if i < 0 or i >= self._n: raise ValueError("dart index out of range") j = ep[i] fi = fl[i] fj = fl[j] if fi == fj: raise ValueError("i=%d and j=%d on the same face" %(i,j)) fmin = min(fi, fj) if i < n - 2 or j < n - 2 or max(fi, fj) != nf-1: raise NotImplementedError ii = ep[vp[i]] jj = ep[vp[j]] if fd[fl[i]] == 1: # monogon assert vp[i] == j fp[jj] = fp[j] vp[fp[j]] = vp[j] elif fd[fl[j]] == 1: # monogon assert vp[j] == i fp[ii] = fp[i] vp[fp[i]] = vp[i] else: # none of them are monogons fp[ii] = fp[j] fp[jj] = fp[i] vp[fp[j]] = vp[i] vp[fp[i]] = vp[j] # update vertex and face degrees vd[vl[i]] -= 1 vd[vl[j]] -= 1 d = fd[fl[i]] + fd[fl[j]] - 2 fd[fmin] = d # update face labels k = fp[i] while fl[k] != fmin: fl[k] = fmin k = fp[k] k = fp[j] while fl[k] != fmin: fl[k] = fmin k = fp[k] self._n -= 2 self._nf -= 1
[docs] def split_vertex(self, i, j): r""" Insert a new edge to split the vertex located at the darts i and j. This operation keeps the genus constant. The inverse operation is implemented in :meth:`contract_edge`. EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: eps = '(0,1)(2,3)(4,5)' sage: vp02 = '(0,4,1,3)(2,5)' sage: fp02 = '(0,4,2,1,3,5)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_vertex(0,2) sage: cm == FatGraph(vp02, eps, fp02) True sage: vp01 = '(0,4,3)(1,5,2)' sage: fp01 = '(0,2,4,1,3,5)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_vertex(0,1) sage: cm == FatGraph(vp01, eps, fp01) True sage: vp03 = '(0,4)(1,3,5,2)' sage: fp03 = '(0,2,1,4,3,5)' sage: cm = FatGraph(vp, ep, fp, 6) sage: cm.split_vertex(0,3) sage: cm == FatGraph(vp03, eps, fp03) True """ vp = self._vp ep = self._ep fp = self._fp vl = self._vl fl = self._fl n = self._n nf = self._nf nv = self._nv vd = self._vd fd = self._fd i = int(i) j = int(j) if i < 0 or i >= self._n or j < 0 or j >= self._n or vl[i] != vl[j]: raise ValueError("invalid darts i=%d and j=%d for vertex splitting" %(i, j)) self._check_alloc(n + 2, nv + 1, nf) x = self._n y = self._n + 1 ii = vp[i] jj = vp[j] ep[x] = y ep[y] = x self._n += 2 self._nv += 1 if i == j: # introduce a vertex of degree 1 vp[x] = ii vp[i] = x vp[y] = y fp[y] = i fp[x] = y fp[ep[ii]] = x fl[x] = fl[y] = fl[i] vl[x] = vl[i] vl[y] = nv vd[vl[x]] += 1 vd[vl[y]] = 1 fd[fl[x]] += 2 else: # general case # update permutations # fp (... i ...) (... j ...) -> (... y i ...) (... x j ...) # ep -> (x y) # vp (A i B j) -> (A i x) (B j y) vp[x] = jj vp[i] = x vp[y] = ii vp[j] = y fp[ep[jj]] = x fp[x] = j fp[ep[ii]] = y fp[y] = i # update labels and degrees fl[x] = fl[j] fl[y] = fl[i] vl[x] = vl[i] vl[y] = vl[j] dvy = 0 while vl[y] != nv: vl[y] = nv y = vp[y] dvy += 1 dvx = vd[vl[x]] + 2 - dvy vd[vl[x]] = dvx vd[vl[y]] = dvy fd[fl[x]] += 1 fd[fl[y]] += 1
[docs] def contract_edge(self, i): r""" Contract an edge between two distinct zeros. Inverse operation of :meth:`split_vertex` except that here we allow vertices of degree one. EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: eps = '(0,1)(2,3)(4,5)' sage: vp02 = '(0,4,1,3)(2,5)' sage: fp02 = '(0,4,2,1,3,5)' sage: cm = FatGraph(vp02, eps, fp02) sage: cm.contract_edge(4) sage: cm == FatGraph(vp, ep, fp) True sage: cm = FatGraph(vp02, eps, fp02) sage: cm.contract_edge(5) sage: cm == FatGraph(vp, ep, fp) True sage: vp01 = '(0,4,3)(1,5,2)' sage: fp01 = '(0,2,4,1,3,5)' sage: cm = FatGraph(vp01, eps, fp01) sage: cm.contract_edge(4) sage: cm == FatGraph(vp, ep, fp) True sage: cm = FatGraph(vp01, eps, fp01) sage: cm.contract_edge(5) sage: cm == FatGraph(vp, ep, fp) True sage: vp03 = '(0,4)(1,3,5,2)' sage: fp03 = '(0,2,1,4,3,5)' sage: cm = FatGraph(vp03, eps, fp03) sage: cm.contract_edge(4) sage: cm == FatGraph(vp, ep, fp) True sage: cm = FatGraph(vp03, eps, fp03) sage: cm.contract_edge(5) sage: cm == FatGraph(vp, ep, fp) True Degree 1 vertices:: sage: cm = FatGraph('(0,2)(1)(3)', '(0,1)(2,3)', '(0,1,2,3)') sage: cm.contract_edge(2) sage: cm FatGraph('(0)(1)', '(0,1)', '(0,1)') sage: cm2 = FatGraph('(0,2)(1)(3)', '(0,1)(2,3)', '(0,1,2,3)') sage: cm2.contract_edge(3) sage: cm == cm2 True """ vp = self._vp ep = self._ep fp = self._fp vl = self._vl fl = self._fl vd = self._vd fd = self._fd n = self._n nf = self._nf nv = self._nv i = int(i) if i < 0 or i >= self._n: raise ValueError("dart index out of range") j = ep[i] if vl[i] == vl[j]: raise ValueError("i=%d and j=%d on the same vertex" %(i,j)) vi = vl[i] vj = vl[j] vmin = min(vi, vj) if i < n - 2 or j < n - 2 or max(vi, vj) != nv-1: raise NotImplementedError ii = ep[vp[i]] jj = ep[vp[j]] if vd[vl[i]] == 1: # vertex of degree one assert fp[j] == i vp[fp[i]] = vp[j] fp[jj] = fp[i] elif vd[vl[j]] == 1: # vertex of degree one assert fp[i] == j vp[fp[j]] = vp[i] fp[ii] = fp[j] else: vp[fp[i]] = vp[i] vp[fp[j]] = vp[j] fp[ii] = fp[i] fp[jj] = fp[j] # update vertex and face degree fd[fl[i]] -= 1 fd[fl[j]] -= 1 d = vd[vl[i]] + vd[vl[j]] - 2 vd[vmin] = d # update vertex labels k = vp[i] while vl[k] != vmin: vl[k] = vmin k = vp[k] k = vp[j] while vl[k] != vmin: vl[k] = vmin k = vp[k] self._n -= 2 self._nv -= 1
[docs] def trisect_face(self, i, j, k): r""" Insert a bridge INPUT: - ``i``, ``j``, ``k`` - dart in the same face in counter-clockwise order EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,2,1,3)' sage: ep = '(0,1)(2,3)' sage: fp = '(0,2,1,3)' sage: cm = FatGraph(vp, ep, fp, 8) sage: vp021 = '(0,7,2,6,5,1,4,3)' sage: ep021 = '(0,1)(2,3)(4,5)(6,7)' sage: fp021 = '(0,5,1,3,7,2,4,6)' sage: cm021 = FatGraph(vp021, ep021, fp021) sage: cm.trisect_face(0, 2, 1) sage: cm == cm021 True sage: cm = FatGraph(vp, ep, fp, 10) sage: cm.trisect_face(0, 0, 3) sage: cm = FatGraph(vp, ep, fp, 10) sage: cm.trisect_face(0, 3, 3) sage: cm = FatGraph(vp, ep, fp, 10) sage: cm.trisect_face(0, 3, 0) sage: cm = FatGraph(vp, ep, fp, 10) sage: cm.trisect_face(0, 0, 0) """ vp = self._vp ep = self._ep fp = self._fp vl = self._vl fl = self._fl vd = self._vd fd = self._fd n = self._n nf = self._nf nv = self._nv i = int(i) j = int(j) k = int(k) if i < 0 or i >= n or j < 0 or j >= n or k < 0 or k >= n: raise ValueError("dart index out of range") if fl[i] != fl[j] or fl[i] != fl[k]: raise ValueError("darts in distinct faces") self._check_alloc(n + 4, nv, nf) self._n += 4 ii = ep[vp[i]] # = fp^-1(i) at the end of B jj = ep[vp[j]] # = fp^-1(j) at the end of A kk = ep[vp[k]] # = fp^-1(k) at the end of C x = n y = n + 1 xx = n + 2 yy = n + 3 ep[x] = y ep[y] = x ep[xx] = yy ep[yy] = xx fl[x] = fl[y] = fl[xx] = fl[yy] = fl[i] vl[x] = vl[k] vl[xx] = vl[y] = vl[j] vl[yy] = vl[i] fd[fl[i]] += 4 vd[vl[i]] += 1 vd[vl[j]] += 2 vd[vl[k]] += 1 if i == j == k: # face: -> (x xx y yy j C) # (j C kk) vp[x] = vp[j] vp[yy] = x vp[y] = yy vp[xx] = y vp[j] = xx fp[kk] = x fp[x] = xx fp[xx] = y fp[y] = yy fp[yy] = j elif i == j: # face: -> (x xx y k B yy j C) # (j C kk) (k B ii) vp[yy] = vp[j] vp[y] = yy vp[xx] = y vp[j] = xx vp[x] = vp[k] vp[k] = x fp[ii] = yy fp[yy] = j fp[kk] = x fp[x] = xx fp[xx] = y fp[y] = k elif j == k: # face: -> (x xx i A y k B yy) # (i A jj) (k B ii) vp[yy] = vp[i] vp[i] = yy vp[y] = vp[k] vp[xx] = y vp[x] = xx vp[k] = x fp[ii] = yy fp[yy] = x fp[x] = xx fp[xx] = i fp[jj] = y fp[y] = k elif k == i: # face: -> (x xx i A y yy j C) # (i A jj) (j C kk) vp[y] = vp[j] vp[xx] = y vp[j] = xx vp[x] = vp[i] vp[yy] = x vp[i] = yy fp[kk] = x fp[x] = xx fp[xx] = i fp[jj] = y fp[y] = yy fp[yy] = j else: # general case # vertex: (...i...)(...j...)(...k...) -> (...i yy...)(...j xx y...)(...k x...) # edge : add (x y) (xx yy) # face : (i A j C k B) -> (x xx i A y k B yy j C) # # (i A jj) (j C kk) (k B ii) vp[yy] = vp[i] vp[i] = yy vp[y] = vp[j] vp[xx] = y vp[j] = xx vp[x] = vp[k] vp[k] = x fp[kk] = x fp[x] = xx fp[xx] = i fp[jj] = y fp[y] = k fp[ii] = yy fp[yy] = j
[docs] def remove_face_trisection(self, x): ep = self._ep fp = self._fp fl = self._fl fd = self._fd vp = self._vp vl = self._vl vd = self._vd x = int(x) xx = fp[x] y = ep[x] yy = ep[xx] if fl[x] != fl[y] or fl[x] != fl[xx] or fl[x] != fl[yy]: raise ValueError("not a trisection") # face: (x xx i A y k B yy j C) -> (i A j C k B) # -> (i A jj) (j C kk) (k B ii) i = fp[xx] k = fp[y] j = fp[yy] ii = ep[vp[yy]] # = fp^-1(yy) jj = ep[vp[y]] # = fp^-1(y) kk = ep[vp[x]] # = fp^-1(x) if fp[xx] == y and fp[y] == yy: # vertex (... j xx y yy x ...) -> (... j ...) # face (x xx y yy j C) -> (j C) # (j C kk) assert vp[j] == xx assert vp[xx] == y assert vp[yy] == x vp[j] = vp[x] fp[kk] = j elif fp[xx] == y: # face: (x xx y k B yy j C) -> (j C k B) # (j C kk) (k B ii) assert fp[y] != yy and fp[yy] != x assert vp[j] == xx assert vp[xx] == y assert vp[y] == yy vp[j] = vp[yy] assert vp[k] == x vp[k] = vp[x] fp[kk] = k fp[ii] = j elif fp[yy] == x: # face: (x xx i A y k B yy) -> (i A k B) # (i A jj) (k B ii) assert fp[xx] != y and fp[y] != yy assert vp[i] == yy vp[i] = vp[yy] assert vp[k] == x assert vp[x] == xx assert vp[xx] == y vp[k] = vp[y] fp[ii] = i fp[jj] = k elif fp[y] == yy: # face: (x xx i A y yy j C) -> (i A j C) # (i A jj) (j C kk) assert fp[xx] != y and fp[yy] != x assert vp[i] == yy assert vp[yy] == x vp[i] = vp[x] assert vp[j] == xx assert vp[xx] == y vp[j] = vp[y] fp[kk] = i fp[jj] = j else: # face: (x xx i A y k B yy j C) -> (i A j C k B) # (i A jj) (j C kk) (k B ii) assert fp[xx] != y and fp[y] != yy and fp[yy] != x assert vp[i] == yy vp[i] = vp[yy] assert vp[j] == xx assert vp[xx] == y vp[j] = vp[y] assert vp[k] == x vp[k] = vp[x] fp[jj] = j fp[kk] = k fp[ii] = i self._n -= 4 fd[fl[i]] -= 4 vd[vl[i]] -= 1 vd[vl[j]] -= 2 vd[vl[k]] -= 1 assert perm_check(vp, self._n), vp assert perm_check(fp, self._n), fp
###################################### # canonical labels and automorphisms # ###################################### # This is chosen so that augmentation works fast (for the exhaustive generation) # - augment1: trisection (single vertex, single face maps) # - augment2: face split (single vertex) # - augment3: vertex split def _good_starts(self, i0=-1): r""" EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: CM = [] sage: w = [0,1,2,3,4,5,0,6,7,1,2,5,3,4,6,7] sage: CM.append(FatGraph.from_unicellular_word(w)) sage: vp = '(0,15,3,6,8)(1,14,18,10,9,12,5,19)(2,7,4,17,11)(13,16)' sage: ep = '(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)' sage: fp = '(0,19,14)(1,8,10,17,13,9,6,2,15)(3,11,18,5,7)(4,12,16)' sage: CM.append(FatGraph(vp, ep, fp)) sage: for cm in CM: ....: gs = set(cm._good_starts()) ....: assert gs ....: for i in range(cm.num_darts()): ....: ggs = cm._good_starts(i) ....: if i in gs: ....: ggs = cm._good_starts(i) ....: assert ggs and ggs[0] == i and sorted(ggs) == sorted(gs), (gs, ggs, i) ....: else: ....: assert not ggs, (gs, ggs, i) """ n = self._n ep = self._ep vd = self._vd fd = self._fd fp = self._fp vl = self._vl fl = self._fl if i0 == -1: ans = [] else: ans = [i0] if self._nv > 1: # consider only edges with distinct start and end. # Maximize the degrees of vertices, then whether the # adjacent faces are distinct, then the degree of adjacent # faces. if i0 != -1: j0 = ep[i0] if vl[i0] == vl[j0]: return None best = (vd[vl[i0]], vd[vl[j0]], fl[i0] != fl[j0], fd[fl[i0]], fd[fl[j0]]) else: best = None for i in range(self._n): if i == i0: continue j = ep[i] if vl[i] == vl[j]: continue cur = (vd[vl[i]], vd[vl[j]], fl[i] != fl[j], fd[fl[i]], fd[fl[j]]) if best is None: best = cur if cur > best: if i0 != -1: return None else: del ans[:] best = cur if cur == best: ans.append(i) elif self._nf > 1: # (we have a single vertex but several faces) # consider only edges with distinct faces on their sides. # Maximize their degrees. if i0 != -1: j0 = ep[i0] if fl[i0] == fl[j0]: return None best = (fd[fl[i0]], fd[fl[j0]]) else: best = None for i in range(self._n): if i == i0: continue j = ep[i] if fl[i] == fl[j]: continue cur = (fd[fl[i]], fd[fl[j]]) if best is None: best = cur if cur > best: if i0 != -1: return None else: del ans[:] best = cur if cur == best: ans.append(i) else: # (we have a single face and a single vertex) # Minimize the face angle between i and ep[i] # 1. compute the "face angle" between the half edges fa = [None] * n fa[0] = 0 i = fp[0] j = 1 while i != 0: fa[i] = j i = fp[i] j += 1 # 2. first guess if i0 != -1: j0 = ep[i0] best = fa[j0] - fa[i0] if best < 0: best += n else: best = None # 3. run accross the edges for i in range(self._n): if i == i0: continue j = ep[i] cur = fa[j] - fa[i] if cur < 0: cur += n if best is None: best = cur if cur < best: if i0 != -1: return None else: del ans[:] best = cur if cur == best: ans.append(i) return ans def _canonical_labelling_from(self, i0): r""" Edges gets relabelled (2i, 2i+1). OUTPUT: a triple ``(fc, fd, rel)`` where - ``fc`` is the list of edges seen along the walk (with respect to the new numbering) - ``fd``: face degrees seen along the walk - ``rel``: relabelling map {current labels} -> {canonical labels} EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,15,3,6,8)(1,14,18,10,9,12,5,19)(2,7,4,17,11)(13,16)' sage: ep = '(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)' sage: fp = '(0,19,14)(1,8,10,17,13,9,6,2,15)(3,11,18,5,7)(4,12,16)' sage: cm = FatGraph(vp, ep, fp) sage: for i in range(20): ....: fc, fd, rel = cm._canonical_labelling_from(i) ....: assert len(fc) == 20 ....: assert sorted(fd, reverse=True) == [9, 5, 3, 3] ....: assert sorted(rel) == list(range(20)) """ n = self._n ep = self._ep fp = self._fp fc = [] # faces seen along the walk fd = [] # face degrees seen along the walk rel = [-1] * n # dart relabeling rel[i0] = 0 # first edge is relabelled (0,1) fc.append(0) c = 2 # current dart number (in the new labelling scheme) # walk along faces first, starting from i0 # along the way, we collect unseen edges i = fp[i0] wait = deque([ep[i0]]) cyc = [0] d = 1 while i != i0: if rel[i] == -1: j = ep[i] if rel[j] != -1: assert rel[j] % 2 == 0 rel[i] = rel[j] + 1 else: rel[i] = c c += 2 wait.append(j) fc.append(rel[i]) d += 1 i = fp[i] fd.append(d) while wait: i0 = wait.popleft() if rel[i0] != -1: continue assert rel[ep[i0]] != -1 and rel[ep[i0]] % 2 == 0 rel[i0] = rel[ep[i0]] + 1 fc.append(rel[i0]) i = fp[i0] d = 1 while i != i0: if rel[i] == -1: j = ep[i] if rel[j] != -1: assert rel[j] % 2 == 0 rel[i] = rel[j] + 1 else: rel[i] = c c += 2 wait.append(j) fc.append(rel[i]) i = fp[i] d += 1 fd.append(d) assert len(fc) == self._n, (fc, fd, rel) assert len(fd) == self._nf, (fc, fd, rel) return fc, fd, rel # TODO: this is a waste! We should implement the proper partial relabeling def _canonical_labelling_from_if_better(self, best, i0): r""" INPUT: - ``best`` - a triple ``(fc, fd, rel)`` as given from _canonical_labeling_from - ``i0`` - start edge """ fc_best, fd_best, rel_best = best n = self._n ep = self._ep fp = self._fp fl = self._fl sfd = self._fd is_fd_better = 0 # whether the current face degree works better is_fc_better = 0 # whether the current relabelling works better # 0 = equal # 1 = better # -1 = worse fd = [] # face degrees seen along the walk (want to maximize) fc = [] # edges seen along the walk (want to minimize) rel = [-1] * n # dart relabeling # walk along faces first, starting from i0 # along the way, we collect unseen edges rel[i0] = 0 # first edge is relabelled (0,1) c = 2 # current dart number (in the new labelling scheme) d = sfd[fl[i0]] if d < fd_best[0]: return -1, None elif d > fd_best[0]: is_fd_better = 1 fd.append(d) fc.append(0) i = fp[i0] wait = deque([ep[i0]]) cyc = [0] while i != i0: if rel[i] == -1: j = ep[i] if rel[j] != -1: assert rel[j] % 2 == 0 rel[i] = rel[j] + 1 else: rel[i] = c c += 2 wait.append(j) # edge comparison ii = rel[i] if not is_fd_better and not is_fc_better: if ii < fc_best[len(fc)]: is_fc_better = 1 elif ii > fc_best[len(fc)]: if self._nf == 1: return -1, None is_fc_better = -1 fc.append(ii) i = fp[i] while wait: i0 = wait.popleft() # face already seen? if rel[i0] != -1: continue # face degree comparison d = sfd[fl[i0]] if not is_fd_better: if d < fd_best[len(fd)]: return -1, None elif d > fd_best[len(fd)]: is_fd_better = 1 fd.append(d) # root edge comparison assert rel[ep[i0]] != -1 and rel[ep[i0]] % 2 == 0 ii0 = rel[ep[i0]] + 1 if not is_fd_better and not is_fc_better: if ii0 < fc_best[len(fc)]: is_fc_better = 1 elif ii0 > fc_best[len(fc)]: is_fc_better = -1 rel[i0] = ii0 fc.append(ii0) i = fp[i0] while i != i0: # label the i-th edge (if not already) if rel[i] == -1: j = ep[i] if rel[j] != -1: assert rel[j] % 2 == 0 rel[i] = rel[j] + 1 else: rel[i] = c c += 2 wait.append(j) # edge comparison ii = rel[i] if not is_fd_better and not is_fc_better: if ii < fc_best[len(fc)]: is_fc_better = 1 elif ii > fc_best[len(fc)]: is_fc_better = -1 # update fc.append(ii) i = fp[i] cur = (fc, fd, rel) if is_fd_better: return 1, cur else: return is_fc_better, cur def _is_canonical(self, i0): r""" Return a pair ``(answer, automorphisms)`` where answer is a boolean that says whether this map is in canonical form and ``automorphisms`` form a generating set of the group of automorphisms. EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: vp = '(0,15,3,6,8)(1,14,18,10,9,12,5,19)(2,7,4,17,11)(13,16)' sage: ep = '(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)' sage: fp = '(0,19,14)(1,8,10,17,13,9,6,2,15)(3,11,18,5,7)(4,12,16)' sage: cm = FatGraph(vp, ep, fp) sage: any(cm._is_canonical(i)[0] for i in range(20)) True A genus 1 example with 4 symmetries:: sage: vp = '(0,8,6,4,3,7)(1,9,11,5,2,10)' sage: ep = '(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)' sage: fp = '(0,10,9)(2,4,11)(1,7,8)(3,5,6)' sage: cm = FatGraph(vp, ep, fp) sage: for i in range(12): ....: test, aut_grp = cm._is_canonical(i) ....: if test: print(aut_grp.group_cardinality()) 4 4 4 4 """ roots = self._good_starts(i0) if roots is None: return False, None if len(roots) == 1: return True, None # perform complete relabelling P = PermutationGroupOrbit(self._n, [], roots) i = next(P) assert i == i0 best = self._canonical_labelling_from(i) rel0 = perm_invert(best[2]) for i in P: test, cur = self._canonical_labelling_from_if_better(best, i) if test == 1: return False, None elif test == 0: fc, fd, rel = cur aut = perm_compose(rel, rel0) P.add_generator(aut) return True, P
[docs] def automorphism_group(self): r""" EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: from surface_dynamics.misc.permutation import perm_conjugate The four unicellular map with 4 edges in genus 2:: sage: cm0 = FatGraph.from_unicellular_word([0,1,0,1,2,3,2,3]) sage: cm1 = FatGraph.from_unicellular_word([0,1,0,2,1,3,2,3]) sage: cm2 = FatGraph.from_unicellular_word([0,1,0,2,3,1,2,3]) sage: cm3 = FatGraph.from_unicellular_word([0,1,2,3,0,1,2,3]) sage: for cm in [cm0, cm1, cm2, cm3]: ....: P = cm.automorphism_group() ....: print(P.group_cardinality()) ....: vp = cm.vertex_permutation() ....: ep = cm.edge_permutation() ....: fp = cm.face_permutation() ....: for a in P.gens(): ....: pp = perm_conjugate(vp, a) ....: assert pp == vp, (vp, pp) 2 1 1 8 sage: cm = FatGraph.from_unicellular_word([0,1,2,3,0,4,1,2,3,4]) sage: cm.automorphism_group().group_cardinality() 2 An example with two faces:: sage: vp = '(0,9,5,6,7,4,8,1,2,3)' sage: ep = '(0,2)(1,3)(4,6)(5,7)(8,9)' sage: fp = '(0,1,2,3,8)(4,5,6,7,9)' sage: cm = FatGraph(vp,ep,fp) sage: cm.automorphism_group() PermutationGroupOrbit(10, [(0,4)(1,5)(2,6)(3,7)(8,9)]) """ roots = self._good_starts() P = PermutationGroupOrbit(self._n, [], roots) if len(roots) == 1: return P i0 = next(P) best = self._canonical_labelling_from(i0) rel0 = perm_invert(best[2]) for i in P: test, cur = self._canonical_labelling_from_if_better(best, i) if test == 1: rel0 = perm_invert(cur[2]) best = cur elif test == 0: fc, fd, rel = cur aut = perm_compose(rel, rel0) P.add_generator(aut) return P
[docs] def relabel(self, r): r""" Relabel according to the permutation ``p`` EXAMPLES:: sage: from surface_dynamics.topology.fat_graph import FatGraph sage: cm = FatGraph.from_unicellular_word([0,1,0,1,2,3,2,3]) sage: cm.relabel([4,7,0,2,3,5,1,6]) sage: cm._check() """ n = self._n self._vp = perm_conjugate(self._vp, r, n) self._ep = perm_conjugate(self._ep, r, n) self._fp = perm_conjugate(self._fp, r, n) vl = [None] * n fl = [None] * n fa = [None] * n for i in range(n): j = r[i] vl[j] = self._vl[i] fl[j] = self._fl[i] self._vl = vl self._fl = fl