Source code for surface_dynamics.topology.fat_graph_exhaustive_generation

r"""
Exhaustive generation of fat graphs.

This is done following the McKay canonical augmentation. This module
is experimental.
"""

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

import numbers

from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ

from sage.stats.basic_stats import mean

from .fat_graph import FatGraph

###########################
# 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)
########################## # Augmentation functions # ########################## # augment1: trisection
[docs]def augment1(cm, aut_grp, g, callback): r""" Given a unicellular map ``cm`` with a single vertex and automorphism group ``aut_grp``, iterate through all its canonical extensions that are uniface-univertex maps of greater genus. This operation inserts two edes. This augmentation function is sufficient to iterate through unicellular map. """ n = cm._n fd = cm._fd fl = cm._fl fp = cm._fp i = 0 if aut_grp is None: R = range(n) else: aut_grp.reset_iterator() R = aut_grp for i in R: j = i for sj in range(fd[fl[i]]): k = j for sk in range(fd[fl[i]] - sj + (i != j)): cm.trisect_face(i, j, k) test, aaut_grp = cm._is_canonical(n) callback('augment1', test, cm, aaut_grp, g-1) if test and g>1: augment1(cm, aaut_grp, g - 1, callback) cm.remove_face_trisection(n) k = fp[k] j = fp[j] i = fp[i]
# augment2: face split # (essentially the same as augment3)
[docs]def augment2(cm, aut_grp, depth, callback): r""" Given a map ``cm`` with a single vertex and automorphism group ``aut_grp`` iterate through all its canonical extensions that are obtained by splitting one of its faces (by adding a single edge). Because of the chosen canonical labellings, we only need to consider the faces with maximal degree and split in such way that the secondly created face is still at least as big as the second biggest. """ n = cm._n nf = cm._nf fp = cm._fp fd = cm._fd fl = cm._fl if aut_grp is None: R = range(n) else: aut_grp.reset_iterator() R = aut_grp # TODO find edges with the highest face degrees on their sides # (the split must remain higher than them) fdmax0 = 0 fdmax1 = 0 for i in range(nf): if fd[i] > fdmax0: fdmax1 = fdmax0 fdmax0 = fd[i] if callback is not None: parent = cm.to_string() for i in R: j = i if fdmax1 <= 1: if fd[fl[i]] < fdmax0 - 1: continue niter = fd[fl[i]] elif fd[fl[i]] != fdmax0 or vd[fl[i]] < 2 * fdmax1 - 2: continue else: for _ in range(fdmax1 - 1): j = fp[j] niter = fd[fl[i]] - 2*fdmax1 + 3 for _ in range(niter): cm.split_face(i, j) test, aaut_grp = cm._is_canonical(n) callback('augment2', test, cm, aaut_grp, depth-1) if test and depth > 1: augment2(cm, aaut_grp, depth-1, callback) cm.remove_edge(n) j = fp[j]
# augment3: vertex split
[docs]def augment3(cm, aut_grp, depth, min_degree, callback): r""" Given a map ``cm``, its automorphism group ``aut_grp`` and a minimum degree ``min_degree``, iterate through all the canonical extensions of ``cm`` that are obtained by splitting ``depth`` times a vertices into two vertices. This augmentation add ``depth`` edges to the fat graph. In principle, because of the chosen canonical labellings, we only need to consider the vertices with maximal degree. """ n = cm._n nv = cm._nv vp = cm._vp vd = cm._vd vl = cm._vl if aut_grp is None: R = range(n) else: aut_grp.reset_iterator() R = aut_grp # TODO: find edges with the highest vertex degrees on their ends # the split must remain higher than them vdmax0 = 0 vdmax1 = 0 for i in range(nv): if vd[i] > vdmax0: vdmax1 = vdmax0 vdmax0 = vd[i] min_degree_loc = max(min_degree, vdmax1) for i in R: # vertex degrees are split as d -> (d1 + 1, d2 + 1) # so, if min_degree > 1 we can ignore the first/last half edges # moreover, by the choosen canonical labelling, the degrees of # the split vertices must remain larger than any other j = i if min_degree_loc == 1: if vd[vl[i]] < vdmax0 - 1: continue niter = vd[vl[i]] elif vd[vl[i]] != vdmax0 or vd[vl[i]] < 2 * min_degree_loc - 2: continue else: for _ in range(min_degree_loc - 1): j = vp[j] niter = vd[vl[i]] - 2*min_degree_loc + 3 for _ in range(niter): cm.split_vertex(i, j) assert vd[vl[i]] >= min_degree_loc assert vd[vl[j]] >= min_degree_loc test, aaut_grp = cm._is_canonical(n) callback('augment3', test, cm, aaut_grp, depth-1) if test and depth > 1: augment3(cm, aaut_grp, depth-1, min_degree, callback) cm.contract_edge(n) j = vp[j]
# TODO
[docs]def augment4(cm): r""" Plant vertices of degree 1,2. """
######################################## # Callbacks for the various map reduce # ######################################## # callback to count elements (behaves somehow as a 2-tuple)
[docs]class CountAndWeightedCount(object): def __init__(self): self.count = ZZ(0) self.weighted_count = QQ(0) def __repr__(self): return "(%s, %s)" % (self.count, self.weighted_count) def __len__(self): return 2 def __getitem__(self, i): if not isinstance(i, numbers.Integral): raise TypeError i = int(i) if i == -1 or i == 1: return self.weighted_count elif i == 0: return self.count else: raise IndexError("index out of range") def __eq__(self, other): if type(self) is not type(other): raise TypeError return self.count == other.count and self.weighted_count == other.weighted_count def __ne__(self, other): if type(self) is not type(other): raise TypeError return self.count != other.count or self.weighted_count != other.weighted_count def __call__(self, cm, aut): self.count += ZZ(1) self.weighted_count += QQ((1, (1 if aut is None else aut.group_cardinality())))
# callback to list elements
[docs]class ListCallback(object): def __init__(self): self._list = [] def __call__(self, cm, aut): self._list.append(cm.copy())
[docs] def list(self): return self._list
# TODO: make it work again! This is the most precious piece of information # to enhance the exhaustive generation... # Callback for getting a full trace of the execution grapvhiz_header="""/****************************************************************/ /* Trace execution of fat graphs generation */ /* */ /* root: vp={vp:6} ep={ep:6} fp={fp:6} */ /* g = {g:2} */ /* nf = {nf:2} */ /* nv = {nv:2} */ */ To compile to a graph in pdf format run */ */ $ sfpdf -Tpdf -o OUTPUT.pdf INPUT.dot */ */ /****************************************************************/ """
[docs]class FatGraphsTrace(object): """ A class to trace the execution of the fat graphs generation. It is mostly used for debugging/profiling/illustration purposes. """ def __init__(self, filename=None, verbosity=0): self._verbosity = int(verbosity) self._properties = {} self._k = 0 # current number of vertices self._vdepth = {} # vertex -> depth self._vnum = {} # vertex -> apparition in the iteration self._edges = {} # parent -> child self._bad_explore = {} # vertex -> number of dead end self._vaut = {} # number of automorphisms def __repr__(self): return 'FatGraphs trace for {%s}' % (', '.join('%s=%s' % (k,v) for k,v in sorted(self._properties.items())))
[docs] def summary(self, filename=None): if filename is None: from sys import stdout f = stdout else: f = open(fiename, 'w') f.write(repr(self)) f.write('\n') if not self._vdepth: if filename is not None: f.close() return count_by_depth = defaultdict(int) for v in self._vdepth.values(): count_by_depth[v] += 1 max_depth = max(count_by_depth) mean_depth = float(sum(k*v for k,v in count_by_depth.items())) / sum(v for v in count_by_depth.values()) childless_by_depth = defaultdict(int) for v,child in self._edges.items(): if self._vdepth[v] != max_depth and not child: childless_by_depth[self._vdepth[v]] += 1 bad_explore_by_depth = defaultdict(int) for v,num in self._bad_explore.items(): bad_explore_by_depth[self._vdepth[v]] += num f.write('depth : %d\n' % max_depth) f.write('mean depth : %f\n' % mean_depth) f.write('total num fat graphs : %d\n' % len(self._vdepth)) f.write('by depth num fat graphs : %s\n' % ' '.join('%d' % count_by_depth[i] for i in range(max_depth + 1))) f.write('total bad explore : %d\n' % sum(bad_explore_by_depth.values())) f.write('by depth bad explore : %s\n' % ' '.join('%d' % bad_explore_by_depth[i] for i in range(max_depth + 1))) f.write('total childless : %d\n' % sum(childless_by_depth.values())) f.write('by depth childless : %s\n' % ' '.join('%d' % childless_by_depth[i] for i in range(max_depth + 1))) if filename is not None: f.close()
def __call__(self, cm, aut): pass
[docs] def add_vertex(self, s, aut_grp, depth): if self._verbosity >= 1: print('add_vertex(s={}, depth={})'.format(s, depth)) if s in self._vdepth: raise RuntimeError("already explored vertex!") self._vdepth[s] = depth self._bad_explore[s] = 0 self._vnum[s] = self._k self._edges[s] = [] self._k += 1 self._vaut[s] = 1 if aut_grp is None else aut_grp.group_cardinality()
[docs] def add_edge(self, s0, s1): if self._verbosity >= 1: print('add_edge(s0={}, s1={})'.format(s0, s1)) if s0 not in self._edges: raise RuntimeError("_edges not properly initialized") self._edges[s0].append(s1)
[docs] def root(self, cm, aut_grp): if self._k: raise RuntimeError("trying to set root in a non-empty trace") s = cm.to_string() if self._verbosity >= 1: print('root(cm={})'.format(s)) self.add_vertex(s, aut_grp, 0)
[docs] def canonical_edge(self, parent, cm, aut_grp, caller): if not isinstance(parent, str): raise RuntimeError s = cm.to_string() if self._verbosity >= 1: print('canonical_edge(parent={}, cm={}, caller={})'.format(parent, s, caller)) if parent not in self._edges: raise RuntimeError("_edges not properly initialized at %s" % parent) if s in self._edges: raise RuntimeError("s already in _edges") self.add_vertex(s, aut_grp, self._vdepth[parent] + 1) self.add_edge(parent, s)
[docs] def non_canonical_edge(self, parent, cm, caller): if not isinstance(parent, str): raise RuntimeError if self._verbosity >= 1: print('non_canonical_edge(parent={}, caller={})'.format(parent, caller)) if parent not in self._edges: raise RuntimeError("_edges not properly initialized at %s" % parent) self._bad_explore[parent] += 1
[docs] def grapvhiz_tree(self, filename=None): if filename is None: from sys import stdout output = stdout else: output = open(filename, 'w') if filename is not None: output.close() f = open(filename, 'w') f.write(header.format(vp=vp, ep=ep, fp=fp, g=g, nf=nf, nv=nv)) f.write('digraph Tree {\n') f.write(' rankdir = TB;\n') col1 = "#FF0000" col2 = "#00FF00" col3 = "#0000FF" a0 = cm0.automorphism_group() s0 = cm0.to_string() f.write(""" %s [label="%s"];\n""" % (s0, 0)) for cm1, a1 in augment1(cm0, a0, g, False): s1 = cm1.to_string() if s0 != s1: f.write(""" %s [label="%s"];\n""" % (s1, 0)) f.write(""" %s -> %s [color="%s"];\n""" %(s0, s1, col1)) for cm2, a2 in augment2(cm1, a1, nnf, intermediate): s2 = cm2.to_string() if s2 != s1: f.write(""" %s [label="%s"];\n""" % (s2, 0)) f.write(""" %s -> %s [color="%s"];\n""" %(s1, s2, col2)) for cm3, a3 in augment3(cm2, a2, nnv, vertex_min_degree, intermediate): s3 = cm3.to_string() if s3 != s2: f.write(""" %s [label="%s"];\n""" % (s3, 0)) f.write(""" %s -> %s [color="%s"];\n""" %(s2, s3, col3)) yield cm3, a3
################# # Main iterator # #################
[docs]class StackCallback(object): def __init__(self, cm, aut, gmin, gdepth, nfmin, nfdepth, nvmin, nvdepth, min_degree, callback, filter): self._gmin = gmin self._gdepth = gdepth self._nfmin = nfmin self._nfdepth = nfdepth self._nvmin = nvmin self._nvdepth = nvdepth self._cm = cm self._aut = aut self._callback = callback self._min_degree = min_degree self._filter = filter # print("StackCallback(gmin={}, gdepth={}, nfmin={}, nfdepth={}, nvmin={}, nvdepth={}".format( # self._gmin, self._gdepth, self._nfmin, self._nfdepth, self._nvmin, self._nvdepth)) def __call__(self, caller, test, cm, aut, depth): if test: if caller == 'augment1': # we know the map has one vertex and one edge and hence 4g = n if cm._n >= 4 * self._gmin: if cm._nv >= self._nvmin and cm._nf >= self._nfmin and \ (self._filter is None or self._filter(cm,aut)): self._callback(cm, aut) # more faces? if self._nfdepth: augment2(cm, aut, self._nfdepth, self) # more vertices? elif self._nvdepth: augment3(cm, aut, self._nvdepth, self._min_degree, self) elif caller == 'augment2': if cm._nf >= self._nfmin: if cm._nv >= self._nvmin and \ (self._filter is None or self._filter(cm, aut)): self._callback(cm, aut) # more vertices? if self._nvdepth: augment3(cm, aut, self._nvdepth, self._min_degree, self) elif caller == 'augment3': if cm._nv >= self._nvmin and \ (self._filter is None or self._filter(cm, aut)): self._callback(cm, aut)
[docs] def run(self): if self._gdepth: augment1(self._cm, self._aut, self._gdepth, self) elif self._nfdepth: augment2(self._cm, self._aut, self._nfdepth, self) elif self._nvdepth: augment3(self._cm, self._aut, self._nvdepth, self._min_degree, self) elif self._filter is None or self._filter(cm, aut): self._callback(self._cm, self._aut)
############## # Main class # ##############
[docs]class FatGraphs_g_nf_nv(object): r""" Isomorphism classes of fat graphs with given genus, number of faces and number of vertices. EXAMPLES:: sage: from surface_dynamics.topology.fat_graph_exhaustive_generation import FatGraphs_g_nf_nv Trees and their dual (maps with single vertex) in genus zero are counted by Catalan numbers:: sage: for n in range(2, 10): ....: ntrees1 = 2 * (n-1) * FatGraphs_g_nf_nv(0, n, 1).weighted_cardinality() ....: ntrees2 = 2 * (n-1) * FatGraphs_g_nf_nv(0, 1, n).weighted_cardinality() ....: assert catalan_number(n-1) == ntrees1 == ntrees2, n Genus zero with same number of vertices and faces:: sage: FatGraphs_g_nf_nv(0, 2, 2).cardinality_and_weighted_cardinality() (2, 5/4) sage: FatGraphs_g_nf_nv(0, 3, 3).cardinality_and_weighted_cardinality() (23, 41/2) sage: FatGraphs_g_nf_nv(0, 4, 4).cardinality_and_weighted_cardinality() (761, 8885/12) Duality checks sage: for g,nf,nv in [(0,2,3), (0,2,4), (0,3,4), ....: (1,1,2), (1,1,3), (1,1,4), (1,1,5), (1,2,3), (1,2,4), (1,3,4), ....: (2,1,2), (2,1,3)]: ....: n1 = FatGraphs_g_nf_nv(g, nf, nv).cardinality_and_weighted_cardinality() ....: n2 = FatGraphs_g_nf_nv(g, nv, nf).cardinality_and_weighted_cardinality() ....: assert n1 == n2 ....: print(g, nf, nv, n1) 0 2 3 (5, 11/3) 0 2 4 (14, 93/8) 0 3 4 (108, 103) 1 1 2 (3, 5/3) 1 1 3 (11, 35/4) 1 1 4 (46, 42) 1 1 5 (204, 385/2) 1 2 3 (180, 172) 1 2 4 (1198, 14065/12) 1 3 4 (18396, 18294) 2 1 2 (53, 483/10) 2 1 3 (553, 539) Unicellular map with one vertex in genus 3:: sage: FatGraphs_g_nf_nv(3, 1, 1).cardinality_and_weighted_cardinality() (131, 495/4) Minimum vertex degree bounds:: sage: for k in range(2,5): ....: F = FatGraphs_g_nf_nv(1, 2, 2, vertex_min_degree=1) ....: c1 = F.cardinality_and_weighted_cardinality(lambda cm,_: cm.vertex_degree_min() >= k) ....: G = FatGraphs_g_nf_nv(1, 2, 2, vertex_min_degree=k) ....: c2 = G.cardinality_and_weighted_cardinality() ....: assert c1 == c2 ....: print(c1) (14, 87/8) (8, 47/8) (4, 15/8) sage: for k in range(2,6): ....: F = FatGraphs_g_nf_nv(0, 5, 2, vertex_min_degree=1) ....: c1 = F.cardinality_and_weighted_cardinality(lambda cm,_: cm.vertex_degree_min() >= k) ....: G = FatGraphs_g_nf_nv(0, 5, 2, vertex_min_degree=k) ....: c2 = G.cardinality_and_weighted_cardinality() ....: assert c1 == c2 ....: print(c1) (28, 123/5) (21, 88/5) (13, 48/5) (7, 18/5) Using ranges for vertex and face numbers:: sage: F = FatGraphs_g_nf_nv(1, nv_min=2, nv_max=4, nf_min=2, nf_max=4) sage: def check(cm,aut): ....: if cm.num_vertices() < 2 or \ ....: cm.num_vertices() >= 4 or \ ....: cm.num_faces() < 2 or \ ....: cm.num_faces() >= 4: ....: raise ValueError(str(cm)) sage: F.map_reduce(check) sage: for nf in [2,3]: ....: for nv in [2,3]: ....: c1 = F.cardinality_and_weighted_cardinality(lambda cm,_: cm.num_vertices() == nv and cm.num_faces() == nf) ....: c2 = FatGraphs_g_nf_nv(1, nf, nv).cardinality_and_weighted_cardinality() ....: assert c1 == c2 ....: print(nf, nv, c1) 2 2 (24, 167/8) 2 3 (180, 172) 3 2 (180, 172) 3 3 (2048, 6041/3) """ def __init__(self, g=None, nf=None, nv=None, vertex_min_degree=1, g_min=None, g_max=None, nf_min=None, nf_max=None, nv_min=None, nv_max=None): r""" INPUT: - ``g``, ``g_min``, ``g_max`` - the genus - ``nf``, ``nf_min``, ``nf_max`` - number of faces - ``nv``, ``nv_min``, ``nv_max`` - number of vertices - ``vertex_min_degree`` - minimal number of vertices (default to ``1``) - ``intermediate`` - if set to ``True`` then return all graphs with genus = g, number of faces <= nf and number of vertices <= nv that satisfy the ``vertex_min_degree`` constraint """ self._gmin, self._gmax = self._get_interval(g, g_min, g_max, 0, 'g') if self._gmax != self._gmin + 1: raise ValueError("not implemented for genus in an interval") self._fmin, self._fmax = self._get_interval(nf, nf_min, nf_max, 1, 'nf') self._vmin, self._vmax = self._get_interval(nv, nv_min, nv_max, 1, 'nv') self._vertex_min_degree = ZZ(vertex_min_degree) def _get_interval(self, v, vmin, vmax, low_bnd, name): if v is not None: if not isinstance(v, numbers.Integral): raise TypeError("%s must be an integral" % name) v = ZZ(v) if v < low_bnd: raise ValueError("%s must be >= %d" % (name, low_bnd)) return (v, v+1) if vmax is None: raise ValueError("at least %s or %s_max must be set" % (name, name)) if not isinstance(vmax, numbers.Integral): raise ValueError("%s_max must be integral" % name) vmax = ZZ(vmax) if vmin is None: vmin = low_bnd elif not isinstance(vmin, numbers.Integral): raise TypeError("%s_min must be integral" % name) vmin = ZZ(vmin) if vmin < low_bnd: raise ValueError("%s_min must be >= %s" % (name, low_bnd)) return vmin, vmax def __repr__(self): return "Fat graphs of genus %d, %d faces and %d vertices" % (self._g, self._nf, self._nv)
[docs] def map_reduce(self, callback, filter=None): r""" EXAMPLES:: sage: from __future__ import print_function sage: from surface_dynamics.topology.fat_graph_exhaustive_generation import FatGraphs_g_nf_nv sage: FatGraphs_g_nf_nv(1, 2, 2).map_reduce(lambda x,y: print(x)) FatGraph('(0,6,5,4,1,2,3)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,3,4,6,7)(5)') FatGraph('(0,6,1,2,3)(4,7,5)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,3,6,4,7)(5)') FatGraph('(0,5,4,1,6,2,3)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,6,7,1,2,3,4)(5)') FatGraph('(0,7,2,3)(1,6,5,4)', '(0,2)(1,3)(4,5)(6,7)', '(0,7,1,2,3,4,6)(5)') FatGraph('(0,5,4,1,2,6,3)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,6,7,2,3,4)(5)') FatGraph('(0,7,3)(1,2,6,5,4)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,7,2,3,4,6)(5)') FatGraph('(0,5,4,1,2,3,6)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,6,7,3,4)(5)') FatGraph('(0,7)(1,2,3,6,5,4)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,7,3,4,6)(5)') FatGraph('(0,5,4,6,1,2,3)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,3,6,7,4)(5)') FatGraph('(0,5,4,6,2,3)(1,7)', '(0,2)(1,3)(4,5)(6,7)', '(0,6,1,2,3,7,4)(5)') FatGraph('(0,5,6,4,1,2,3)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,3,4)(5,6,7)') FatGraph('(0,5,6,1,2,3)(4,7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,3,6,4)(5,7)') FatGraph('(0,5,6,2,3)(1,7,4)', '(0,2)(1,3)(4,5)(6,7)', '(0,6,1,2,3,4)(5,7)') FatGraph('(0,5,6,3)(1,2,7,4)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,6,2,3,4)(5,7)') FatGraph('(0,6,5,1,2,4,3)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,4,6,7)(2,3,5)') FatGraph('(0,6,1,2,4,3)(5,7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,4,7)(2,3,6,5)') FatGraph('(0,6,4,3)(1,2,7,5)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,4,7)(2,3,5,6)') FatGraph('(0,6,5,1,2,3,4)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,4,6,7)(3,5)') FatGraph('(0,5,1,6,2,3,4)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,6,7,1,2,4)(3,5)') FatGraph('(0,5,1,6,3,4)(2,7)', '(0,2)(1,3)(4,5)(6,7)', '(0,7,1,6,2,4)(3,5)') FatGraph('(0,5,1,2,3,6,4)(7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,4)(3,5,6,7)') FatGraph('(0,5,1,2,3,6)(4,7)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,6,4)(3,5,7)') FatGraph('(0,7,4)(1,2,3,6,5)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,4,6)(3,5,7)') FatGraph('(0,5,7,4)(1,2,3,6)', '(0,2)(1,3)(4,5)(6,7)', '(0,1,2,4)(3,6,5,7)') """ g = self._gmin fmin = self._fmin fmax = self._fmax vmin = self._vmin vmax = self._vmax if g == 0: if fmin == 1 and vmin == 1: raise NotImplementedError elif fmin > 1: # start with face splitting of the bicellular map (g = 0, nv = 1, nf = 2) cm0 = FatGraph('(0,1)', '(0,1)', '(0)(1)') gshift = 0 vshift = - 1 fshift = - 2 elif vmin > 1: # start with vertex splitting of the unicellular map (g = 0, nv = 2, nf = 1) cm0 = FatGraph('(0)(1)', '(0,1)', '(0,1)') gshift = 0 vshift = - 2 fshift = - 1 else: raise RuntimeError("this should not happen") else: # start with trisection of the trivial map (g = 1, nv = 1, nf = 1) cm0 = FatGraph.from_unicellular_word([0,1,0,1]) gshift = - 1 vshift = - 1 fshift = - 1 cm0._realloc(4 * g + 2 * (fmax + vmax - 2)) a0 = cm0.automorphism_group() StackCallback(cm0, a0, g, # gmin g + gshift, # depth for trisections fmin, # nfmin fmax + fshift - 1, # depth for face splitting vmin, # nvmin vmax + vshift - 1, # depth for vertex splitting self._vertex_min_degree, callback, filter).run()
[docs] def cardinality_and_weighted_cardinality(self, filter=None): N = CountAndWeightedCount() self.map_reduce(N, filter) return tuple(N)
[docs] def weighted_cardinality(self, filter=None): N = CountAndWeightedCount() self.map_reduce(N, filter) return N[1]
[docs] def list(self): r""" EXAMPLES:: sage: from surface_dynamics.topology.fat_graph_exhaustive_generation import FatGraphs_g_nf_nv sage: L21 = FatGraphs_g_nf_nv(0, 2, 1).list() sage: L21[0].num_faces() 2 sage: L21[0].num_vertices() 1 sage: L12 = FatGraphs_g_nf_nv(0, 1, 2).list() sage: L12[0].num_faces() 1 sage: L12[0].num_vertices() 2 """ L = ListCallback() self.map_reduce(L) return L.list()