Source code for surface_dynamics.flat_surfaces.separatrix_diagram

r"""
Separatrix diagrams and cylinder diagrams

A separatrix diagram is a couple of permutation ``(bot,top)`` that have the same
number of cycles in their cycle decompositions. A cylinder diagram is a
separatrix diagram together with a bijection between the cycles of ``bot`` and
``top``.

A cylinder diagram encodes the combinatorics of cylinder decomposition of a
completely periodic direction in a translation surface. If we adjoin coordinates
to this combinatorial datum, we have a complete description of the underlying
surface. In the case of arithmetic curves, the coordinates can be taken to be
rational numbers.

This representation of a surface is used in various constructions:

- square tiled surfaces

- Thurston-Veech construction of pseudo-Anosov diffeomorphism

- description of the cusp of Teichmueller curves

.. TODO::

    - We need a more general structure to encode configurations of structure of
      saddle connections (which need not be completely periodic directions (see
      [EMZ]_, [MZ]_)

    - Gray code for conjugacy classes of permutation in order to optimize the
      generation of separatrix and cylinder diagrams.

REFERENCES:

.. [EMZ] A. Eskin, H. Masur, A. Zorich "Principal boundary ... and Siegel-Veech
         constant"

.. [MZ]  H. Masur, A. Zorich "Multiple saddle connections on flat surfaces and
         the principal boundary of the moduli spaces of quadratic
         differentials"

.. [N]   Y. Naveh "Tight upper bounds on the number of invariant components on
         translation surfaces", Isr. J. Math. 165, 211-231 (2008)

EXAMPLES::

    sage: from surface_dynamics.all import *

Separatrix diagrams::

    sage: s = SeparatrixDiagram('(0,1,2)(3,4)(5,6,7)','(0,4,1,2)(3,7)(5,6)')
    sage: s
    (0,1,2)(3,4)(5,6,7)-(0,4,1,2)(3,7)(5,6)
    sage: s.bot_cycle_tuples()
    [(0, 1, 2), (3, 4), (5, 6, 7)]
    sage: s.top_cycle_tuples()
    [(0, 4, 1, 2), (3, 7), (5, 6)]

Cylinder diagrams::

    sage: c = CylinderDiagram([((0,),(4,)),((1,2),(0,1,3)),((3,4),(2,))])
    sage: print(c)
    (0)-(4) (1,2)-(0,1,3) (3,4)-(2)
    sage: print(c.separatrix_diagram())
    (0)(1,2)(3,4)-(0,1,3)(2)(4)

They can also be built from separatrix diagram::

    sage: s = SeparatrixDiagram('(0,1,2)(3,4)(5,6,7)','(0,4,1,2)(3,7)(5,6)')
    sage: s
    (0,1,2)(3,4)(5,6,7)-(0,4,1,2)(3,7)(5,6)
    sage: s.to_cylinder_diagram([(0,1),(1,0),(2,2)])
    (0,1,2)-(3,7) (3,4)-(0,4,1,2) (5,6,7)-(5,6)
"""
from __future__ import print_function
from sage.structure.sage_object import SageObject

import itertools
import sage.arith.misc as arith
from sage.rings.integer import Integer

from sage.graphs.digraph import DiGraph

from surface_dynamics.misc.permutation import (perm_check, equalize_perms, init_perm,
        perm_cycle_tuples, perm_cycle_string, perm_compose, perm_compose_i,
        perm_orbit, perm_invert, perms_canonical_labels,
        perms_transitive_components, canonical_perm, canonical_perm_i)

