| Download
Project: admcycles
Views: 724Visibility: Unlisted (only visible to those who know the link)
Image: ubuntu2004from __future__ import absolute_import1from __future__ import print_function23# pylint does not know sage4from sage.structure.sage_object import SageObject # pylint: disable=import-error5from sage.rings.rational_field import QQ # pylint: disable=import-error6from sage.misc.cachefunc import cached_function # pylint: disable=import-error7from sage.misc.flatten import flatten # pylint: disable=import-error89from copy import deepcopy1011import admcycles.diffstrata.levelstratum1213#######################################################################14#######################################################################15###### Point Dictionaries16#######################################################################17## * Points on generalised strata are of the form (i,j) where i is the18## index of the component and j is the index in the signature of19## the component.20## * An EmbeddedLevelGraph is a LevelGraph together with a dictionary21## mapping all non-half-edges (i.e. marked points) to the the points22## of the associated stratum.23## Note that the numbering of points starts with 1 while the indices24## of the signatures start with 0. I.e. in the case of a gen. stratum25## with only one component, the dictionary is i -> (0,i-1).26## * For clutching, we need dictionaries that map points of strata to27## points of other strata. This allows us to embed clutched LevelGraphs28## by composition.29## * When splitting a BIC into top and bottom, we consequently need to30## remember the dictionary that maps marked points of the top and31## bottom gen. stratum into the points of stratum the BIC was32## embedded into.33##34## Thus, a splitting of a BIC inside stratum X must result in two generalised35## strata, top and bottom, as well as three dictionaries:36## * emb_top: points of top -> points of X37## * emb_bot: points of bottom -> points of X38## * clutching: points of top -> points of bottom39## All of these dictionaries are injective, the keys of emp_top and clutching40## give a partition of the points of top, the keys of emb_bot and the values41## of clutching give a partition of the points of bottom and the values of42## emb_top and emb_bot give a partition of the points of X.43#######################################################################44#######################################################################4546def clutch(X, top, bottom, clutch_dict, emb_dict_top, emb_dict_bot,47middle=None, clutch_dict_lower={}, clutch_dict_long={}, emb_dict_mid={}):48"""49Clutch EmbeddedLevelGraphs top and bottom to get a new EmbeddedLevelGraph.5051If middle is specified, we do a "double clutching" top - middle - bottom to52give a graph in X.53NOTE:54* this cannot be split into two steps, as the intermediate graph is55not a graph in X!56* We include the possibility to clutch points in the top component *past*57the middle to the bottom component (long edges!)5859This is the inverse procedure to EmbeddedLevelGraph.split() and60GeneralisedStratum.doublesplit().6162Note that if top or bottom is None, we return None.6364Args:65X (GeneralisedStratum): Stratum that the clutched graph will live in66top (EmbeddedLevelGraph): Top component to be clutched67bottom (EmbeddedLevelGraph): Bottom component to be clutched68middle (EmbeddedLevelGraph, optional, defaults to None): Middle component to69be clutched.70clutch_dict (dict): The dictionary giving the clutching information,71(i.e. the edges that will be inserted).72In the case of a "simple clutch", i.e. top to bottom with no middle,73a dictionary:74point on top stratum -> point on bottom stratum75In the case of a middle graph, i.e. a "double clutching":76point on top stratum -> point on middle stratum.77In this case, we also need clutch_dict_lower for the other clutching78and clutch_dict_long for the long edges.79clutch_dict_lower (dict, optional): In the case of a "double clutching", the80info for the "lower" clutching, i.e. a dictionary81point on middle stratum -> point on bottom stratum82clutch_dict_long (dict, optional): In the case of a "double clutching", the83info for the "long edges", i.e. a dictionary84point on top stratum -> point on bottom stratum85emb_dict_top (dict): dictionary giving the embedding of the resulting86EmbeddedLevelGraph, i.e. points on top stratum -> point on87enveloping stratum.88emb_dict_bot (dict): dictionary giving the embedding of the resulting89EmbeddedLevelGraph, i.e. points on bottom stratum -> point on90enveloping stratum.91emb_dict_mid (dict, optional): dictionary giving the embedding of the92resulting EmbeddedLevelGraph, i.e. points on middle stratum -> point on93enveloping stratum.9495Returns:96EmbeddedLevelGraph: Clutched LevelGraph together with embedding.9798Returns:99tuple: EmbeddedLevelGraph: as above100101EXAMPLES ::102103sage: from admcycles.diffstrata import *104sage: X=GeneralisedStratum([Signature((1,1))])105sage: assert clutch(**X.bics[1].split()).is_isomorphic(X.bics[1])106sage: assert all(clutch(**B.split()).is_isomorphic(B) for B in X.bics)107108The same works for 3-level graphs and doublesplit:109110sage: X=GeneralisedStratum([Signature((1,1))])111sage: assert all(X.lookup_graph(*ep).is_isomorphic(clutch(**X.doublesplit(ep))) for ep in X.enhanced_profiles_of_length(2))112sage: X=GeneralisedStratum([Signature((2,2,-2))])113sage: assert all(X.lookup_graph(*ep).is_isomorphic(clutch(**X.doublesplit(ep))) for ep in X.enhanced_profiles_of_length(2)) # long time (4 seconds)114"""115if top is None or bottom is None:116return None117## Build new EmbeddedLevelGraph:118## This is somewhat similar to levelstratum's unite_embedded_graphs119## but here the result is embedded into a _different_ stratum!120# In case top, middle or bottom are LevelStrata, we replace them by their smooth121# component (this is mainly to allow clutch to eat the output of split...)122if isinstance(top, admcycles.diffstrata.levelstratum.LevelStratum):123top = top.smooth_LG124if isinstance(bottom, admcycles.diffstrata.levelstratum.LevelStratum):125bottom = bottom.smooth_LG126if isinstance(middle, admcycles.diffstrata.levelstratum.LevelStratum):127# in particular, middle is not None!128middle = middle.smooth_LG129# genera simply get combined130if middle is None:131newgenera = top.LG.genera + bottom.LG.genera132else:133newgenera = top.LG.genera + middle.LG.genera + bottom.LG.genera134# We renumber the levels consecutively starting at 0.135top_levels = top.LG.numberoflevels()136top_level_dict = {top.LG.internal_level_number(l) : -l for l in range(top_levels)}137newlevels = [top_level_dict[l] for l in top.LG.levels]138if middle is None:139mid_levels = 0140mid_level_dict = {}141else:142# the levels of the middle component have to be shifted:143mid_levels = middle.LG.numberoflevels()144mid_level_dict = {middle.LG.internal_level_number(l) : -l - top_levels145for l in range(mid_levels)}146newlevels += [mid_level_dict[l] for l in middle.LG.levels]147bot_levels = bottom.LG.numberoflevels()148# The levels of the bottom component have to be shifted by both top and middle:149bot_level_dict = {bottom.LG.internal_level_number(l) : -l - top_levels - mid_levels150for l in range(bot_levels)}151newlevels += [bot_level_dict[l] for l in bottom.LG.levels]152# TODO: What is a sensible level dictionary?153# At the moment, we choose the identity.154newdlevels = {-l : -l for l in range(top_levels + mid_levels + bot_levels)}155# The legs have to be renumbered in analogy to levelstratum's unite_embedded_graphs:156newlegs = []157newedges = []158newpoleorders = {}159newdmp = {} # the new embedding is given by the emb_dicts160# For adding the new edges, we have to record the new leg numbers and this will161# happen at different stages (on each component).162# The idea is, for each set of edges, to create a list of the form163# [(starting leg 1, starting leg 2,....), (ending leg 1, ending leg 2,...)]164# and then zip these lists to create the edges.165# The points are currently stored (as points on the respective stratum) in the166# various clutching dictionaries.167# We want to move them to lists of the form described above.168if middle is None:169# If this is a "simple clutch", we only have to add edges between top170# and bottom.171clutch_edges = [] # the new edges to be added172else:173# Otherwise, we have to distinguish between:174# * edges from top to middle:175clutch_edges_tm = []176# * edges from middle to bottom:177clutch_edges_mb = []178# * and edges from top to bottom (going past middle):179clutch_edges_tb = []180leg_number_shift = 0 # the shift for renumbering legs181legs = 0 # leg counter182# We now go through the components, starting with the top:183#184# Note that we also have to choose the appropriate embedding dictionary.185# We will also have to record the clutching information, as the points are all186# going to be renamed, so we have to remember who will be clutched.187#188if middle is None:189# in the "simple clutch" case, it makes sense to also pass190# the clutch points to each component; these are stored in clutch_dict191comp_data = ((top,emb_dict_top,clutch_dict.keys()),192(bottom, emb_dict_bot, clutch_dict.values()))193else:194# We have to sort out the clutching in the loop anyway, so we just pass a dummy.195comp_data = ((top, emb_dict_top, {}),196(middle, emb_dict_mid, {}),197(bottom, emb_dict_bot, {}))198# emb_g: graph to be clutched199# emb_dict: dictionary200# marked points of the enveloping stratum of emb_g -> points of X201for emb_g, emb_dict, clutch_points in comp_data:202leg_dict = {} # old number -> new number203for i, l in enumerate(flatten(emb_g.LG.legs)):204# the point numbers on bottom component are shifted by the top number205newlegnumber = leg_number_shift + i + 1206leg_dict[l] = newlegnumber207# while we're at it, we add the pole orders:208newpoleorders[newlegnumber] = emb_g.LG.poleorders[l]209legs += 1210# For the dictionary of marked points (for the embedding), we211# must distinguish if this is a marked point or a half-edge.212# Marked points are simply the ones for which we have a key213# in emb_dict :-)214# The newdmp must then map this point to the image of its dmp in215# the new stratum, i.e. the image under emb_dict:216# Note that emb_dict eats stratum points, i.e. the image of the217# leg under dmp.218try:219newdmp[newlegnumber] = emb_dict[emb_g.dmp[l]]220except KeyError:221pass222leg_number_shift += legs223# build (nested) list of legs:224newlegs += [[leg_dict[l] for l in comp] for comp in emb_g.LG.legs]225# finally, the edges are renumbered accordingly:226newedges += [(leg_dict[e[0]], leg_dict[e[1]]) for e in emb_g.LG.edges]227# We now record the clutching information:228# Note that the points to be clutched are points on the Stratum!229#230# Because everything was renamed with leg_dict, we need to *now* remember231# the edges to clutch (see discussion above).232#233# For this, we now have to distinguish if we're working with234# two or three components:235# * In the two component case, the points to be clutched are236# the keys (top) and values (bottom) of clutch_dict.237# Said differently: clutch_dict encodes the edges that will be added.238if middle is None:239# We save "half" of the clutch points in each step, afterwards we just240# have to combine these lists to obtain all new edges.241clutch_edges.append(tuple(leg_dict[emb_g.dmp_inv[p]] for p in clutch_points))242# * In the three component case,243# * the *keys* of clutch_dict are points of the *top* component244# * the *values* clutch_dict are those points on the *middle* component that245# are clutched to the *top* component246# * the *keys* of clutch_dict_lower are points of the *middle* component247# * the *values* of clutch_dict_lower are points of the *bottom* component that248# are clutched to the *middle* component249# * the *keys* of clutch_dict_long are points of the *top* component250# * the *values* of clutch_dict_long are points of the *bottom* component that251# are clutched to the *top* component (long edges going past the middle)252# Said differently:253# * clutch_dict encodes edges top - middle254# * clutch_dict_lower encodes edges middle - bottom255# * clutch_dict_long encodes edges top - bottom (long edges going past middle)256else:257# We save the tuple of legs on the current component:258if emb_g is top:259clutch_edges_tm.append(tuple(260leg_dict[emb_g.dmp_inv[p]] for p in clutch_dict.keys()261))262clutch_edges_tb.append(tuple(263leg_dict[emb_g.dmp_inv[p]] for p in clutch_dict_long.keys()264))265elif emb_g is middle:266clutch_edges_tm.append(tuple(267leg_dict[emb_g.dmp_inv[p]] for p in clutch_dict.values()268))269clutch_edges_mb.append(tuple(270leg_dict[emb_g.dmp_inv[p]] for p in clutch_dict_lower.keys()271))272else:273assert emb_g is bottom274clutch_edges_tb.append(tuple(275leg_dict[emb_g.dmp_inv[p]] for p in clutch_dict_long.values()276))277clutch_edges_mb.append(tuple(278leg_dict[emb_g.dmp_inv[p]] for p in clutch_dict_lower.values()279))280# Now the actual clutching happens, i.e. adding in the extra edges between281# the points of clutch_dict:282if middle is None:283assert len(clutch_edges) == 2284newedges += list(zip(*clutch_edges))285else:286assert len(clutch_edges_tm) == 2287assert len(clutch_edges_tb) == 2288assert len(clutch_edges_mb) == 2289newedges += list(zip(*clutch_edges_tm)) + list(zip(*clutch_edges_tb)) + list(zip(*clutch_edges_mb))290291LG = admcycles.diffstrata.levelgraph.LevelGraph(292newgenera, newlegs, newedges, newpoleorders, newlevels293)294295ELG = admcycles.diffstrata.levelstratum.EmbeddedLevelGraph(X, LG, newdmp, newdlevels)296297if not ELG.is_legal():298# This should not happen if R-GRC is checked!299# print("Illegal clutch attempted: %r, %r" % (top,bottom))300raise RuntimeError("Illegal clutch, this should not happen anymore!")301302return ELG303304class GenDegenerationGraph(SageObject):305"""306The degeneration graph of the Generalised Stratum X.307308A degeneration graph of a (generalised) stratum is built recursively.309For that we need to know:310* The BICs inside X311* For each BIC its top and bottom component (generalised strata)312* For each BIC the clutching map of these components313* For each top and bottom component of each BIC an embedding of their314respective BICs into BIC(X)315This allows us to translate products of BICs on X into clutchings of316products of BICs on top and bottom components and gives a recursive317procedure to compute the LevelGraph(s) for any product of BICs in X.318319Args:320X (GeneralisedStratum): The GeneralisedStratum we give the degeneration321graph of.322"""323def __init__(self,X):324self.X = X325self.n = len(self.X.bics) # possibly generates all bics of X (!)326self._top_to_bic = [None for _ in range(self.n)] # initialise on demand327self._bot_to_bic = [None for _ in range(self.n)] # initialise on demand328self._middle_to_bic = {} # initialise on demand329self._top_to_bic_inv = [None for _ in range(self.n)] # initialise on demand330self._bot_to_bic_inv = [None for _ in range(self.n)] # initialise on demand331self._middle_to_bic_inv = {} # initialise on demand332# Note that while top_to_bic and bot_to_bic aren't injective, their333# images are disjoint, i.e. we can remove the guys we found for top334# from the ones we're searching through for bot (and vice versa).335# This happens for every bic, though.336self._unused_bics_top = [[i for i in range(self.n)] for _ in range(self.n)]337self._unused_bics_bot = [[i for i in range(self.n)] for _ in range(self.n)]338# To build all LevelGraphs inside a (generalised) stratum, we store all339# tuples of indices of bics that give a (non-empty!) 3-level graph:340# Note that the multiplicities tell us something about automorphisms341# so we keep track of them and the set in parallel (use _append_triple_prod() !!)342self._triple_prods = []343self._triple_prod_set = set()344self._triple_prod_set_list = None345346def __repr__(self):347return "GenDegenerationGraph(X=%r)" % self.X348349def _append_triple_prod(self,t):350## append the tuple t to _triple_prods (both the list and the set...)351self._triple_prods.append(t)352self._triple_prod_set.add(t)353354@property355def triple_prods(self):356"""357A list of profiles of the 3-level graphs in X.358359Note that this is generated on first call.360361Returns:362list: list of tuples of length two of indices of X.bics.363"""364if self._triple_prod_set_list is None:365# the easiest way to initialise is to initialise all bic maps:366for i in range(self.n):367self.top_to_bic(i)368self.bot_to_bic(i)369self._triple_prod_set_list = list(self._triple_prod_set)370return self._triple_prod_set_list371372def top_to_bic(self,i):373"""374A dictionary indices of BICs of X.bic[i].top -> indices of X.bics.375376Note that this is created once and then reused.377378Args:379i (int): Index of X.bics380381Raises:382RuntimeError: Raised if the squish of the clutching of a degeneration of383the top component with X.bic[i].bot is not found in X.bics.384385Returns:386dict: Dictionary mapping BICs of X.bic[i].top to indices of X.bics.387"""388if self._top_to_bic[i] is None:389B = self.X.bics[i]390top_to_bic = {} # index of B.top.bics -> index of X.bics391for j, Bt in enumerate(B.top.bics):392# Note that Bt is embedded (as a Graph) into B.top393# B.top is embedded (as a stratum) into B (via B.emb_top)394G = clutch(self.X,Bt,B.bot,B.clutch_dict,B.emb_top,B.emb_bot)395if G is None:396# illegal clutch:397raise RuntimeError("Illegal clutch, this should not happen anymore!")398# Because the degeneration is clutched on top, squishing the399# bottom level gives a new divisor (i.e. delta(1))400squished_bic = G.delta(1)401for im_j in self._unused_bics_top[i]:402if im_j == i:403continue # B^2 is empty404if squished_bic.is_isomorphic(self.X.bics[im_j]):405top_to_bic[j] = im_j406# Record profile of the 3-level graph:407self._append_triple_prod((im_j,i))408if self._bot_to_bic[i] is None:409# otherwise bot_to_bic has already been constructed and410# this is futile...411try:412self._unused_bics_bot[i].remove(im_j)413except ValueError:414# this is a case where the map is non-injective415pass416break417else: # no break418raise RuntimeError("delta(1) of %s, %s, not found in list of BICs of %s"419% (G,squished_bic,self.X)420)421self._top_to_bic[i] = top_to_bic.copy()422return self._top_to_bic[i]423424def bot_to_bic(self,i):425"""426A dictionary indices of BICs of X.bic[i].bot -> indices of X.bics.427428Note that this is created once and then reused.429430Args:431i (int): Index of X.bics432433Raises:434RuntimeError: Raised if the squish of the clutching of a degeneration of435the bottom component with X.bic[i].top is not found in X.bics.436437Returns:438dict: Dictionary mapping BICs of X.bic[i].bot to indices of X.bics.439"""440if self._bot_to_bic[i] is None:441B = self.X.bics[i]442bot_to_bic = {} # index of B.top.bics -> index of X.bics443for j, Bb in enumerate(B.bot.bics):444# Note that Bb is embedded (as a Graph) into B.bot445# B.bot is embedded (as a stratum) into B (via B.emb_bot)446G = clutch(self.X,B.top,Bb,B.clutch_dict,B.emb_top,B.emb_bot)447if G is None:448# illegal clutch:449raise RuntimeError("Illegal clutch, this should not happen anymore!")450# Because the degeneration is clutched on bottom, squishing the451# top level gives a new divisor (i.e. delta(2))452squished_bic = G.delta(2)453for im_j in self._unused_bics_bot[i]:454if im_j == i:455continue # B^2 is empty456if squished_bic.is_isomorphic(self.X.bics[im_j]):457bot_to_bic[j] = im_j458# Record profile of the 3-level graph:459self._append_triple_prod((i,im_j))460if self._top_to_bic[i] is None:461# otherwise top_to_bic has already been constructed and462# this is futile...463try:464self._unused_bics_top[i].remove(im_j)465except ValueError:466# this is a case where the map is non-injective467pass468break469else: # no break470raise RuntimeError("delta(2) of %s, %s, not found in list of BICs of %s"471% (G,squished_bic,self.X)472)473self._bot_to_bic[i] = bot_to_bic.copy()474return self._bot_to_bic[i]475476def middle_to_bic(self,enh_profile):477"""478A dictionary for each 3-level graph mapping (indices of) BICs of the middle level479to (indices of) BICs of the enveloping stratum.480481Args:482enh_profile (tuple): Enhanced profile of a 3-level graph.483484Raises:485RuntimeError: Raised if enh_profile is not a 3-level graph.486RuntimeError: Raised if a degeneration of the middle level is isomorphic487(after squishing) to more than one BIC of X.488RuntimeError: Raised if no isomorphic BIC of X is found.489490Returns:491dict: dictionary: indices of bics of the middle level -> indices of X.bics492493EXAMPLES ::494495"""496if enh_profile not in self._middle_to_bic:497p, i = enh_profile498if len(p) != 2:499raise RuntimeError("Only 3-level graphs have a well-defined middle! %r" % (enh_profile,))500# The dictionary we want to create:501mid_to_bic = {}502# The easiest thing is to split the graph and reuse all the clutching503# info this yields, replacing the middle level by one of its BICs:504clutching_info = self.X.doublesplit(enh_profile)505L = clutching_info['middle']506# candidates are those BICs that appear as bottom degenerations507# of the top level *and* as top degenerations of the bottom level:508candidates = set()509top_deg = set(self.top_to_bic(p[1]).values())510for b in self.bot_to_bic(p[0]).values():511if b in top_deg:512candidates.add(b)513# We now clutch in degenerations of the middle level:514for i, B in enumerate(L.bics):515clutching_info['middle'] = B516H = clutch(**clutching_info)517# We now apply to delta to find the new BIC.518# Note that delta is shifted with regard to the profile numbering.519# It also allows us to recover p:520assert H.delta(1).is_isomorphic(self.X.bics[p[0]])521assert H.delta(3).is_isomorphic(self.X.bics[p[1]])522# delta(2) is the one we are interested in:523XB = H.delta(2)524for b in candidates:525if XB.is_isomorphic(self.X.bics[b]):526# check if more than one is found527if i in mid_to_bic:528raise RuntimeError("BIC %r of %r seems to be isomorphic to several BICs of %r!" % (i,L,self.X))529mid_to_bic[i] = b530if i not in mid_to_bic:531raise RuntimeError("BIC %r of %r not found in BICs of %r!" % (i,L,self.X))532self._middle_to_bic[enh_profile] = mid_to_bic.copy()533return self._middle_to_bic[enh_profile]534535def top_to_bic_inv(self,i):536"""537Inverse of top_to_bic.538539More Precisely: A dictionary assigning indices of X.bics a list of indices of540X.top.bics. Note that this can be more than one (if the intersection is not541irreducible).542543Note also that not all indices of X.bics are keys (but if not, they should be544keys of bot_to_bic_inv)!545546Args:547i (int): index of X.bics548549Returns:550dict: index of X.bics -> list of indices of X.top.bics.551"""552if self._top_to_bic_inv[i] is None:553self._top_to_bic_inv[i] = {}554d = self.top_to_bic(i) # possibly built here (!)555for j, im_j in d.items():556try:557self._top_to_bic_inv[i][im_j].append(j)558except KeyError:559self._top_to_bic_inv[i][im_j] = [j]560return self._top_to_bic_inv[i]561562def bot_to_bic_inv(self,i):563"""564Inverse of bot_to_bic.565566More Precisely: A dictionary assigning indices of X.bics a list of indices of567X.bot.bics. Note that this can be more than one (if the intersection is not568irreducible).569570Note also that not all indices of X.bics are keys (but if not, they should be571keys of top_to_bic_inv)!572573Args:574i (int): index of X.bics575576Returns:577dict: index of X.bics -> list of indices of X.bot.bics.578"""579if self._bot_to_bic_inv[i] is None:580self._bot_to_bic_inv[i] = {}581d = self.bot_to_bic(i) # possibly built here (!)582for j, im_j in d.items():583try:584self._bot_to_bic_inv[i][im_j].append(j)585except KeyError:586self._bot_to_bic_inv[i][im_j] = [j]587return self._bot_to_bic_inv[i]588589def middle_to_bic_inv(self,enh_profile):590"""591Inverse of middle_to_bic.592593More Precisely: A dictionary assigning indices of X.bics a list of indices of594{middle level of enh_profile}.bics.595Note that this can be more than one (if the intersection is not596irreducible).597598Args:599enh_profile (tuple): enhanced profile of a 3-level graph.600601Returns:602dict: index of X.bics -> list of indices of {middle level of enh_profile}.bics.603604EXAMPLES ::605606"""607if enh_profile not in self._middle_to_bic_inv:608self._middle_to_bic_inv[enh_profile] = {}609d = self.middle_to_bic(enh_profile) # possibly built here (!)610for j, im_j in d.items():611try:612self._middle_to_bic_inv[enh_profile][im_j].append(j)613except KeyError:614self._middle_to_bic_inv[enh_profile][im_j] = [j]615return self._middle_to_bic_inv[enh_profile]616617618