#
# Abelian and quadratic Separatrix Diagram
#
[docs]def two_non_connected_perms_canonical_labels(bot, top): r""" EXAMPLES:: sage: from surface_dynamics.flat_surfaces.separatrix_diagram import two_non_connected_perms_canonical_labels sage: two_non_connected_perms_canonical_labels([3,2,1,0],[0,1,2,3]) ([1, 0, 3, 2], [0, 1, 2, 3]) """ n = len(bot) cs_type_nb = {} # (bot,top) -> nb of them c_inv = [None] * n for c in perms_transitive_components([bot,top]): for i,j in enumerate(c): c_inv[j] = i cbot = [None]*len(c) ctop = [None]*len(c) for i in c: cbot[c_inv[i]] = c_inv[bot[i]] ctop[c_inv[i]] = c_inv[top[i]] (cbot,ctop), _ = perms_canonical_labels([cbot,ctop]) bt = (tuple(cbot),tuple(ctop)) if bt in cs_type_nb: cs_type_nb[bt] += 1 else: cs_type_nb[bt] = 1 shift = 0 bot = [] top = [] keys = cs_type_nb.keys() keys.sort() for key in keys: for _ in xrange(cs_type_nb[key]): bot.extend(shift+i for i in key[0]) top.extend(shift+i for i in key[1]) shift += len(key[0]) return bot,top
# main class
[docs]class SeparatrixDiagram(SageObject): r""" Separatrix diagram of oriented foliation. A separatrix diagram is a 2-tuple of permutations ``(bot,top)`` such that ``bot`` and ``top`` share the same number of cycles. bot (resp. top) has to be thought a bottom (resp. top) of a potential face as in the following:: -- bot --> ------------------- <-- top -- The order for bot and top is choosen in such a way that it cooresponds to the orientation of a face. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,2)(1,3,4)','(0,4)(2,1,3)') sage: print(s) (0,2)(1,3,4)-(0,4)(1,3,2) sage: print(s.stratum()) H_3(4) """ def __init__(self, data, top=None, check=True, copy=True): r""" TESTS:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1)(2,3,4)','(0,2,4)(1,3)') sage: s == loads(dumps(s)) True sage: SeparatrixDiagram(s) (0,1)(2,3,4)-(0,2,4)(1,3) sage: s == SeparatrixDiagram(s) True sage: SeparatrixDiagram(str(s)) (0,1)(2,3,4)-(0,2,4)(1,3) sage: s == SeparatrixDiagram(str(s)) True """ if copy: if top is None: if isinstance(data,SeparatrixDiagram): bot = data.bot() top = data.top() elif isinstance(data,(list,tuple)) and len(data) == 2: bot,top = data elif isinstance(data,str): bot,top = data.split('-') else: raise ValueError("the argument data is not valid") else: bot = data bot = init_perm(bot) top = init_perm(top) equalize_perms([bot, top]) else: bot = data self._bot = bot self._top = top n = len(bot) bot_seen = [True] * n top_seen = [True] * n bot_to_cycle = [None]*n top_to_cycle = [None]*n bot_cycles = [] top_cycles = [] for i in xrange(n): if bot_seen[i]: c=[] k = len(bot_cycles) while bot_seen[i]: bot_to_cycle[i] = k bot_seen[i] = False c.append(i) i = self._bot[i] bot_cycles.append(tuple(c)) k += 1 if top_seen[i]: c=[] k = len(top_cycles) while top_seen[i]: top_to_cycle[i] = k top_seen[i] = False c.append(i) i = self._top[i] top_cycles.append(tuple(c)) k += 1 self._bot_cycles = bot_cycles self._top_cycles = top_cycles self._bot_to_cycle = bot_to_cycle self._top_to_cycle = top_to_cycle if check: self._check() def _check(self): r""" Check that the data of self is valid, i.e. * self._bot, self._top are valid permutations * the number of cylces of bot and top are the same EXAMPLES:: sage: from surface_dynamics.all import * sage: c = SeparatrixDiagram('(0,1)(2,3)','(0,2,3,1)') #indirect doctest Traceback (most recent call last): ... ValueError: bot has 2 cylinders whereas top has 1 """ perm_check(self._bot) perm_check(self._top) p_bot = self.bot_cycle_tuples() p_top = self.top_cycle_tuples() if len(p_top) != len(p_bot): raise ValueError("bot has %d cylinders whereas top has %d"%(len(p_bot),len(p_top))) def _sage_input_(self, sib, coerced): r""" Sage input support. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,3,2)(1,4)','(0,1)(2,3,4)') sage: sage_input(s) SeparatrixDiagram('(0,3,2)(1,4)-(0,1)(2,3,4)') We can check that evaluating the code actually gives back the same object:: sage: t = eval(str(sage_input(s))) sage: t == s True """ return sib.name('SeparatrixDiagram')(str(self))
[docs] def to_directed_graph(self): r""" Return a graph that encodes this separatrix diagram. The vertices correspond to separatrix and the edges are of two types - 'b' neighboor corresponds to the right neighbors on the bottom permutation - 't' edges correspond to the neighbor of the top permutation EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,1)(2,3,4)','(0,3,2)(1,4)') sage: G = S.to_directed_graph(); G Looped multi-digraph on 5 vertices sage: G.vertices() [0, 1, 2, 3, 4] sage: G.edges() [(0, 1, 'b'), (0, 3, 't'), (1, 0, 'b'), (1, 4, 't'), (2, 0, 't'), (2, 3, 'b'), (3, 2, 't'), (3, 4, 'b'), (4, 1, 't'), (4, 2, 'b')] """ G = DiGraph(multiedges=True, loops=True) G.add_edges((i, self._top[i], 't') for i in xrange(self.nseps())) G.add_edges((i, self._bot[i], 'b') for i in xrange(self.nseps())) return G
def _repr_(self): r""" String representation of self EXAMPLES:: sage: from surface_dynamics.all import * sage: d = SeparatrixDiagram('(0,1)(2)','(0)(1,2)') sage: repr(d) #indirect doctest '(0,1)(2)-(0)(1,2)' """ return self.bot_cycle_string() + "-" + self.top_cycle_string() #TODO def _latex_(self): r""" Latex representation EXAMPLES:: sage: from surface_dynamics.all import * sage: print("to be done") to be done """ n = self._n if len(self.vertices_out().cycle_type()) == 1: v = self.vertices()[0] m = 360. / (2*n) d = dict([i,(v.index(i),v.index(-i))] for i in range(1,self._n+1)) s = "\\begin{tikzpicture}\n" for i,(vout,vin) in d.iteritems(): s += " \draw [-triangle 45] (0,0) -- (%f:0.8cm);\n" %(vout*m) s += " \draw (%f:0.8cm) -- (%f:1cm);\n" %(vout*m,vout*m) s += " \draw (%f:1cm) \n" %(vout*m) v1 = Integer(vout+vin)/2 if vout+vin > 2*n: v2 = v1 - n else: v2 = v1 + n d1 = min([abs(vout-v1), abs(vout-v1-2*n), abs(vout-v1+2*n)]) d2 = min([abs(vout-v2), abs(vout-v2-2*n), abs(vout-v2+2*n)]) if d1 < d2: vint = v1 d = d1 else: vint = v2 d = d2 dint = '%fcm' %(1.5+d/2.) ct1 = '%fcm' %(d/2.) if cyclic_direction(vout,vint,vin) == 1: ct2 = '%fcm' %(-d/2.) ct3 = '%fcm' %(d/2.) else: ct2 = '%fcm' %(d/2.) ct3 = '%fcm' %(-d/2.) s += " ..controls +(%f:%s) and +(%f:%s) ..\n" %(vout*m,ct1,(vint+n/2.)*m,ct2) s += " (%f:%s)\n" %(vint*m,dint) s += " ..controls +(%f:%s) and +(%f:%s) ..\n" %((vint+n/2.)*m,ct3,vin*m,ct1) s += " (%f:1cm);\n" %(vin*m) s += " \draw [-open triangle 45] (%f:1cm) -- (%f:0.6cm);\n" %(vin*m,vin*m) s += " \draw (%f:0.6cm) -- (0,0);\n" %(vin*m) s += "\\end{tikzpicture}" return s else: return "" # # Comparisons and canonic labels # def __eq__(self, other): r""" Equality test TESTS:: sage: from surface_dynamics.all import * sage: d1 = SeparatrixDiagram('(0)','(0)') sage: d2 = SeparatrixDiagram('(0,1)(2)','(0,1)(2)') sage: d3 = SeparatrixDiagram('(0,1)(2)','(0,2)(1)') sage: d1 == d1 and d2 == d2 and d3 == d3 True sage: d1 == d2 or d1 == d3 or d2 == d3 or d3 == d2 False """ return (isinstance(other, SeparatrixDiagram) and self._bot == other._bot and self._top == other._top) def __ne__(self,other): r""" Difference test TESTS:: sage: from surface_dynamics.all import * sage: d1 = SeparatrixDiagram('(0)','(0)') sage: d2 = SeparatrixDiagram('(0,1)(2)','(0,1)(2)') sage: d3 = SeparatrixDiagram('(0,1)(2)','(0,2)(1)') sage: d1 != d1 or d2 != d2 or d3 != d3 False sage: d1 != d2 and d1 != d3 and d2 != d3 and d3 != d2 True """ return not self.__eq__(other) def __cmp__(self,other): r""" Comparison TESTS:: sage: from surface_dynamics.all import * sage: s = ['(0,1,2)-(0,1,2)', ....: '(0,2,1)-(0,1,2)', ....: '(0,2,1)-(0,2,1)', ....: '(0)(1,2)-(0)(1,2)', ....: '(0)(1,2)-(0,1)(2)', ....: '(0)(1,2)-(0,2)(1)', ....: '(0,1)(2)-(0)(1,2)', ....: '(0,1)(2)-(0,1)(2)', ....: '(0,1)(2)-(0,2)(1)', ....: '(0,2)(1)-(0)(1,2)', ....: '(0,2)(1)-(0,1)(2)', ....: '(0,2)(1)-(0,2)(1)', ....: '(0)(1)(2)-(0)(1)(2)'] sage: s0 = map(SeparatrixDiagram,s) sage: s1 = s0[:] sage: for _ in xrange(10): ....: shuffle(s1) ....: assert sorted(s1) == s0 """ if not isinstance(other, SeparatrixDiagram): raise TypeError("only separatrix diagram can be compared to separatrix diagrams") test = cmp(self.nseps(), other.nseps()) if test: return test test = cmp(self.ncyls(),other.ncyls()) if test: return test test = cmp(self._bot_cycles, other._bot_cycles) if test: return test test = cmp(self._top_cycles, other._top_cycles) if test: return test return 0
[docs] def is_isomorphic(self, other, return_map=False): r""" Test whether self is isomorphic to other. EXAMPLES:: sage: from surface_dynamics.all import * sage: bot = [1,2,0,3] sage: top = [1,0,3,2] sage: s = SeparatrixDiagram(bot,top); s (0,1,2)(3)-(0,1)(2,3) sage: m = [3,0,1,2] sage: bot2 = [0]*4 sage: top2 = [0]*4 sage: for i in xrange(4): ....: bot2[m[i]] = m[bot[i]] ....: top2[m[i]] = m[top[i]] sage: ss = SeparatrixDiagram(bot2,top2) sage: s.is_isomorphic(ss) True sage: m = [1,2,0,3] sage: for i in xrange(4): ....: bot2[m[i]] = m[bot[i]] ....: top2[m[i]] = m[top[i]] sage: ss = SeparatrixDiagram(bot2,top2) sage: s.is_isomorphic(ss) True """ if not isinstance(other, SeparatrixDiagram): raise ValueError("other must be a separatrix diagram") return self._get_normal_perms() == other._get_normal_perms()
[docs] def relabel(self, perm, inplace=False): r""" Relabel self according to the permutation ``perm``. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0)(2,3,4)','(0,3,2)(1)') sage: s (0)(1)(2,3,4)-(0,3,2)(1)(4) sage: s.relabel(perm=[1,0,2,3,4]) (0)(1)(2,3,4)-(0)(1,3,2)(4) sage: s.relabel(perm=[1,2,0,3,4]) (0,3,4)(1)(2)-(0,1,3)(2)(4) """ n = self.degree() perm.extend(xrange(len(perm),n)) bot = [None] * self.degree() top = [None] * self.degree() for i in xrange(n): bot[perm[i]] = perm[self._bot[i]] top[perm[i]] = perm[self._top[i]] S = SeparatrixDiagram(bot,top) if inplace: self._bot = S._bot self._top = S._top self._bot_cycles = S._bot_cycles self._top_cycles = S._top_cycles self._bot_to_cycle = S._bot_to_cycle self._top_to_cycle = S._top_to_cycle return S
[docs] def canonical_label(self, inplace=False): r""" Relabel self according to some canonical labels. The result is cached. INPUT: - ``inplace`` - boolean (default: ``True``) - if True modify self if not return a new separatrix diagram. EXAMPLES:: sage: from surface_dynamics.all import * sage: bot = '(0,1,3,6,7,5)(2,4)(8)(9)' sage: top = '(0)(1,2)(3,4,5)(6,7,8,9)' sage: s = SeparatrixDiagram(bot,top) sage: s.canonical_label() (0)(1)(2,3,4,5,6,7)(8,9)-(0,1,2,3)(4,7,9)(5)(6,8) TESTS:: sage: from surface_dynamics.all import * sage: bot = [3,2,4,0,1] sage: top = [1,0,3,4,2] sage: b = [None]*5; t = [None]*5 sage: for p in Permutations([0,1,2,3,4]): ....: for i in xrange(5): ....: b[p[i]] = p[bot[i]] ....: t[p[i]] = p[top[i]] ....: s = SeparatrixDiagram(b,t) ....: print(s.canonical_label()) (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) ... (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) (0,1)(2,3,4)-(0,2,4)(1,3) """ try: sep = self._normal_form except AttributeError: bot, top = self._get_normal_perms() self._normal_form = SeparatrixDiagram(bot, top, check=False, copy=False) self._normal_form._normal_form = self._normal_form sep = self._normal_form if inplace: other = self._normal_form self._bot = other._bot self._top = other._top self._bot_cycles = other._bot_cycles self._top_cycles = other._top_cycles self._bot_to_cycle = other._bot_to_cycle self._top_to_cycle = other._top_to_cycle return return self._normal_form
[docs] def horizontal_symmetry(self): r""" Return the horizontal symmetric of this separatrix diagram. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1,2,3)(4,5)','(1,2,3)(4,5,0)') sage: sh = s.horizontal_symmetry() sage: print(sh) (0,5,4)(1,3,2)-(0,3,2,1)(4,5) sage: sh.cylinder_diagrams() [(0,2,4)-(1,5) (1,3,5)-(0,2,3,4)] sage: [c.horizontal_symmetry().canonical_label() for c in s.cylinder_diagrams()] [(0,2,4)-(1,5) (1,3,5)-(0,2,3,4)] """ return SeparatrixDiagram(tuple(t[::-1] for t in self._top_cycles), tuple(b[::-1] for b in self._bot_cycles))
[docs] def vertical_symmetry(self): r""" Return the vertical symmetric of this separatrix diagram. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1,2,3)(4,5)','(1,2,3)(4,5,0)') sage: sv = s.vertical_symmetry() sage: print(sv) (0,3,2,1)(4,5)-(0,5,4)(1,3,2) sage: sv.cylinder_diagrams() [(0,1,3,4)-(2,3,5) (2,5)-(0,1,4)] sage: [c.vertical_symmetry().canonical_label() for c in sv.cylinder_diagrams()] [(0,1,3,4)-(2,3,5) (2,5)-(0,1,4)] """ return SeparatrixDiagram(tuple(b[::-1] for b in self._bot_cycles), tuple(t[::-1] for t in self._top_cycles))
[docs] def inverse(self): r""" Return the inverse of this separatrix diagram, that is the one we obtain after application of `-Id`. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1,2)(3,4,5,6,7,8)-(0,1,3,5,7)(2,4,6,8)') sage: s.inverse() (0,1,3,5,7)(2,4,6,8)-(0,1,2)(3,4,5,6,7,8) sage: s.horizontal_symmetry().vertical_symmetry() == s.inverse() True sage: s.vertical_symmetry().horizontal_symmetry() == s.inverse() True """ return SeparatrixDiagram(tuple(self._top_cycles), tuple(self._bot_cycles))
def _get_normal_perms(self): r""" Returns the normal form of the permutations bot top defining self. Note that the result is cached. ALGORITHM: 1) compute the orbit of G = <bot,top> 2) for each of the connected component compute a normal form 3) sort the list of (normal_top, normal_bot) and concatenate them EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,3,2)(1,4)','(0,1)(2,3,4)') sage: s._get_normal_perms() ([1, 0, 3, 4, 2], [2, 3, 4, 1, 0]) sage: s = SeparatrixDiagram('(0,5,2)(1,3,4)(6,7,8)','(0,3,7,8)(1,5)(2,4,6)') sage: s._get_normal_perms() ([1, 2, 0, 4, 5, 3, 7, 8, 6], [1, 3, 5, 6, 8, 7, 0, 2, 4]) (0,5,2)(1,3,4)(6,7,8)-(0,3,7,8)(1,5)(2,4,6) sage: s.canonical_label() #indirect doctest (0,1,2)(3,4,5)(6,7,8)-(0,1,3,6)(2,5,7)(4,8) """ try: return self._normal_bot, self._normal_top except AttributeError: pass self._normal_bot, self._normal_top = two_non_connected_perms_canonical_labels(self._bot, self._top) return self._normal_bot, self._normal_top def _get_sym_perms(self): r""" Return the four symmetric version of self. """ n = len(self._top) bot, top = self._get_normal_perms() # compute the inverses ibot = [None]*n itop = [None]*n for i in range(n): ibot[bot[i]] = i itop[top[i]] = i hbot, htop = two_non_connected_perms_canonical_labels(itop, ibot) vbot, vtop = two_non_connected_perms_canonical_labels(ibot, itop) sbot, stop = two_non_connected_perms_canonical_labels(top, bot) return (bot,top),(hbot,htop),(vbot,vtop),(sbot,stop)
[docs] def symmetries(self): r""" Return a triple of boolean ``(horiz_sym, vert_sym, inverse_sym)`` which correspond to the symmetry of ``self``. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1,2)(3,4,5)-(0,1)(2,3,4,5)') sage: s.symmetries() (False, True, False) sage: s.horizontal_symmetry().is_isomorphic(s) False sage: s.vertical_symmetry().is_isomorphic(s) True sage: s.inverse().is_isomorphic(s) False sage: s = SeparatrixDiagram('(0,1,3,5)(2,4)-(0,4,1,5)(2,3)') sage: s.symmetries() (True, False, False) sage: s.horizontal_symmetry().is_isomorphic(s) True sage: s.vertical_symmetry().is_isomorphic(s) False sage: s.inverse().is_isomorphic(s) False sage: s = SeparatrixDiagram('(0,1,3,5)(2,4)-(0,3,2,1)(5,4)') sage: s.symmetries() (False, False, True) sage: s.horizontal_symmetry().is_isomorphic(s) False sage: s.vertical_symmetry().is_isomorphic(s) False sage: s.inverse().is_isomorphic(s) True sage: s = SeparatrixDiagram('(0)(1,2,3,4,5)-(0,1,2,5,3)(4)') sage: s.symmetries() (False, False, False) sage: s.horizontal_symmetry().is_isomorphic(s) False sage: s.vertical_symmetry().is_isomorphic(s) False sage: s.inverse().is_isomorphic(s) False TESTS:: sage: sym = lambda s: (s.horizontal_symmetry().is_isomorphic(s), ....: s.vertical_symmetry().is_isomorphic(s), ....: s.inverse().is_isomorphic(s)) sage: from surface_dynamics.flat_surfaces.separatrix_diagram import separatrix_diagram_iterator sage: for s in separatrix_diagram_iterator((2,2,2,2)): ....: assert s.symmetries() == sym(s) sage: for s in separatrix_diagram_iterator((4,2)): ....: assert s.symmetries() == sym(s) """ n = len(self._top) bot, top = self._get_normal_perms() # compute the inverses ibot = [None]*n itop = [None]*n for i in range(n): ibot[bot[i]] = i itop[top[i]] = i # horiz bot1, top1 = two_non_connected_perms_canonical_labels(itop, ibot) horiz_sym = bot == bot1 and top == top1 # vert bot1, top1 = two_non_connected_perms_canonical_labels(ibot, itop) vert_sym = bot == bot1 and top == top1 # inv if horiz_sym and vert_sym: # got the two inverse_sym = True elif horiz_sym^vert_sym: # got exactly one inverse_sym = False else: # none of them bot1, top1 = two_non_connected_perms_canonical_labels(top, bot) inverse_sym = bot == bot1 and top == top1 return (horiz_sym, vert_sym, inverse_sym)
[docs] def is_in_normal_form(self): r""" Test normal form Return True if self is in normal form and False otherwise. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1,2)(3,4,5)(6,7,8)','(0,3,7,8)(1,5)(2,4,6)') sage: s.is_in_normal_form() False sage: s.canonical_label().is_in_normal_form() True """ return (self._bot, self._top) == self._get_normal_perms()
# # Attributes access #
[docs] def degree(self): r""" Return the degree (number of separatrices) of this separatrix diagram. EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,1)(2,3)','(1,3,2)(0)') sage: S.degree() 4 """ return len(self._top)
nseps = degree
[docs] def ncyls(self): r""" Return the number of cylinders of this separatrix diagram. EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,1)(2,3)','(1,3,2)(0)') sage: S.ncyls() 2 """ return len(self._top_cycles)
[docs] def profile(self): r""" Return the angles around each vertex EXAMPLES:: sage: from surface_dynamics.all import * sage: a = AbelianStratum(1,1,0) sage: s = a.separatrix_diagrams()[0] sage: s.profile() [2, 2, 1] """ from sage.combinat.partition import Partition p = map(len,perm_cycle_tuples(self.outgoing_edges_perm(),singletons=True)) return Partition(sorted(p, reverse=True))
[docs] def euler_characteristic(self): r""" Return the Euler characteristic EXAMPLES:: sage: from surface_dynamics.all import * sage: SeparatrixDiagram('(0)','(0)').euler_characteristic() 0 sage: CylinderDiagram([((0,),(0,))]).euler_characteristic() 0 sage: CylinderDiagram([((0,1),(0,2)), ((2,),(1,))]).euler_characteristic() -2 """ p = self.profile() return Integer(len(p)-sum(p))
[docs] def genus(self): r""" Return the genus EXAMPLES:: sage: from surface_dynamics.all import * sage: CylinderDiagram([((0,),(0,))]).genus() 1 sage: CylinderDiagram([((0,1),(0,1))]).genus() 1 sage: CylinderDiagram([((0,1,2),(0,1,2))]).genus() 2 sage: CylinderDiagram([((0,1,2,3),(0,1,2,3))]).genus() 2 sage: CylinderDiagram([((0,1,2,3,4),(0,1,2,3,4))]).genus() 3 """ return Integer(1 - self.euler_characteristic()//2)
[docs] def stratum(self): r""" Return the Abelian stratum this separatrix diagram belongs to. EXAMPLES:: sage: from surface_dynamics.all import * sage: SeparatrixDiagram('(0)(1)(2)','(0)(1)(2)').stratum() H_1(0^3) sage: SeparatrixDiagram('(0,1)(2)','(0,2)(1)').stratum() H_2(2) """ from abelian_strata import AbelianStratum return AbelianStratum([i-1 for i in self.profile()])
[docs] def bot(self): r""" The bot permutation as a list from 0 to nseps-1 Warning: the output list should not be modified EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0)(1,2)','(0,1)(2)') sage: s.bot() [0, 2, 1] """ return list(self._bot)
[docs] def bot_perm(self): r""" Return the bot as a permutation (element of a group) EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0)(1,2)','(0,1)(2)') sage: s.bot_perm() (2,3) """ from sage.groups.perm_gps.permgroup_element import PermutationGroupElement return PermutationGroupElement([i+1 for i in self._bot])
[docs] def bot_orbit(self, i): r""" Return the orbit of i under the bot permutation EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1)(2,5)(3,4,6)','(0,1,5)(2,3,6)(4)') sage: s.bot_orbit(0) (0, 1) sage: s.bot_orbit(4) (3, 4, 6) """ return self._bot_cycles[self._bot_to_cycle[i]]
[docs] def bot_cycle_tuples(self): r""" Return the cycles of the bottom permutation as a list of tuples. EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,2)(3,4)','(0)(1,2,3)') sage: S.bot_cycle_tuples() [(0, 2), (1,), (3, 4)] """ return self._bot_cycles
[docs] def bot_cycle_string(self): r""" Return the cycles of the top permutation as a string. EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,2)(3,4)','(0)(1,2,3)') sage: S.bot_cycle_string() '(0,2)(1)(3,4)' """ return ''.join('(' + ','.join(map(str,c)) +')' for c in self.bot_cycle_tuples())
[docs] def top(self): r""" Return the top permutation of self as a list. Warning: the output should not be modified EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1,3)(2,4)','(0,4)(1,2,3)') sage: s.top() [4, 2, 3, 1, 0] """ return self._top
[docs] def top_perm(self): r""" Return the top as a permutation EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0)(1,2)','(1)(0,2)') sage: s.top_perm() (1,3) """ from sage.groups.perm_gps.permgroup_element import PermutationGroupElement return PermutationGroupElement([i+1 for i in self._top])
[docs] def top_orbit(self,i): r""" Return the orbit of ``i`` under the top permutation. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1)(2,5)(3,4,6)','(0,1,5)(2,3,6)(4)') sage: s.top_orbit(0) (0, 1, 5) sage: s.top_orbit(6) (2, 3, 6) """ return self._top_cycles[self._top_to_cycle[i]]
[docs] def top_cycle_tuples(self): r""" Return the cycle of the top permutation as a list of tuples. EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,2)(3,4)','(0)(1,2,3)') sage: S.top_cycle_tuples() [(0,), (1, 2, 3), (4,)] """ return self._top_cycles
[docs] def top_cycle_string(self): r""" Return the cycle of the top permutation as a string. EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,2)(3,4)','(0)(1,2,3)') sage: S.top_cycle_string() '(0)(1,2,3)(4)' """ return ''.join('(' + ','.join(map(str,c)) + ')' for c in self.top_cycle_tuples())
[docs] def automorphism_group(self, implementation='graph'): r""" Return the automorphism group of self. That is the centralizer of the permutations top and bottom. INPUT: - ``implementation`` - either graph or gap EXAMPLES:: sage: from surface_dynamics.all import * sage: S = SeparatrixDiagram('(0,3,1,4,2)','(0,1,2,3,4)') sage: G1 = S.automorphism_group(implementation='graph'); G1 Permutation Group with generators [(0,1,2,3,4)] sage: G2 = S.automorphism_group(implementation='gap'); G2 Subgroup of (Symmetric group of order 5! as a permutation group) generated by [(1,2,3,4,5), (1,4,2,5,3)] sage: G1.is_isomorphic(G2) True """ if implementation == 'graph': return self.to_directed_graph().automorphism_group(edge_labels=True) elif implementation == 'gap': from sage.groups.perm_gps.permgroup import PermutationGroup from sage.groups.perm_gps.permgroup_named import SymmetricGroup return SymmetricGroup(self.nseps()).centralizer(PermutationGroup([self.top_perm(),self.bot_perm()])) else: raise ValueError, "implementation should be either 'graph' or 'gap'"
[docs] def homological_dimension_of_cylinders(self): r""" Returns the dimension in the first homology group of the span of waist curves of horizontal cylinders. EXAMPLES:: sage: from surface_dynamics.all import * Homological dimension in the stratum H(2):: sage: c = CylinderDiagram('(0,1,2)-(0,1,2)') sage: c.stratum() H_2(2) sage: c.homological_dimension_of_cylinders() 1 sage: c = CylinderDiagram('(0,1)-(1,2) (2)-(0)') sage: c.stratum() H_2(2) sage: c.homological_dimension_of_cylinders() 2 Homological dimensions for cylinder diagrams in H(1,1):: sage: c = CylinderDiagram('(0,1,2,3)-(0,1,2,3)') sage: c.stratum() H_2(1^2) sage: c.homological_dimension_of_cylinders() 1 sage: c = CylinderDiagram('(0,1)-(0,2) (2,3)-(1,3)') sage: c.stratum() H_2(1^2) sage: c.homological_dimension_of_cylinders() 2 sage: c = CylinderDiagram('(0,1,2)-(1,2,3) (3)-(0)') sage: c.stratum() H_2(1^2) sage: c.homological_dimension_of_cylinders() 2 sage: c = CylinderDiagram('(0,1)-(2,3) (2)-(0) (3)-(1)') sage: c.stratum() H_2(1^2) sage: c.homological_dimension_of_cylinders() 2 """ return Integer(self.ncyls() - SeparatrixDiagram.to_directed_graph(self).connected_components_number() + 1)
# # Vertices of the separatrix diagram #
[docs] def outgoing_edges_perm(self): r""" Permutation associated to turning around vertices in trigonometric order. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1)','(2,3)') sage: s.outgoing_edges_perm() [1, 0, 3, 2] sage: s = SeparatrixDiagram('(0,5,2)(1,3,4)(6,7,8)','(0,3,7,8)(1,5)(2,4,6)') sage: s.outgoing_edges_perm() [7, 0, 8, 2, 5, 4, 3, 1, 6] """ return perm_compose_i(self._bot,self._top)
[docs] def incoming_edges_perm(self): r""" Permutation associated to turning around vertices in trigonometric order. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1)','(2,3)') sage: s.incoming_edges_perm() [1, 0, 3, 2] sage: s = SeparatrixDiagram('(0,5,2)(1,3,4)(6,7,8)','(0,3,7,8)(1,5)(2,4,6)') sage: s.incoming_edges_perm() [4, 2, 1, 8, 7, 3, 0, 6, 5] """ return perm_compose(self._top,self._bot)
# # to cylinder diagram #
[docs] def to_cylinder_diagram(self, pairing): r""" Return a cylinder diagram with the given pairing The pairing should be a list of 2-tuples of integer. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1,3)(2,4)','(0,2)(1,4,3)'); s (0,1,3)(2,4)-(0,2)(1,4,3) sage: s.to_cylinder_diagram([(0,0),(1,1)]) (0,1,3)-(0,2) (2,4)-(1,4,3) sage: s.to_cylinder_diagram([(1,1),(0,0)]) (0,1,3)-(0,2) (2,4)-(1,4,3) sage: s.to_cylinder_diagram([(0,1),(1,0)]) (0,1,3)-(1,4,3) (2,4)-(0,2) sage: s.to_cylinder_diagram([(1,0),(0,1)]) (0,1,3)-(1,4,3) (2,4)-(0,2) """ from copy import copy other = copy(self) other.__class__ = CylinderDiagram bots = self.bot_cycle_tuples() tops = self.top_cycle_tuples() other._bot_to_cyl = [None]*self.nseps() other._top_to_cyl = [None]*self.nseps() for i in xrange(len(pairing)): b = bots[pairing[i][0]] t = tops[pairing[i][1]] cyl = (b[0],t[0]) for j in b: other._bot_to_cyl[j] = cyl for j in t: other._top_to_cyl[j] = cyl return other
[docs] def cylinder_diagram_iterator(self,connected=True,up_to_isomorphism=True): r""" Construct all cylinder diagrams from given separatrix diagram (i.e. a pair of permutations). INPUT: - ``connected`` - boolean (default: True) - if true, returns only connected cylinder diagrams. - ``up_to_isomorphism`` - boolean (default: True) - take care of isomorphism problem. It is memory efficient and probably faster to set this option to ``False``. EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1)(2,3)(4,5)','(1,2)(3,4)(5,0)') sage: for c in s.cylinder_diagram_iterator(): print(c) (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) (0,3)-(0,5) (1,2)-(1,4) (4,5)-(2,3) (0,5)-(3,4) (1,4)-(0,2) (2,3)-(1,5) sage: G = s.automorphism_group(); G Permutation Group with generators [(0,1)(2,5)(3,4), (0,2,4)(1,3,5)] sage: G.order() 6 sage: sum(1 for _ in s.cylinder_diagram_iterator(up_to_isomorphism=False)) 6 Here is an example with some symmetry:: sage: s = SeparatrixDiagram('(0)(1)(2,3)(4,5,6)-(0,1)(2,4)(3,5)(6)') sage: s.vertical_symmetry().canonical_label() == s True sage: s.cylinder_diagrams() [(0,1)-(0,4) (2,3,4)-(5,6) (5)-(2) (6)-(1,3), (0,1)-(4) (2,4,3)-(5,6) (5)-(0,2) (6)-(1,3), (0,3,1)-(0,6) (2,6)-(4,5) (4)-(1) (5)-(2,3)] """ cbot = self.bot_cycle_tuples() ctop0 = self.top_cycle_tuples() n = self.nseps() connected = not connected if up_to_isomorphism: # note: here we should only consider symmetries of the cylinder diagrams # only when this underlying separatrix diagrams has some. But the # canonical labels of cylinder diagrams and separatrix diagrams are # not compatible!! s = set([]) hsym, vsym, isym = self.symmetries() for ctop in itertools.permutations(ctop0): c = CylinderDiagram(zip(cbot,ctop),check=False) c.canonical_label(inplace=True) if c in s: continue cc = [c] if hsym: c1 = c.horizontal_symmetry() c1.canonical_label(inplace=True) cc.append(c1) if vsym: c1 = c.vertical_symmetry() c1.canonical_label(inplace=True) cc.append(c1) if isym: c1 = c.inverse() c1.canonical_label(inplace=True) cc.append(c1) s.update(cc) if (connected or c.is_connected()) and c.smallest_integer_lengths(): yield min(cc) else: for ctop in itertools.permutations(ctop0): c = CylinderDiagram(zip(cbot,ctop),check=False) if (connected or c.is_connected()) and c.smallest_integer_lengths(): yield c
[docs] def cylinder_diagrams(self, connected=True,up_to_isomorphism=True): r""" Return the list of cylinder diagrams associated to this separatrix diagram. We warn that the cylinder diagram may be renumeroted in the output list (in order to prevent repetitions). If you care about numerotation the option ``up_to_isomorphism`` should be set to False. INPUT: - ``connected`` - boolean (default: True) - ``up_to_isomorphism`` - boolean (default: True) EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0)(1)(2)','(0)(1)(2)') sage: for c in s.cylinder_diagrams(connected=True): print(c) (0)-(2) (1)-(0) (2)-(1) sage: for c in s.cylinder_diagrams(connected=False): print(c) (0)-(0) (1)-(1) (2)-(2) (0)-(1) (1)-(0) (2)-(2) (0)-(2) (1)-(0) (2)-(1) sage: s = SeparatrixDiagram('(0,1)(2)','(0)(1,2)') sage: for c in s.cylinder_diagrams(): print(c) (0,1)-(0,2) (2)-(1) In the example below, there is no isomorphism problem for the cylinder diagram generation as the separatrix diagram admit no automorphism:: sage: s = SeparatrixDiagram('(0,3)(1,4,5)(2)','(0)(1,2)(3,4,5)') sage: for c in s.cylinder_diagrams(): print(c) (0,1,2)-(0,1,5) (3,5)-(2,4) (4)-(3) (0,2,3)-(2,5) (1,4)-(0,1,3) (5)-(4) (0,3,1)-(5) (2,5)-(3,4) (4)-(0,2,1) sage: for c in s.cylinder_diagrams(up_to_isomorphism=False): print(c) (0,3)-(1,2) (1,4,5)-(0) (2)-(3,4,5) (0,3)-(1,2) (1,4,5)-(3,4,5) (2)-(0) (0,3)-(3,4,5) (1,4,5)-(1,2) (2)-(0) sage: s.automorphism_group() Permutation Group with generators [()] """ return sorted(self.cylinder_diagram_iterator( connected=connected, up_to_isomorphism=up_to_isomorphism))
[docs]def cyclic_direction(x,y,z): r""" Returns 1 or -1 depending on the cyclic ordering of (x,y,z) TESTS:: sage: from surface_dynamics.flat_surfaces.separatrix_diagram import cyclic_direction sage: cyclic_direction(0,1,2) 1 sage: cyclic_direction(1,2,0) 1 sage: cyclic_direction(2,0,1) 1 sage: cyclic_direction(2,1,0) -1 sage: cyclic_direction(1,0,2) -1 sage: cyclic_direction(0,2,1) -1 """ if (x < y < z) or (y < z < x) or (z < x < y): return 1 else: return -1
# iterators
[docs]def separatrix_diagram_fast_iterator(profile,ncyls=None): r""" Iterator over separatrix diagram with given ``profile`` Return a list of 3-tuples ``[bot, top, s]`` where ``bot`` and ``top`` are list on 0, ..., nseps-1 that corresponds to a separatrix diagram with profile ``profile`` while ``s`` is the element conjugacy class corresponding to the profile which equals ``bot * top``. If ncyls is not None, it should be a list of integers from which the number of cylinders is considered. Warning: each isomorphism class of separatrix diagram is output more than once in general. If you want a unique representative in each isomorphism class you may consider the method separatrix_diagram_iterator instead. EXAMPLES:: sage: from surface_dynamics.all import * sage: from surface_dynamics.flat_surfaces.separatrix_diagram import separatrix_diagram_fast_iterator sage: for s in separatrix_diagram_fast_iterator([3]): print(s) ([0, 2, 1], [1, 0, 2], [(0, 1, 2)]) ([1, 2, 0], [1, 2, 0], [(0, 2, 1)]) ([2, 1, 0], [1, 0, 2], [(0, 2, 1)]) sage: for s in separatrix_diagram_fast_iterator([2,2]): print(s) ([0, 2, 3, 1], [1, 2, 0, 3], [(0, 1), (2, 3)]) ([0, 1, 3, 2], [1, 0, 2, 3], [(0, 1), (2, 3)]) ([1, 2, 3, 0], [1, 2, 3, 0], [(0, 2), (1, 3)]) ([1, 3, 2, 0], [1, 2, 0, 3], [(0, 2), (1, 3)]) ([3, 2, 1, 0], [1, 0, 3, 2], [(0, 2), (1, 3)]) ([3, 1, 0, 2], [1, 2, 0, 3], [(0, 3), (1, 2)]) ([2, 3, 0, 1], [1, 0, 3, 2], [(0, 3), (1, 2)]) """ from sage.combinat.partition import Partition,Partitions from sage.groups.perm_gps.symgp_conjugacy_class import conjugacy_class_iterator part = Partition(profile) n = sum(part) d = (n+len(part))//2 # the maximum number of cylinders is known # to be g+s-1 from a theorem of Y. Naveh res = set([]) tops = [[]] if ncyls is None: ncyls = range(1,d+1) else: if isinstance(ncyls,(int,long,Integer)): ncyls = set([int(ncyls)]) else: ncyls = set(map(int,ncyls)) for i in ncyls: if i < 1 or i > d: raise ValueError("%d is not possible as number of cylinders"%i) # build the list of admissible tops up to conjugacy class for k in xrange(1,d+1): tops.append([]) if k in ncyls: for p in Partitions(n,length=k): tops[-1].append((canonical_perm(p),canonical_perm_i(p))) for s in conjugacy_class_iterator(part,range(n)): for k in xrange(len(tops)): for top,top_i in tops[k]: bot = range(len(top_i)) for cycle in s: for i in xrange(len(cycle)-1): bot[cycle[i]] = top_i[cycle[i+1]] bot[cycle[-1]] = top_i[cycle[0]] seen = [True]*len(bot) nb_cycles = 0 for i in xrange(len(bot)): if seen[i]: seen[i] = False nb_cycles += 1 if nb_cycles > k: break j = bot[i] while seen[j]: seen[j] = False j = bot[j] if nb_cycles == k: yield (bot,top,s)
[docs]def separatrix_diagram_iterator(profile, ncyls=None): r""" Iterator over separatrix diagram with given ``profile`` and number of cylinders. Warning: to prevent isomorphism class to be output twice the function implement a cache mechanism. If you intend to iterate through a huge class of separatrix_diagram and do not care about isomorphism problem use separatrix_diagram_fast_iterator instead. EXAMPLES:: sage: from surface_dynamics.all import * sage: from surface_dynamics.flat_surfaces.separatrix_diagram import separatrix_diagram_iterator sage: for s in separatrix_diagram_iterator([1,1]): print(s) (0,1)-(0,1) (0)(1)-(0)(1) sage: for s in separatrix_diagram_iterator([3]): print(s) (0)(1,2)-(0,1)(2) (0,1,2)-(0,1,2) sage: for s in separatrix_diagram_iterator([2,2]): print(s) (0)(1,2,3)-(0,1,2)(3) (0)(1)(2,3)-(0,1)(2)(3) (0,1,2,3)-(0,1,2,3) (0,1)(2,3)-(0,2)(1,3) sage: sum(1 for s in separatrix_diagram_iterator([3,2,2])) 64 """ res = set([]) for bot,top,_ in separatrix_diagram_fast_iterator(profile,ncyls): bot, top = two_non_connected_perms_canonical_labels(bot, top) s_perm = tuple(bot+top) if s_perm not in res: s = SeparatrixDiagram(bot, top, check=False, copy=False) syms = s._get_sym_perms() s = SeparatrixDiagram(*min(syms), check=False, copy=False) res.update(tuple(bot+top) for bot,top in syms) yield s
# # Cylinder diagram # (or completely periodic decomposition) #
[docs]def string_to_cycle(s): r""" TESTS:: sage: from surface_dynamics.flat_surfaces.separatrix_diagram import string_to_cycle sage: string_to_cycle('(3,1,2)') (3, 1, 2) """ if len(s) < 2: raise ValueError("Wrong syntax") if s[0] != '(': raise ValueError("A cycle string should start with an opening paranthesis") if s[-1] != ')': raise ValueError("A cycle string should end with a closing paranthesis") return tuple(int(i) for i in s[1:-1].split(','))
[docs]def orientation_cover(alpha,phi,a,verbose=0): r""" Build the cylinder diagram of Abelian differentials that double covers it. A quadratic differrential separatrix diagram is given by three permutations - sigma: the permutation of 1/2-separatrices around vertices - alpha: the permutation of 1/2-separatrices that describe the separatrices (it is a fixed point free involution) - phi: the permutation of 1/2-separatrices that describe the cycles. INPUT: - ``alpha`` -- permutation - ``phi`` -- permutation - ``a`` -- number of half separatrices EXAMPLES:: sage: from surface_dynamics.all import * sage: from surface_dynamics.flat_surfaces.separatrix_diagram import orientation_cover sage: alpha = [3, 2, 1, 0, 5, 4, 7, 6] sage: phi = [3, 1, 0, 2, 5, 4, 7, 6] sage: orientation_cover(alpha,phi,3) (0,2)-(0,1) (1)-(2) """ if verbose: print(" orientation cover") cyls = [] todo = [True]*a for i in xrange(a): if todo[i]: todo[i] = False b = [i] if alpha[i] >= a: t = [i] else: t = [alpha[i]] if verbose: print(" top from %d, bot from %d" % (i, t[0])) j = phi[i] if j >= a: j = phi[j] while j != i: todo[j] = False b.append(j) if alpha[j] >= a: t.append(j) else: t.append(alpha[j]) if verbose: print(" add %d to bot, add %d to top" % (j, b[-1])) j = phi[j] if j >= a: j = phi[j] cyls.append((b,t)) return CylinderDiagram(cyls)
#TODO: do something less stupid for symmetries
[docs]def hyperelliptic_cylinder_diagram_iterator(a,verbose=False): r""" Return an iterator over cylinder diagrams of Abelian differentials that double covers Q((a-2), -1^(a+2)). The generator is up to isomorphism. TODO: - An optimization could be obtained by considering the generation of k-subsets of {1,...,n} up to the cyclic symmetry of the tree. INPUT: - ``a`` - integer - angle of the conical singularity of the quadratic differential. - ``verbose`` - integer (default: 0) - output various information during the iteration (mainly for debug). EXAMPLES:: sage: from surface_dynamics.all import * sage: from surface_dynamics.flat_surfaces.separatrix_diagram import hyperelliptic_cylinder_diagram_iterator sage: it = hyperelliptic_cylinder_diagram_iterator(3) sage: c = it.next(); c (0,1)-(0,2) (2)-(1) sage: c.stratum_component() H_2(2)^hyp sage: hyp = AbelianStratum(2,2).hyperelliptic_component() sage: all(c.stratum_component() == hyp for c in hyperelliptic_cylinder_diagram_iterator(6)) True """ from surface_dynamics.misc.plane_tree import admissible_plane_tree_iterator from sage.combinat.gray_codes import combinations cyl_diags = set([]) if verbose is True: verbose=1 aa = a//2 B = [False]*(2*a+2) # open loops indicator # if B[k] is not False, it is where loop k starts sigma = range(1,a) + [0] + range(a,2*a+2) for t,n,l in admissible_plane_tree_iterator(a): # Build the initial tree L = [] p = 2*n-a # the number of poles ll = 0 # leaf counter s = 0 # 1/2-separatrix counter sp = a # pole counter alpha = [None]*(2*a+2) # edge permutation phi = [None]*(2*a+2) # face permutation if verbose: print("n = %d, l = %d, p = %d" % (n, l, p)) print("t =", t) for k in xrange(1,n+2): if verbose: print(" k = %d" % k) for kk in xrange(t[k-1],t[k]-1,-1): # close current loops if B[kk] is not False: if verbose: print(" close loop from %d to %d" % (B[kk], s)) alpha[B[kk]] = s alpha[s] = B[kk] phi[s] = (B[kk]-1)%a phi[B[kk]] = (s-1)%a s += 1 if verbose > 2: print(" alpha =", alpha) print(" phi =", phi) if ll < p and t[k] >= t[k+1]: L.append(s) # store the leaf # t[k] is a pole if verbose: print(" pole at %d" % s) alpha[s] = sp alpha[sp] = s phi[s] = sp phi[sp] = (s-1)%a s += 1 sp += 1 ll += 1 B[t[k]] = False if verbose > 2: print(" alpha =", alpha) print(" phi =", phi) elif k != n+1: # not at the end -> open a loop if t[k] >= t[k+1]: # store the leaf L.append(s) if verbose: print(" open loop at %d" % s) B[t[k]] = s s += 1 if verbose > 2: print(" alpha =", alpha) print(" phi =", phi) if verbose: print(" tree is over") print(" alpha =", alpha) print(" phi =", phi) for pp in xrange(a+p,2*a+2,2): if verbose: print(" paired poles (%d,%d)" % (pp, pp+1)) alpha[pp] = phi[pp] = pp+1 alpha[pp+1] = phi[pp+1] = pp if verbose > 1: print(" alpha =", alpha) print(" phi =", phi) assert len(L) == l, "This may not happen" # yield the canonical sepx. diag if verbose: print(" =" * (3*a+7)) print(" sigma =", sigma) print(" alpha =", alpha) print(" phi =", phi) print(" =" * (3*a+7)) c = orientation_cover(alpha,phi,a,verbose=verbose) c.canonical_label(inplace=True) if c not in cyl_diags: c_sym = [c] cc = c.horizontal_symmetry() cc.canonical_label(inplace=True) c_sym.append(cc) cc = c.vertical_symmetry() cc.canonical_label(inplace=True) c_sym.append(cc) cyl_diags.update(c_sym) yield c # Make the poles vary among the leaves #TODO: optimization when tree has nontrivial cyclic symmetry if p != 0 and p != l: if verbose: print(" start revolving door(%d,%d)" % (l, p)) print(" leaves are at separatrices", L) for i,j in combinations(l,p): i = L[i] j = L[j] if verbose > 1: print(" revolve i=%d j=%d" % (i, j)) a_i = alpha[i] a_j = alpha[j] s_i = sigma[i] s_a_j = sigma[a_j] ss_i = phi[alpha[i]] # sigma^-1(i) ss_j = phi[alpha[j]] # sigma^-1(j) a_s_i = alpha[s_i] a_s_a_j = alpha[s_a_j] assert sigma[j] == a_j, "sigma[%d] = %d != alpha[%d]"%(j,sigma[j],a_j) assert phi[i] == a_i, "phi[%d] != alpha[i]"%(i,i) assert phi[a_s_i] == i, "phi[%d] != %d"%(a_s_i,i) assert phi[j] == j, "phi[%d] + %d"%(j,j) assert phi[a_s_a_j] == a_j, "phi[%d] != alpha[%d]"%(a_s_a_j,j) alpha[i] = a_j alpha[a_j] = i alpha[j] = a_i alpha[a_i] = j sigma[i] = a_j # old_sigma[j] sigma[a_j] = s_i # old_sigma[i] sigma[j] = s_a_j # old_sigma[a_j] phi[i] = i # old_phi[a_s_i] phi[j] = a_i # old_phi[i] if s_i != j: # and a_s_i == a_j phi[a_s_i] = a_j # old_phi[a_s_a_j] phi[a_i] = ss_j # old_phi[a_j] else: phi[a_i] = a_j if s_a_j != i: phi[a_j] = ss_i # old_phi[a_i] phi[a_s_a_j] = j # old_phi[j] else: phi[a_j] = j if verbose: print(" =" * (3*a+7)) print(" sigma =", sigma) print(" alpha =", alpha) print(" phi =", phi) print(" =" * (3*a+7)) for i in xrange(2*a+2): ii = phi[alpha[sigma[i]]] assert ii == i, "f_a_s(%d) == %d != %d"%(i,ii,i) for i in xrange(a,2*a+2): assert sigma[i] == i, "sigma[%d] = %d != %d"%(i,sigma[i],i) c = orientation_cover(alpha,phi,a,verbose=verbose) c.canonical_label(inplace=True) if c not in cyl_diags: c_sym = [c] cc = c.horizontal_symmetry() cc.canonical_label(inplace=True) c_sym.append(cc) cc = c.vertical_symmetry() cc.canonical_label(inplace=True) c_sym.append(cc) cyl_diags.update(c_sym) yield c # reinitialize sigma sigma = range(1,a) + [0] + range(a,2*a+2)
[docs]class CylinderDiagram(SeparatrixDiagram): r""" Separatrix diagram with pairing. Each cylinder is stored as a couple (bot,top) for which the orientation is as follows:: +--------------------+ | <-- top -- | | | | | | -- bot --> | +--------------------+ INPUT: - ``data`` - list of 2-tuples - matching of bottom-top pairs EXAMPLES:: sage: from surface_dynamics.all import * We first build the simplest cylinder diagram which corresponds to a torus:: sage: CylinderDiagram([((0,),(0,))]) (0)-(0) The same initialized from a string:: sage: CylinderDiagram('(0)-(0)') (0)-(0) The following initialize a cylinder diagram with two cylinder which gives a surface of genus 2 with one singularity of degree 2:: sage: CylinderDiagram([((0,1),(0,2)),((2,),(1,))]) (0,1)-(0,2) (2)-(1) ALGORITHM: A cylinder is represented by a couple (i,j) where i is the min in bot and j is the min in top. The data _top_to_cyl and _bot_to_cyl corresponds to the association of a separatrix to the corresponding 2-tuple. The twist coordinate correspond to the shift betwenn those two indices. """ def __init__(self, data, check=True): r""" TESTS:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram([((0,),(0,))]) sage: CylinderDiagram(str(c)) == c True sage: loads(dumps(c)) == c True """ bot = [] top = [] if isinstance(data,str): data = [(string_to_cycle(b),string_to_cycle(t)) for b,t in (w.split('-') for w in data.split(' '))] for b,t in data: bot.append(tuple(b)) top.append(tuple(t)) SeparatrixDiagram.__init__(self,tuple(bot),tuple(top)) b2c = [None] * self.nseps() # bot separatrix -> cylinder (bot_min_index, top_min_index) t2c = [None] * self.nseps() # top separatrix -> cylinder (bot_min_index, top_min_index) for b,t in data: cyl = (min(b),min(t)) for j in b: b2c[j] = cyl for j in t: t2c[j] = cyl self._bot_to_cyl = b2c self._top_to_cyl = t2c #from sage.misc.latex import latex #if latex.has_file("tikz.sty"): #latex.add_to_preamble('\\usepackage{tikz}') #latex.add_to_preamble('\\usetikzlibrary{arrows}') #latex.add_to_jsmath_avoid_list('\\begin{tikzpicture}') def __hash__(self): r""" Hash value: This is bad since we can modify it inplace!! """ return hash(tuple(self._bot_to_cyl + self._top_to_cyl + self._bot_cycles + self._top_cycles)) def _repr_(self): r""" String representation TESTS:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram([((0,1),(1,2)),((2,),(0,))]) sage: repr(c) #indirect doctest '(0,1)-(1,2) (2)-(0)' """ l = [] for b,t in self.cylinders(): l.append('(' + ','.join(map(str,b)) + ')-(' + ','.join(map(str,t)) + ')') return ' '.join(l) def __cmp__(self,other): r""" Comparison TESTS:: sage: from surface_dynamics.all import * sage: C = AbelianStratum(4).cylinder_diagrams() sage: for c in C: ....: assert sum(1 for cc in C if cmp(c,cc) == 0) == 1 sage: for c1 in C: ....: for c2 in C: ....: if c1 != c2: ....: assert ((c1 < c2) is False) or ((c2 < c1) is False) ....: assert ((c1 > c2) is False) or ((c2 > c1) is False) """ if not isinstance(other, CylinderDiagram): raise ValueError test = SeparatrixDiagram.__cmp__(self,other) if test: return test test = cmp(self._bot_to_cyl,other._bot_to_cyl) if test: return test test = cmp(self._top_to_cyl,other._top_to_cyl) if test: return test return 0 # # access to attribute #
[docs] def to_directed_graph(self): r""" Return a labeled directed graph that encodes the cylinder diagram. EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,1,5)-(2,5) (2)-(0,1,3) (3,4)-(4)'); c (0,1,5)-(2,5) (2)-(0,1,3) (3,4)-(4) sage: G = c.to_directed_graph(); G Looped multi-digraph on 6 vertices sage: G.edges() [(0, 1, 'b'), (0, 1, 't'), (0, 2, 'c'), (0, 5, 'c'), (1, 2, 'c'), (1, 3, 't'), (1, 5, 'b'), (1, 5, 'c'), (2, 0, 'c'), (2, 1, 'c'), (2, 2, 'b'), (2, 3, 'c'), (2, 5, 't'), (3, 0, 't'), (3, 4, 'b'), (3, 4, 'c'), (4, 3, 'b'), (4, 4, 'c'), (4, 4, 't'), (5, 0, 'b'), (5, 2, 'c'), (5, 2, 't'), (5, 5, 'c')] """ G = SeparatrixDiagram.to_directed_graph(self) for cb,ct in self.cylinders(): for i in cb: for j in ct: G.add_edge(i,j,'c') return G
[docs] def canonical_label(self, inplace=False, return_map=False): r""" Return a cylinder diagram with canonical labels. EXAMPLES:: sage: from surface_dynamics.all import * sage: import itertools sage: for p in itertools.permutations([0,1,2,3]): ....: c = CylinderDiagram([((p[0],),(p[1],)),((p[1],p[2]),(p[0],p[3])),((p[3],),(p[2],))]) ....: cc,m = c.canonical_label(return_map=True) ....: b = c.bot() ; t = c.top() ....: bb = cc.bot(); tt = cc.top() ....: print(cc) ....: print(all(bb[m[i]] == m[b[i]] for i in xrange(c.nseps()))) ....: print(all(tt[m[i]] == m[t[i]] for i in xrange(c.nseps()))) (0,1)-(2,3) (2)-(1) (3)-(0) True True (0,1)-(2,3) (2)-(1) (3)-(0) True True (0,1)-(2,3) (2)-(1) (3)-(0) True True (0,1)-(2,3) (2)-(1) (3)-(0) True True (0,1)-(2,3) (2)-(1) (3)-(0) True True (0,1)-(2,3) (2)-(1) (3)-(0) True True (0,1)-(2,3) (2)-(1) (3)-(0) True True (0,1)-(2,3) (2)-(1) (3)-(0) True True ... (0,1)-(2,3) (2)-(1) (3)-(0) True True sage: import itertools sage: for p in itertools.permutations([0,1,2,3,4,5]): ....: c1 = ((p[0],p[4]),(p[0],p[3])) ....: c2 = ((p[1],p[3]),(p[1],p[5])) ....: c3 = ((p[2],p[5]),(p[2],p[4])) ....: c = CylinderDiagram([c1,c2,c3]) ....: cc,m = c.canonical_label(return_map=True) ....: b = c.bot() ; t = c.top() ....: bb = cc.bot(); tt = cc.top() ....: print(cc) ....: print(all(bb[m[i]] == m[b[i]] for i in xrange(c.nseps()))) ....: print(all(tt[m[i]] == m[t[i]] for i in xrange(c.nseps()))) (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) True True (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) True True (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) True True (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) True True (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) True True ... (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) True True (0,5)-(0,4) (1,4)-(1,3) (2,3)-(2,5) True True TESTS:: sage: c = CylinderDiagram('(0,1)-(0,2) (3,5,4)-(1,4,6) (2,6)-(3,5)') sage: c is c.canonical_label() False sage: c.canonical_label() is c.canonical_label() True sage: c.canonical_label().canonical_label() is c.canonical_label() True """ if not hasattr(self,'_normal_form'): G = self.to_directed_graph() _,m = G.canonical_label(certificate=True,edge_labels=True) # m = [m[i] for i in xrange(self.nseps())] # GG the new digraph # m from the digraph to its canonic labels cyls = [] for b,t in self.cylinders(): cyls.append((tuple(m[i] for i in b),tuple(m[i] for i in t))) self._normal_form = CylinderDiagram(cyls,check=False) self._normal_labels = m self._normal_form._normal_form = self._normal_form self._normal_form._normal_labels = range(self.nseps()) if inplace: self.__dict__ = self._normal_form.__dict__ if return_map: return self._normal_form, self._normal_labels elif not inplace: return self._normal_form
[docs] def separatrix_diagram(self): r""" Return the underlying separatrix diagram EXAMPLES:: sage: from surface_dynamics.all import * sage: s = SeparatrixDiagram('(0,1)(2,3,4)','(0,3)(1,4,2)'); s (0,1)(2,3,4)-(0,3)(1,4,2) sage: c = s.to_cylinder_diagram([(0,1),(1,0)]); c (0,1)-(1,4,2) (2,3,4)-(0,3) sage: c.separatrix_diagram() == s True """ return SeparatrixDiagram(self._bot,self._top,check=False)
[docs] def lengths_polytope(self, heights): r""" Return the rational polyhedron corresponding to the set of length with the given fixed heights. -> one can obtain ehrhard series for each of them! It tells us that we have a nice asymptotics... and the asymptotics is simply given by the volume of this polytope (up to the ignored twists parameters)! """ from sage.geometry.polyhedron.constructor import Polyhedron from sage.rings.integer_ring import ZZ n = self.nseps() k = self.ncyls() ieqs = [] # lengths are positive (here non-negative) e = [ZZ.zero()] * (n+k+1) for i in range(n+k): e[i+1] = ZZ.one() ieqs.append(e[:]) e[i+1] = ZZ.zero() area = [-1] + [None]*n twist = [ZZ.zero()] * (n+k+1) eqns = [] for i,(bot,top) in enumerate(self.cylinders()): # for each cylinder, length top = length bot e = [ZZ.zero()] * (n+1) for i in set(bot).difference(top): e[i+1] = ZZ.one() for i in set(top).difference(bot): e[i+1] = -ZZ.one() eqns.append(e) # the twist must be less than the width # the area should sum up to the area of the surface area[i+1] = heights[i] eqns.append(area) return Polyhedron(ieqs=ieqs, eqns=eqns)
[docs] def cylinders(self): r""" Cylinders of self EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,2,4)-(1,3,5) (1,5)-(0) (3)-(2,4)') sage: c (0,2,4)-(1,3,5) (1,5)-(0) (3)-(2,4) sage: c.cylinders() [((0, 2, 4), (1, 3, 5)), ((1, 5), (0,)), ((3,), (2, 4))] """ return [(b,self.top_orbit(self._bot_to_cyl[b[0]][1])) for b in self.bot_cycle_tuples()]
[docs] def bot_to_cyl(self, j): r""" Return the cylinder above the separatrix j EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,2,4)-(1,3,5) (1,5)-(0) (3)-(2,4)') sage: c (0,2,4)-(1,3,5) (1,5)-(0) (3)-(2,4) sage: c.bot_to_cyl(0) ((0, 2, 4), (1, 3, 5)) sage: c.bot_to_cyl(1) ((1, 5), (0,)) sage: c.bot_to_cyl(3) ((3,), (2, 4)) """ jb,jt = self._bot_to_cyl[j] return self.bot_orbit(jb), self.top_orbit(jt)
[docs] def top_to_cyl(self, j): r""" Return the cylinder below the separatrix j EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,2,4)-(1,3,5) (1,5)-(0) (3)-(2,4)') sage: c.top_to_cyl(0) ((1, 5), (0,)) sage: c.top_to_cyl(2) ((3,), (2, 4)) """ jb,jt = self._top_to_cyl[j] return self.bot_orbit(jb), self.top_orbit(jt)
# # properties #
[docs] def is_connected(self): r""" Check the connectedness of this cylinder diagram. TESTS:: sage: from surface_dynamics.all import * sage: CylinderDiagram('(0)-(1) (1)-(0)').is_connected() True sage: CylinderDiagram('(0,1)-(0) (2)-(1,2)').is_connected() True sage: CylinderDiagram('(0)-(0) (1)-(1)').is_connected() False sage: CylinderDiagram('(0,1)-(3) (2)-(2) (3)-(0,1)').is_connected() False """ from sage.graphs.graph import Graph G = Graph(multiedges=True, loops=True) for b,t in self.cylinders(): G.add_edges((b[0],b[j]) for j in xrange(1,len(b))) G.add_edges((t[0],t[j]) for j in xrange(1,len(t))) G.add_edge(b[0],t[0]) return G.num_verts() == self.nseps() and G.is_connected()
# # symmetries #
[docs] def inverse(self): r""" Return the inverse cylinder diagram The inverse of a cylinder diagram is the cylinder diagram in which all cylinders have been reversed. It corresponds to the multiplication by `-1` on the underlying Abelian differential. Combinatorially the operation is b0-t0 ... bk-tk becomes t0-b0 ... tk-bk EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,1)-(0,2) (3,5,4)-(1,4,6) (2,6)-(3,5)') sage: c (0,1)-(0,2) (2,6)-(3,5) (3,5,4)-(1,4,6) sage: c.inverse() (0,2)-(0,1) (1,4,6)-(3,5,4) (3,5)-(2,6) The operation can also be defined at the level of the separatrix diagrams and the two operation commutes:: sage: c.separatrix_diagram().inverse() == c.inverse().separatrix_diagram() True The inversion can also be seen as the composition of the horizontal and vertical symmetries:: sage: c.horizontal_symmetry().vertical_symmetry() == c.inverse() True sage: c.vertical_symmetry().horizontal_symmetry() == c.inverse() True The inversion is an involution on cylinder diagrams:: sage: all(cc.inverse().inverse() == cc for cc in AbelianStratum(4).cylinder_diagrams()) # long time True """ return CylinderDiagram([(t,b) for (b,t) in self.cylinders()])
[docs] def vertical_symmetry(self): r""" Return the cylinder diagram obtained by reflecting the cylinder configuration along the vertical axis. EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,3,4)-(0,3,5) (1,2,5)-(1,2,4)') sage: c.vertical_symmetry() (0,4,3)-(0,5,3) (1,5,2)-(1,4,2) sage: c.separatrix_diagram().vertical_symmetry() == c.vertical_symmetry().separatrix_diagram() True sage: A = AbelianStratum(2,2) sage: all(c.vertical_symmetry().stratum() == A for c in A.cylinder_diagrams()) True """ return CylinderDiagram(tuple((b[::-1],t[::-1]) for b,t in self.cylinders()))
[docs] def horizontal_symmetry(self): r""" Return the cylinder diagram obtained by reflecting the cylinder configuration along the horizontal axis. EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,3,4)-(0,3,5) (1,2,5)-(1,2,4)') sage: c.horizontal_symmetry() (0,5,3)-(0,4,3) (1,4,2)-(1,5,2) sage: c.separatrix_diagram().horizontal_symmetry() == c.horizontal_symmetry().separatrix_diagram() True sage: A = AbelianStratum(2,2) sage: all(c.horizontal_symmetry().stratum() == A for c in A.cylinder_diagrams()) True """ return CylinderDiagram(tuple((t[::-1],b[::-1]) for b,t in self.cylinders()))
[docs] def symmetries(self): r""" Return a triple ``(horiz_sym, vert_sym, inv_sym)`` EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,1)-(2,3,5) (2,3,4)-(1) (5)-(0,4)') sage: c.symmetries() (False, True, False) sage: c.horizontal_symmetry().is_isomorphic(c) False sage: c.vertical_symmetry().is_isomorphic(c) True sage: c.inverse().is_isomorphic(c) False """ n = len(self._top) # we first consider the separatrix diagram as it is much faster bot, top = two_non_connected_perms_canonical_labels(self._top, self._bot) # compute the inverses ibot = [None]*n itop = [None]*n for i in range(n): ibot[bot[i]] = i itop[top[i]] = i # horiz bot1, top1 = two_non_connected_perms_canonical_labels(itop, ibot) sep_horiz_sym = bot == bot1 and top == top1 # vert bot1, top1 = two_non_connected_perms_canonical_labels(ibot, itop) sep_vert_sym = bot == bot1 and top == top1 # inv if sep_horiz_sym and sep_vert_sym: # got the two sep_inverse_sym = True elif sep_horiz_sym^sep_vert_sym: # got exactly one sep_inverse_sym = False else: # none of them bot1, top1 = two_non_connected_perms_canonical_labels(top, bot) sep_inverse_sym = bot == bot1 and top == top1 # next we check the cylinder diagram if needed if sep_horiz_sym: c1 = self.canonical_label(inplace=False) c2 = self.horizontal_symmetry().canonical_label(inplace=False) horiz_sym = c1 == c2 else: horiz_sym = False if sep_vert_sym: c1 = self.canonical_label(inplace=False) c2 = self.vertical_symmetry().canonical_label(inplace=False) vert_sym = c1 == c2 else: vert_sym = False if horiz_sym and vert_sym: # got the two inverse_sym = True elif horiz_sym^vert_sym: # got exactly one inverse_sym = False else: # none of them c1 = self.canonical_label(inplace=False) c2 = self.inverse().canonical_label(inplace=False) inverse_sym = c1 == c2 return (horiz_sym, vert_sym, inverse_sym)
[docs] def automorphism_group(self, order=False): r""" Return the automorphism group INPUT: - ``order`` - boolean (default: False) - whether or not return the order of the group EXAMPLES:: sage: from surface_dynamics.all import * sage: cyl = CylinderDiagram('(0,1)-(0,2) (2,3)-(1,3)') sage: cyl.automorphism_group() Permutation Group with generators [(0,3)(1,2)] """ return self.to_directed_graph().automorphism_group(edge_labels=True, order=order)
[docs] def is_hyperelliptic(self,verbose=False): r""" Test of hyperellipticity Each stratum of Abelian differentials as up to three connected components. For the strata H(2g-2) and H(g-1,g-1) there is a special component called *hyperelliptic* in which all translation surfaces `(X,\omega)` in that component are such that `X` is hyperelliptic. This function returns True if and only if the cylinder diagrams correspond to a decomposition of a surface associated to the hyperelliptic components in H(2g-2) or H(g-1,g-1). EXAMPLES:: sage: from surface_dynamics.all import * In genus 2, strata H(2) and H(1,1), all surfaces are hyperelliptic:: sage: for c in AbelianStratum(2).cylinder_diagrams(): ....: print(c) ....: print(c.is_hyperelliptic()) (0,2,1)-(0,2,1) True (0,1)-(0,2) (2)-(1) True sage: for c in AbelianStratum(1,1).cylinder_diagrams(): ....: print(c) ....: print(c.is_hyperelliptic()) (0,3,1,2)-(0,3,1,2) True (0,1,2)-(0,1,3) (3)-(2) True (0,3)-(0,2) (1,2)-(1,3) True (0,1)-(2,3) (2)-(1) (3)-(0) True In higher genera, some of them are, some of them are not:: sage: C = AbelianStratum(4).cylinder_diagrams() sage: len(C) 15 sage: len(filter(lambda c: c.is_hyperelliptic(), C)) 5 sage: C = AbelianStratum(2,2).cylinder_diagrams() sage: len(C) 41 sage: len(filter(lambda c: c.is_hyperelliptic(), C)) 11 """ z = self.stratum().zeros() if z == [0] or z == [2] or z == [1,1]: return True if 0 in z: raise NotImplementedError("is_hyperelliptic method not implemented for cylinder diagrams with fake zeros") ns = self.nseps() if len(z) == 1: # minimal stratum H(2g-2) for cy in self.cylinders(): if len(cy[0]) != len(cy[1]): return False b = self.bot() t = self.top() # build list of seps in cyclic order around zero, starting by outgoing sep 0 lout = [0] lin = [] for _ in xrange(ns): lin.append(t[lout[-1]]) lout.append(b[lin[-1]]) if verbose: print('lin ', lin); print('lout', lout) # build involution on separatrices p = [None]*ns for a in xrange(ns): p[lout[a]] = lin[(a+ns//2)%ns] if verbose: print("involution on seps", p) # wsep = counter of sepatrices with a wpt wsep = 0 for cy in self.cylinders(): for k in cy[0]: # check that p(k) is on the top of the cyl that has k on its bottom if p[k] not in cy[1]: return False # check that if k is on bot and top of cyl, then p(k) = k if k in cy[1]: if k != p[k]: return False wsep += 1 if verbose: print("wsep", wsep) # check number of w pts if wsep + 2*self.ncyls() != z[0] + 3: return False # check that cylinders are stable under involution if self != CylinderDiagram( [(cy[0],tuple(map(lambda x: p[x],cy[0]))) for cy in self.cylinders()]): return False return True elif len(z) == 2: # should be stratum H(g-1,g-1) if z[0] != z[1]: return False for cy in self.cylinders(): if len(cy[0]) != len(cy[1]): return False b = self.bot() t = self.top() # build list of seps in cyclic order around first zero, starting by outgoing sep 0 lout = [0] lin = [] for _ in xrange(ns//2): lin.append(t[lout[-1]]) lout.append(b[lin[-1]]) if verbose: print('lin ', lin); print('lout', lout) # build list of seps in cyclic order around the other zero a = 0 while a in lout: a += 1 llout = [a] llin = [] for _ in xrange(ns//2): llin.append(t[llout[-1]]) llout.append(b[llin[-1]]) if verbose: print('llin ', llin); print('llout', llout) # now, try each way the involution could send lout to llout for j in xrange(ns//2): test = True # build involution on separatrices p = [None]*ns for a in xrange(ns//2): p[lout[a]] = llin[(j+a)%(ns//2)] p[llout[a]] = lin[(a-j-1)%(ns//2)] if verbose: print("involution on seps", p) wsep = 0 for cy in self.cylinders(): for k in cy[0]: # check that p(k) is on the top of the cyl that has k on its bottom if p[k] not in cy[1]: test = False break # check that if k is on bot and top of cyl, then p(k) = k if k in cy[1]: if k != p[k]: test = False break wsep += 1 if test is False: break if test is False: continue # try next j if verbose: print("wsep", wsep) # check number of w pts if wsep + 2*self.ncyls() != 2*z[0] + 4: continue # try next j # check that cylinders are stable under involution if self != CylinderDiagram( [(cy[0],tuple(map(lambda x: p[x],cy[0]))) for cy in self.cylinders()]): continue # try next j return True return False else: return False
# # construction #
[docs] def dual_graph(self): r""" The dual graph of the stable curve at infinity in the horizontal direction. This graph is defines as follows. Cut each horizontal cylinder along a circumference, then the vertices are the equivalence class of half cylinder modulo the relation "linked by a saddle connection" and the edges are the circumferences. EXAMPLES:: sage: from surface_dynamics.all import * We consider the three diagrams of the stratum H(1,1):: sage: c1 = CylinderDiagram('(0,1,2,3)-(0,1,2,3)') sage: c1.stratum() H_2(1^2) sage: c1.dual_graph() Looped multi-graph on 1 vertex sage: c2 = CylinderDiagram('(0,1)-(1,2) (2,3)-(0,3)') sage: c2.stratum() H_2(1^2) sage: c2.dual_graph() Looped multi-graph on 1 vertex sage: c3 = CylinderDiagram('(0,1)-(2,3) (2)-(0) (3)-(1)') sage: c3.stratum() H_2(1^2) sage: c3.dual_graph() Looped multi-graph on 2 vertices """ from sage.graphs.graph import Graph cb = self.bot_cycle_tuples() ct = self.top_cycle_tuples() # first compute the equivalence class of half cylinders (i.e. gives vertices) V = Graph() V.add_vertices('%db' %c[0] for c in cb) V.add_vertices('%dt' %c[0] for c in ct) for i in xrange(self.nseps()): V.add_edge( ('%db' %self._bot_to_cyl[i][0]), ('%dt' %self._top_to_cyl[i][1])) # the dual graph G = Graph(loops=True,multiedges=True) cc = map(tuple,V.connected_components()) hc2cc = {} # half-cyl to conn comp for c in cc: for e in c: hc2cc[e] = c for c in self.cylinders(): G.add_edge(hc2cc['%db' %c[0][0]],hc2cc['%dt' %c[1][0]],(c[0][0],c[1][0])) return G
[docs] def matrix_relation(self): r""" Return the matrix of relation on the lengths of the separatrices. The output matrix has size `ncyls \times nseps`. EXAMPLES:: sage: from surface_dynamics.all import * For a one cylinder diagram, there is no relations:: sage: cyl = CylinderDiagram('(0,1,2,3)-(0,1,2,3)') sage: cyl.matrix_relation() [0 0 0 0] Here is an example in the stratum H(2):: sage: cyl = CylinderDiagram('(0,1)-(0,2) (2)-(1)') sage: cyl.stratum() H_2(2) sage: cyl.matrix_relation() [ 0 1 -1] [ 0 -1 1] """ from sage.matrix.constructor import matrix m = matrix(self.ncyls(),self.nseps(),sparse=True) for i,(top,bot) in enumerate(self.cylinders()): for t in top: m[i,t] = 1 for b in bot: m[i,b] += -1 return m
# # Abelian differentials / coordinates #
[docs] def stratum_component(self): r""" Return the connected component of stratum of ``self``. EXAMPLES:: sage: from surface_dynamics.all import * sage: CylinderDiagram('(0,1)-(0,2) (2)-(1)').stratum_component() H_2(2)^hyp sage: c = CylinderDiagram('(0,3,2,1)-(1,4,3,2) (4,7,6,5)-(0,7,6,5)') sage: c.stratum_component() H_4(3^2)^hyp sage: c = CylinderDiagram('(0,1,4)-(1,6,7) (2,5,3)-(0,2,4) (6)-(5) (7)-(3)') sage: c.stratum_component() H_4(3^2)^nonhyp sage: c = CylinderDiagram('(0,6)-(1,7) (1,5,4,3,2)-(2,6,5,4,3) (7,9,8)-(0,9,8)') sage: c.stratum_component() H_5(4^2)^hyp sage: c = CylinderDiagram('(0,2,6,1)-(0,8,1,9,2,5,7,4) (3,7,4,8,9,5)-(3,6)') sage: c.stratum_component() H_5(4^2)^even sage: c = CylinderDiagram('(3,7,4,8,9,5)-(0,8,1,9,2,5,7,4) (0,2,6,1)-(3,6)') sage: c.stratum_component() H_5(4^2)^odd """ stratum = self.stratum() cc = stratum._cc if len(cc) == 1: return cc[0](stratum) from abelian_strata import HypASC if cc[0] is HypASC: if self.is_hyperelliptic(): return HypASC(stratum) elif len(cc) == 2: return cc[1](stratum) if self.spin_parity() == 0: from abelian_strata import EvenASC return EvenASC(stratum) else: from abelian_strata import OddASC return OddASC(stratum)
[docs] def smallest_integer_lengths(self): r""" Check if there is a integer solution that satisfy the cylinder conditions. If there is a solution, the function returns a list a pair ``(total_length, list_of_lengths)`` that consists of the sum of the length of the separatrices together with the list of lengths. Otherwise, returns False. EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,1)-(0,2) (2,3)-(1,3)') sage: c.smallest_integer_lengths() (4, [1, 1, 1, 1]) sage: c = CylinderDiagram('(0,1,2)-(3) (3)-(0) (4)-(1,2,4)') sage: c.smallest_integer_lengths() False sage: c = CylinderDiagram('(0,1)-(0,5) (2)-(3) (3,6)-(8) (4,8)-(6,7) (5)-(2,4) (7)-(1)') sage: c.smallest_integer_lengths() (13, [1, 2, 1, 1, 1, 2, 1, 2, 2]) """ if self.ncyls() == 1: return (self.nseps(), [1] * self.nseps()) from sage.numerical.mip import MixedIntegerLinearProgram, MIPSolverException n = self.nseps() bot = self.bot_cycle_tuples() top = [self.top_orbit(self._bot_to_cyl[b[0]][1]) for b in bot] p = MixedIntegerLinearProgram(maximization=False) scl = p.new_variable(nonnegative=True) p.set_objective(sum(scl[i] for i in xrange(n))) for i in xrange(n): p.add_constraint(scl[i],min=1) for b,t in itertools.izip(bot,top): p.add_constraint( p.sum(scl[i] for i in set(b).difference(t)) == p.sum(scl[i] for i in set(t).difference(b)) ) try: total = Integer(p.solve()) lengths = [Integer(p.get_values(scl[i])) for i in xrange(n)] return total, lengths except MIPSolverException: return False
# # homology #
[docs] def to_ribbon_graph(self): r""" Return a ribbon graph A *ribbon graph* is a graph embedded in an oriented surface such that its complement is a union of topological discs. To a cylinder diagram we associate the graph which consists of separatrices together with a choice of one vertical edge in each cylinder. The edges of the ribbon graph are labeled by ``(i,nseps+i)`` for separatrices and by ``(2(nseps+j),2(nseps+j)+1)`` for vertical in cylinders. EXAMPLES:: sage: from surface_dynamics.all import * sage: C = CylinderDiagram([((0,1),(0,2)),((2,),(1,))]) sage: C.stratum() H_2(2) sage: R = C.to_ribbon_graph(); R Ribbon graph with 1 vertex, 5 edges and 2 faces sage: l,m = R.cycle_basis(intersection=True) sage: m.rank() == 2 * C.genus() True TESTS:: sage: f = lambda c: c.to_ribbon_graph().cycle_basis(intersection=True)[1] sage: a = AbelianStratum(2) sage: all(f(c).rank() == 4 for c in a.cylinder_diagrams()) True sage: a = AbelianStratum(1,1) sage: all(f(c).rank() == 4 for c in a.cylinder_diagrams()) True """ from homology import RibbonGraphWithAngles n = self.nseps() m = self.ncyls() edges = [(i,n+i) for i in xrange(n)] + [(2*(n+i),2*(n+i)+1) for i in xrange(m)] faces = [] angles = [1] * (2*(n+m)) half = Integer(1)/Integer(2) for j,(b,t) in enumerate(self.cylinders()): face = [i for i in b] + [2*(n+j)] + [n+i for i in t[1:]+t[:1]] + [2*(n+j)+1] faces.append(tuple(face)) t1 = t[1] if len(t) > 1 else t[0] angles[b[0]] = angles[n+t1] = angles[2*(n+j)] = angles[2*(n+j)+1] = half return RibbonGraphWithAngles(edges=edges,faces=faces,angles=angles)
[docs] def to_ribbon_graph_with_holonomies(self, lengths, heights, twists): from homology import RibbonGraphWithHolonomies n = self.nseps() m = self.ncyls() edges = [(i,n+i) for i in xrange(n)] + [(2*(n+i),2*(n+i)+1) for i in xrange(m)] faces = [] half = Integer(1)/Integer(2) for j,(b,t) in enumerate(self.cylinders()): face = [i for i in b] + [2*(n+j)] + [n+i for i in t[1:]+t[:1]] + [2*(n+j)+1] faces.append(tuple(face)) holonomies = [None] * (2*(n+m)) for i in xrange(n): holonomies[i] = (lengths[i],0) holonomies[n+i] = (-lengths[i],0) for i in xrange(m): holonomies[2*(n+i)] = (twists[i], heights[i]) holonomies[2*(n+i)+1] = (-twists[i], -heights[i]) return RibbonGraphWithHolonomies(edges=edges,faces=faces,holonomies=holonomies)
[docs] def spin_parity(self): r""" Return the spin parity of any surface that is built from this cylinder diagram. EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram('(0,1,2,3,4)-(0,1,2,3,4)') sage: c.spin_parity() 0 sage: c = CylinderDiagram('(0,1,2,3,4)-(0,1,4,2,3)') sage: c.spin_parity() 1 sage: c = CylinderDiagram('(0,2,6,1)-(0,8,1,9,2,5,7,4) (3,7,4,8,9,5)-(3,6)') sage: c.spin_parity() 0 sage: c = CylinderDiagram('(3,7,4,8,9,5)-(0,8,1,9,2,5,7,4) (0,2,6,1)-(3,6)') sage: c.spin_parity() 1 """ if any(z%2 for z in self.stratum().zeros()): return None return self.to_ribbon_graph().spin_parity()
# def circumferences_of_cylinders(self,ring=None): # r""" # Return the set of circumferences of cylinders as cycles in the chain # space. # """ # from sage.modules.free_module import FreeModule # from copy import copy # # if ring is None: # from sage.rings.integer_ring import ZZ # ring = ZZ # # g = self.to_ribbon_graph() # C = g.chain_complex(ring) # C1 = C.chain_space(1) # Z1 = C.cycle_space(1) # n = g.num_edges() # # V = FreeModule(ring, n) # # l = [] # for (b,t) in self.cylinders(): # v = copy(V.zero()) # for i in b: # v[g.dart_to_edge(i,orientation=True)] = 1 # l.append(Z1(V(v))) # return l # # build one or many origamis #
[docs] def an_origami(self): r""" Return one origami with this diagram cylinder if any. EXAMPLES:: sage: from surface_dynamics.all import * sage: cyl = CylinderDiagram('(0,1)-(0,2) (2,3)-(1,3)') sage: cyl.an_origami() (1,2)(3,4) (1,3,4,2) """ res = self.smallest_integer_lengths() if res is False: return False m,lengths = res widths = [sum(lengths[i] for i in bot) for bot in self.bot_cycle_tuples()] areas = [widths[i] for i in xrange(self.ncyls())] v = [0] for a in areas: v.append(v[-1] + a) # initialization of bottom squares: sep_i -> bottom position sep_bottom_pos = [None] * self.nseps() for i,(bot,_) in enumerate(self.cylinders()): w = 0 for j in bot: sep_bottom_pos[j] = v[i] + w w += lengths[j] # initialization of sigma_h which remains constant lx = range(1, v[-1]+1) for i in xrange(self.ncyls()): for j in xrange(v[i], v[i+1], widths[i]): lx[j+widths[i]-1] = j # initialization of y except the top ly = [] for i in xrange(self.ncyls()): ly.extend([None]*widths[i]) # build the top interval without twist for i,(_,top_seps) in enumerate(self.cylinders()): top = [] for k in reversed(top_seps): top.extend(range(sep_bottom_pos[k],sep_bottom_pos[k]+lengths[k])) ly[v[i+1]-widths[i]:v[i+1]] = top # yield the origami without twist from surface_dynamics.flat_surfaces.origamis.origami import Origami_dense_pyx return Origami_dense_pyx(tuple(lx), tuple(ly))
[docs] def origami_iterator(self,n): r""" Iteration over all origamis with n squares. INPUT: - ``n`` - positive integer - the number of squares EXAMPLES:: sage: from surface_dynamics.all import * sage: cyl = CylinderDiagram('(0,1,2)-(3,1,2) (3)-(0)') sage: for o in cyl.origami_iterator(4): ....: print(o) ....: print(o.stratum()) ....: print(o.nb_squares())) (1,2,3)(4) (1,4)(2,3) H_2(1^2) 4 (1,2,3)(4) (1,2,4)(3) H_2(1^2) 4 (1,2,3)(4) (1,3,4)(2) H_2(1^2) 4 """ for w,h in self.widths_and_heights_iterator(n): for o in self.cylcoord_to_origami_iterator(w, h): yield o
[docs] def origamis(self,n=None): r""" Return the set of origamis having ``n`` squares. If ``n`` is None then return the origamis with less number of squares. EXAMPLES:: sage: from surface_dynamics.all import * sage: cyl = CylinderDiagram('(0,1,2)-(0,1,3) (3)-(2)') sage: o5 = cyl.origamis(5) sage: o5[0] (1,2,3,4)(5) (1,5,4,2,3) sage: o5[1].nb_squares() 5 sage: o5[2].stratum_component() H_2(1^2)^hyp """ if n is None: res = self.smallest_integer_lengths() if res is False: return False n = res[0] return list(self.origami_iterator(n))
[docs] def widths_and_heights_iterator(self, n): """ Iterate over the possible integer widths and heights of the cylinders for which the corresponding translation surface has area ``n``. At each iteration, the output is a pair of ``(lengths,heights)``. You can then use :meth:`cylcoord_to_origami` to build the corresponding origami. EXAMPLES:: sage: from surface_dynamics.all import * sage: cyl = CylinderDiagram([((0,1),(0,2)),((2,),(1,))]) sage: cyl (0,1)-(0,2) (2)-(1) sage: it = cyl.widths_and_heights_iterator(10) sage: l,h = it.next() sage: print(l) (2, 1, 1) sage: print(h) [3, 1] sage: cyl.cylcoord_to_origami(l,h) (1,2,3)(4,5,6)(7,8,9)(10) (1,4,7)(2,5,8)(3,6,9,10) """ from sage.combinat.integer_lists import IntegerListsLex from sage.rings.integer_ring import ZZ from sage.modules.free_module import FreeModule from copy import copy V = FreeModule(ZZ,self.nseps()) m = self.matrix_relation() min_lengths = [1] * self.nseps() for i in xrange(self.ncyls()): pos = m.nonzero_positions_in_row(i) pos_m = filter(lambda j: m[i,j] == -1, pos) pos_p = filter(lambda j: m[i,j] == 1, pos) if len(pos_m) == 1: min_lengths[pos_m[0]] = max(min_lengths[pos_m[0]], len(pos_p)) if len(pos_p) == 1: min_lengths[pos_p[0]] = max(min_lengths[pos_m[0]], len(pos_m)) min_widths = [] for bot,top in self.cylinders(): min_widths.append(max( sum(min_lengths[j] for j in top), sum(min_lengths[j] for j in bot))) for a in itertools.ifilter( lambda x: all(x[i] >= min_widths[i] for i in xrange(self.ncyls())), IntegerListsLex(n=n, length=self.ncyls(), min_part=1)): area_div = tuple(filter(lambda d: d >= min_widths[i],arith.divisors(a[i])) for i in xrange(self.ncyls())) for w in itertools.product(*area_div): h = [Integer(a[i]/w[i]) for i in xrange(self.ncyls())] # from here the resolution becomes linear and convex ... #TODO: program a linear and convex solution seps_b = [c[0] for c in self.cylinders()] nseps_b = map(len, seps_b) lengths = tuple(IntegerListsLex(n=w[i], length=nseps_b[i], min_part=1) for i in xrange(self.ncyls())) for l_by_cyl in itertools.product(*lengths): l = copy(V.zero()) for i in xrange(self.ncyls()): for j in xrange(nseps_b[i]): l[seps_b[i][j]] = l_by_cyl[i][j] if not m*l: yield l,h
[docs] def cylcoord_to_origami_iterator(self, lengths, heights): r""" Convert coordinates of the cylinders into an origami. INPUT: - ``lengths`` - lengths of the separatrices - ``heights`` - heights of the cylinders OUTPUT: - iterator over all possible origamis with those lengths and heights... EXAMPLES:: sage: from surface_dynamics.all import * sage: cyl = CylinderDiagram('(0,1,2)-(3,1,2) (3)-(0)') sage: for o in cyl.cylcoord_to_origami_iterator((1,1,1,1),(1,1)): ....: print(o) (1,2,3)(4) (1,4)(2,3) (1,2,3)(4) (1,2,4)(3) (1,2,3)(4) (1,3,4)(2) The number of origamis generated is just the product of the widths:: sage: sum(1 for _ in cyl.cylcoord_to_origami_iterator((2,1,1,2),(3,2))) 8 """ from surface_dynamics.flat_surfaces.origamis.origami_dense import Origami_dense_pyx from sage.combinat.gray_codes import product widths = [sum(lengths[i] for i in bot) for bot in self.bot_cycle_tuples()] areas = [heights[i]*widths[i] for i in xrange(self.ncyls())] # intialization of partial volumes: the set of squares in cylinder i is range(v[i],v[i+1]) v = [0] for a in areas: v.append(v[-1] + a) # initialization of bottom squares: sep_i -> bottom position sep_bottom_pos = [None] * self.nseps() for i,(bot,_) in enumerate(self.cylinders()): w = 0 for j in bot: sep_bottom_pos[j] = v[i] + w w += lengths[j] # initialization of sigma_h which remains constant lx = range(1, v[-1]+1) for i in xrange(self.ncyls()): for j in xrange(v[i], v[i+1], widths[i]): lx[j+widths[i]-1] = j # initialization of y except the top ly = [] for i in xrange(self.ncyls()): ly.extend(range(v[i]+widths[i],v[i+1])) ly.extend([None]*widths[i]) # build the top interval without twist for i,(_,top_seps) in enumerate(self.cylinders()): top = [] for k in reversed(top_seps): top.extend(range(sep_bottom_pos[k],sep_bottom_pos[k]+lengths[k])) ly[v[i+1]-widths[i]:v[i+1]] = top # yield the one without twist yield Origami_dense_pyx(tuple(lx),tuple(ly)) # yield the others using a Gray code for i,o in product(widths): if o == 1: ly.insert(v[i+1]-widths[i],ly.pop(v[i+1]-1)) else: ly.insert(v[i+1]-1,ly.pop(v[i+1]-widths[i])) yield Origami_dense_pyx(tuple(lx),tuple(ly))
[docs] def cylcoord_to_origami(self, lengths, heights, twists=None): r""" Convert coordinates of the cylinders into an origami. INPUT: - ``lengths`` - lengths of the separatrices - ``heights`` - heights of the cylinders - ``twists`` - twists for cylinders EXAMPLES:: sage: from surface_dynamics.all import * sage: c = CylinderDiagram([((0,1),(1,2)),((2,),(0,))]) sage: c.stratum() H_2(2) sage: c.cylcoord_to_origami([1,1,1],[1,1]).stratum() H_2(2) sage: o1 = c.cylcoord_to_origami([2,1,2],[1,1],[1,0]) sage: o1 = o1.relabel() sage: o2 = c.cylcoord_to_origami([2,1,2],[1,1],[0,1]) sage: o2 = o2.relabel() sage: o3 = c.cylcoord_to_origami([2,1,2],[1,1],[1,1]) sage: o3 = o3.relabel() sage: all(o.stratum() == AbelianStratum(2) for o in [o1,o2,o3]) True sage: o1 == o2 or o1 == o3 or o3 == o1 False If the lengths are not compatible with the cylinder diagram a ValueError is raised:: sage: c.cylcoord_to_origami([1,2,3],[1,1]) Traceback (most recent call last): ... ValueError: lengths are not compatible with cylinder equations TESTS:: sage: c = CylinderDiagram([((0,),(1,)), ((1,2,3),(0,2,3))]) sage: c (0)-(1) (1,2,3)-(0,2,3) sage: lengths = [1,1,1,1] sage: heights = [1,1] sage: c.cylcoord_to_origami(lengths,heights,[0,0]) (1)(2,3,4) (1,2)(3,4) sage: c.cylcoord_to_origami(lengths,heights,[0,1]) (1)(2,3,4) (1,2,3)(4) sage: c.cylcoord_to_origami(lengths,heights,[0,2]) (1)(2,3,4) (1,2,4)(3) """ from surface_dynamics.flat_surfaces.origamis.origami_dense import Origami_dense_pyx widths = [sum(lengths[i] for i in bot) for bot,_ in self.cylinders()] if widths != [sum(lengths[i] for i in top) for _,top in self.cylinders()]: raise ValueError, "lengths are not compatible with cylinder equations" if twists is None: twists = [0] * len(widths) elif len(twists) != len(widths): raise ValueError, "not enough twists" else: twists = [(-twists[i])%widths[i] for i in xrange(len(widths))] areas = [heights[i]*widths[i] for i in xrange(self.ncyls())] # intialization of partial volumes: the set of squares in cylinder i is range(v[i],v[i+1]) v = [0] for a in areas: v.append(v[-1] + a) # initialization of bottom squares: sep_i -> bottom position sep_bottom_pos = [None] * self.nseps() for i,(bot,_) in enumerate(self.cylinders()): w = 0 for j in bot: sep_bottom_pos[j] = v[i] + w w += lengths[j] # build the permutation r lx = range(1, v[-1]+1) for i in xrange(self.ncyls()): for j in xrange(v[i], v[i+1], widths[i]): lx[j+widths[i]-1] = j # build permutation u with the given twists ly = [] for i,(_,top_seps) in enumerate(self.cylinders()): # everything excepted the top ly.extend(range(v[i]+widths[i],v[i+1])) # the top k = top_seps[0] top = range(sep_bottom_pos[k],sep_bottom_pos[k]+lengths[k]) for k in reversed(top_seps[1:]): top.extend(range(sep_bottom_pos[k],sep_bottom_pos[k]+lengths[k])) ly.extend(top[twists[i]:] + top[:twists[i]]) # yield the one without twist return Origami_dense_pyx(tuple(lx), tuple(ly))
#TODO # def chain_complex_dual(self, ring=None): # r""" # Return a chain complex for the cylinder diagram # # The vertices are in bijection with the cylinder of self # The edges are in bijection with separatrices and cylinders # # """ # from homology import TranslationSurfaceChainComplex # from sage.rings.integer import Integer # # if ring is None: # from sage.rings.integer_ring import IntegerRing # ring = IntegerRing() # # vertices = [] # list of list of vertex = integers from 0 to ncyls # # (in or out, edge) # edges = {} # label -> (start vertex,end) # angles = {} # (in or out,label) -> angle to next edge # # cyls = self.cylinders() # t2c = [None]*self.nseps() # b2c = [None]*self.nseps() # # for k,(cb,ct) in enumerate(cyls): # for i in cb: b2c[i] = k # for i in ct: t2c[i] = k # # for k,(cb,ct) in enumerate(cyls): # vertex = [] # e = 'c%d' %k # edges[e] = (k,k) # angles[(1,e)] = Integer(1)/Integer(2) # angles[(-1,e)] = Integer(1)/Integer(2) # # the incoming edges from bottom # for i in cb: # e = 's%d' %i # edges[e] = (t2c[i],k) # vertex.append((-1,e)) # angles[(-1,e)] = Integer(0) # angles[(-1,e)] = Integer(1)/Integer(2) # # # the central edge (outgoing) # vertex.append((1, 'c%d' %k)) # # # the outgoing edges from top # for i in ct: # e = 's%d' %i # vertex.append((1,e)) # angles[(1,e)] = Integer(0) # angles[(1,e)] = Integer(1)/Integer(2) # # # the central edge (incoming) # vertex.append((-1, 'c%d' %k)) # # vertices.append(vertex) # # return TranslationSurfaceChainComplex(ring,vertices,edges,angles)