from collections import defaultdict
from sage.misc.misc_c import prod
from sage.misc.cachefunc import cached_method
from sage.combinat.subset import Subsets
from sage.rings.integer_ring import ZZ
from sage.modules.free_module import FreeModule
from sage.functions.other import floor
from sage.graphs.graph import Graph
from sage.rings.all import Integer
from sage.arith.all import factorial
from sage.groups.perm_gps.permgroup_named import SymmetricGroup
from sage.structure.sage_object import SageObject
from sage.plot.polygon import polygon2d
from sage.plot.text import text
from sage.plot.bezier_path import bezier_path
from sage.plot.line import line
from sage.plot.circle import circle
class StableGraph(SageObject):
r"""
Stable graph.
A stable graph is a graph (with allowed loops and multiple edges) that
has "genus" and "marking" decorations at its vertices. It is represented
as a list of genera of its vertices, a list of legs at each vertex and a
list of pairs of legs forming edges.
The markings (the legs that are not part of edges) are allowed to have
repetitions.
EXAMPLES:
We create a stable graph with two vertices of genera 3,5 joined by an edge
with a self-loop at the genus 3 vertex::
sage: from admcycles import StableGraph
sage: StableGraph([3,5], [[1,3,5],[2]], [(1,2),(3,5)])
[3, 5] [[1, 3, 5], [2]] [(1, 2), (3, 5)]
The markings can have repetitions::
sage: StableGraph([1,0], [[1,2], [3,2]], [(1,3)])
[1, 0] [[1, 2], [3, 2]] [(1, 3)]
It is also possible to create graphs which are not neccesarily stable::
sage: StableGraph([1,0], [[1], [2,3]], [(1,2)])
[1, 0] [[1], [2, 3]] [(1, 2)]
sage: StableGraph([0], [[1]], [])
[0] [[1]] []
If the input is invalid a ``ValueError`` is raised::
sage: StableGraph([0, 0], [[1], [2], [3]], [])
Traceback (most recent call last):
...
ValueError: genera and legs must have the same length
sage: StableGraph([0, 'hello'], [[1], [2]], [(1,2)])
Traceback (most recent call last):
...
ValueError: genera must be a list of non-negative integers
sage: StableGraph([0, 0], [[1,2], [3]], [(3,4)])
Traceback (most recent call last):
...
ValueError: the edge (3, 4) uses invalid legs
sage: StableGraph([0, 0], [[2,3], [2]], [(2,3)])
Traceback (most recent call last):
...
ValueError: the edge (2, 3) uses invalid legs
"""
__slots__ = ['_genera', '_legs', '_edges', '_maxleg', '_mutable',
'_graph_cache', '_canonical_label_cache', '_hash']
def __init__(self, genera, legs, edges, mutable=False, check=True):
"""
INPUT:
- ``genera`` -- (list) List of genera of the vertices of length m.
- ``legs`` -- (list) List of length m, where ith entry is list of legs
attached to vertex i.
- ``edges`` -- (list) List of edges of the graph. Each edge is a 2-tuple of legs.
- ``mutable`` - (boolean, default to ``False``) whether this stable graph
should be mutable
- ``check`` - (boolean, default to ``True``) whether some additional sanity
checks are performed on input
"""
if check:
if not isinstance(genera, list) or \
not isinstance(legs, list) or \
not isinstance(edges, list):
raise TypeError('genera, legs, edges must be lists')
if len(genera) != len(legs):
raise ValueError('genera and legs must have the same length')
if not all(isinstance(g, (int, Integer)) and g >= 0 for g in genera):
raise ValueError("genera must be a list of non-negative integers")
mlegs = defaultdict(int)
for v,l in enumerate(legs):
if not isinstance(l, list):
raise ValueError("legs must be a list of lists")
for i in l:
if not isinstance(i, (int, Integer)) or i <= 0:
raise ValueError("legs must be positive integers")
mlegs[i] += 1
for e in edges:
if not isinstance(e, tuple) or len(e) != 2:
raise ValueError("invalid edge {}".format(e))
if mlegs.get(e[0], 0) != 1 or mlegs.get(e[1], 0) != 1:
raise ValueError("the edge {} uses invalid legs".format(e))
self._genera = genera
self._legs = legs
self._edges = edges
self._maxleg = max([max(j+[0]) for j in self._legs])
self._mutable = bool(mutable)
self._graph_cache = None
self._canonical_label_cache = None
self._hash = None
def set_immutable(self):
r"""
Set this graph immutable.
"""
self._mutable = False
def is_mutable(self):
r"""
Return whether this graph is mutable.
"""
return self._mutable
def __hash__(self):
r"""
EXAMPLES::
sage: from admcycles import StableGraph
sage: G1 = StableGraph([3,5], [[1,3,5],[2]], [(1,2),(3,5)])
sage: G2 = StableGraph([3,5], [[1,3,5],[2]], [(1,2),(3,5)])
sage: G3 = StableGraph([3,5], [[3,5,1],[2]], [(2,1),(3,5)])
sage: G4 = StableGraph([2,2], [[1,3,5],[2]], [(1,2),(3,5)])
sage: G5 = StableGraph([3,5], [[1,4,5],[2]], [(1,2),(4,5)])
sage: hash(G1) == hash(G2)
True
sage: (hash(G1) == hash(G3) or hash(G1) == hash(G4) or
....: hash(G1) == hash(G5) or hash(G3) == hash(G4) or
....: hash(G3) == hash(G5) or hash(G4) == hash(G5))
False
"""
if self._mutable:
raise TypeError("mutable stable graph are not hashable")
if self._hash is None:
self._hash = hash((tuple(self._genera),
tuple(tuple(x) for x in self._legs),
tuple(self._edges)))
return self._hash
def copy(self, mutable=True):
r"""
Return a copy of this graph.
When it is asked for an immutable copy of an immutable graph the
current graph is returned without copy.
INPUT:
- ``mutable`` - (boolean, default ``True``) whether the returned graph must
be mutable
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([3,5], [[1,3,5],[2]], [(1,2),(3,5)])
sage: H = G.copy()
sage: H == G
True
sage: H.is_mutable()
True
sage: H is G
False
sage: G.copy(mutable=False) is G
True
"""
if not self.is_mutable() and not mutable:
return self
G = StableGraph.__new__(StableGraph)
G._genera = self._genera[:]
G._legs = [x[:] for x in self._legs]
G._edges = [x[:] for x in self._edges]
G._maxleg = self._maxleg
G._mutable = mutable
G._graph_cache = None
G._canonical_label_cache = None
G._hash = None
return G
def __repr__(self):
return repr(self._genera)+ ' ' + repr(self._legs) + ' ' + repr(self._edges)
def __eq__(self, other):
r"""
TESTS::
sage: from admcycles import StableGraph
sage: G1 = StableGraph([3,5], [[1,3,5],[2]], [(1,2),(3,5)])
sage: G2 = StableGraph([3,5], [[1,3,5],[2]], [(1,2),(3,5)])
sage: G3 = StableGraph([3,5], [[3,5,1],[2]], [(2,1),(3,5)])
sage: G4 = StableGraph([2,2], [[1,3,5],[2]], [(1,2),(3,5)])
sage: G5 = StableGraph([3,5], [[1,4,5],[2]], [(1,2),(4,5)])
sage: G1 == G2
True
sage: G1 == G3 or G1 == G4 or G1 == G5
False
"""
if type(self) is not type(other):
return False
return self._genera == other._genera and \
self._legs == other._legs and \
self._edges == other._edges
def __ne__(self, other):
return not (self == other)
def _graph(self):
if not self._mutable and self._graph_cache is not None:
return self._graph_cache
from collections import defaultdict
legs = defaultdict(list)
G = Graph(len(self._genera), loops=True, multiedges=False, weighted=True)
for li,lj in self._edges:
i = self.vertex(li)
j = self.vertex(lj)
if G.has_edge(i, j):
G.set_edge_label(i, j, G.edge_label(i, j) + 1)
else:
G.add_edge(i, j, 1)
if i < j:
legs[i,j].append((li,lj))
else:
legs[j,i].append((lj,li))
vertex_partition = defaultdict(list)
for i, (g,l) in enumerate(zip(self._genera, self._legs)):
l = list(self.list_markings(i))
l.sort()
inv = (g,) + tuple(l)
vertex_partition[inv].append(i)
vertex_data = sorted(vertex_partition)
partition = [vertex_partition[k] for k in vertex_data]
output = (G, vertex_data, dict(legs), partition)
if not self._mutable:
self._graph_cache = output
return output
def _canonical_label(self):
if not self._mutable and self._canonical_label_cache is not None:
return self._canonical_label_cache
G, _, _, partition = self._graph()
H, phi = G.canonical_label(partition=partition,
edge_labels=True,
certificate=True,
algorithm='sage')
output = (H, phi)
if not self._mutable:
self._canonical_label_cache = output
return output
def set_canonical_label(self, certificate=False):
r"""
Set canonical label to this stable graph.
The canonical labeling is such that two isomorphic graphs get relabeled
the same way. If certificate is true return a pair `dicv`, `dicl` of
mappings from the vertices and legs to the canonical ones.
EXAMPLES::
sage: from admcycles import StableGraph
sage: S = StableGraph([1,2,3], [[1,4,5],[2,6,7],[3,8,9]], [(4,6),(5,8),(7,9)])
sage: T = S.copy()
sage: T.set_canonical_label()
sage: T # random
[1, 2, 3] [[1, 4, 6], [2, 5, 8], [3, 7, 9]] [(4, 5), (6, 7), (8, 9)]
sage: assert S.is_isomorphic(T)
Check that isomorphic graphs get relabelled the same way::
sage: S0 = StableGraph([3,5], [[1,3,5,4],[2]], [(1,2),(3,5)], mutable=False)
sage: S1 = S0.copy()
sage: S2 = StableGraph([3,5], [[2,3,1,4],[5]], [(2,5),(3,1)], mutable=True)
sage: S3 = StableGraph([5,3], [[5],[2,3,4,1]], [(2,5),(3,1)], mutable=True)
sage: S1.set_canonical_label()
sage: S2.set_canonical_label()
sage: S3.set_canonical_label()
sage: assert S1 == S2 == S3
sage: assert S0.is_isomorphic(S1)
sage: S0 = StableGraph([1,2,3], [[1,4,5],[2,6,7],[3,8,9]], [(4,6),(5,8),(7,9)], mutable=False)
sage: S1 = S0.copy()
sage: S2 = StableGraph([3,2,1], [[3,8,5],[2,6,7],[1,4,9]], [(8,6),(5,4),(7,9)], mutable=True)
sage: S3 = StableGraph([2,1,3], [[7,2,5],[6,4,1],[3,9,8]], [(7,6),(5,8),(4,9)], mutable=True)
sage: S1.set_canonical_label()
sage: S2.set_canonical_label()
sage: S3.set_canonical_label()
sage: assert S1 == S2 == S3
sage: assert S0.is_isomorphic(S1)
sage: S0 = StableGraph([1,2,3], [[1,4,5],[2,6,7],[3,8,9]], [(4,6),(5,8),(7,9)], mutable=True)
sage: S1 = StableGraph([3,2,1], [[3,8,5],[2,6,7],[1,4,9]], [(8,6),(5,4),(7,9)], mutable=True)
sage: S2 = StableGraph([2,1,3], [[7,2,5],[6,4,1],[3,9,8]], [(7,6),(5,8),(4,9)], mutable=True)
sage: for S in [S0, S1, S2]:
....: T = S.copy()
....: assert S == T
....: vm, lm = T.set_canonical_label(certificate=True)
....: S.relabel(vm, lm, inplace=True)
....: S.tidy_up()
....: assert S == T, (S, T)
TESTS::
sage: from admcycles import StableGraph
sage: S0 = StableGraph([2], [[]], [], mutable=True)
sage: S0.set_canonical_label()
sage: S0 = StableGraph([0,1,0], [[1,2,4], [3], [5,6,7]], [(2,3), (4,5), (6,7)])
sage: S1 = S0.copy()
sage: S1.set_canonical_label()
sage: assert S0.is_isomorphic(S1)
sage: S2 = S1.copy()
sage: S1.set_canonical_label()
sage: assert S1 == S2
sage: S0 = StableGraph([1,0], [[2,3], [5,7,9]], [(2,5), (7,9)], mutable=True)
sage: S1 = StableGraph([1,0], [[1,3], [2,7,9]], [(1,2), (7,9)], mutable=True)
sage: S0.set_canonical_label()
sage: S1.set_canonical_label()
sage: assert S0 == S1
"""
if not self._mutable:
raise ValueError("the graph must be mutable; use inplace=False")
G, vdat, legs, part = self._graph()
H, dicv = self._canonical_label()
invdicv = {j:i for i,j in dicv.items()}
if certificate:
dicl = {}
new_genera = [self._genera[invdicv[i]] for i in range(self.num_verts())]
assert new_genera == sorted(self._genera)
new_legs = [sorted(self.list_markings(invdicv[i])) for i in range(self.num_verts())]
can_edges = []
for e0,e1,mult in G.edges():
f0 = dicv[e0]
f1 = dicv[e1]
inv = False
if f0 > f1:
f0,f1 = f1,f0
inv = True
can_edges.append((f0,f1,e0,e1,mult,inv))
can_edges.sort()
nl = self.num_legs()
marks = set(self.list_markings())
m0 = (max(marks) if marks else 0) + 1
non_markings = range(m0, m0 + nl - len(marks))
assert len(non_markings) == 2 * sum(mult for _,_,_,_,mult,_ in can_edges)
k = 0
new_edges = []
for f0,f1,e0,e1,mult,inv in can_edges:
assert f0 <= f1
new_legs[f0].extend(non_markings[i] for i in range(k, k+2*mult, 2))
new_legs[f1].extend(non_markings[i] for i in range(k+1, k+2*mult, 2))
new_edges.extend((non_markings[i], non_markings[i+1]) for i in range(k, k+2*mult, 2))
if certificate:
assert len(legs[e0, e1]) == mult, (len(legs[e0, e1]), mult)
if inv:
assert dicv[e0] == f1
assert dicv[e1] == f0
for i, (l1,l0) in enumerate(legs[e0,e1]):
dicl[l0] = non_markings[k + 2*i]
dicl[l1] = non_markings[k + 2*i + 1]
else:
assert dicv[e0] == f0
assert dicv[e1] == f1
for i, (l0,l1) in enumerate(legs[e0,e1]):
dicl[l0] = non_markings[k + 2*i]
dicl[l1] = non_markings[k + 2*i + 1]
k += 2*mult
self._genera = new_genera
self._legs = new_legs
self._edges = new_edges
if certificate:
return (dicv, dicl)
def relabel(self, vm, lm, inplace=False, mutable=False):
r"""
INPUT:
- ``vm`` -- (dictionary) a vertex map (from the label of this graph to
the new labels). If a vertex number is missing it will remain untouched.
- ``lm`` -- (dictionary) a leg map (idem). If a leg label is missing it
will remain untouched.
- ``inplace`` -- (boolean, default ``False``) whether to relabel the
graph inplace
- ``mutable`` -- (boolean, default ``False``) whether to make the
resulting graph immutable. Ignored when ``inplace=True``
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([3,5], [[1,3,5,4],[2]], [(1,2),(3,5)])
sage: vm = {0:1, 1:0}
sage: lm = {1:3, 2:5, 3:7, 4:9, 5:15}
sage: G.relabel(vm, lm)
[5, 3] [[5], [3, 7, 15, 9]] [(3, 5), (7, 15)]
sage: G.relabel(vm, lm, mutable=False).is_mutable()
False
sage: G.relabel(vm, lm, mutable=True).is_mutable()
True
sage: H = G.copy()
sage: H.relabel(vm, lm, inplace=True)
sage: H == G.relabel(vm, lm)
True
"""
m = len(self._genera)
genera = [None] * m
legs = [None] * m
for i,(g,l) in enumerate(zip(self._genera, self._legs)):
j = vm.get(i, i)
genera[j] = g
legs[j] = [lm.get(k, k) for k in l]
edges = [(lm.get(i, i), lm.get(j, j)) for i, j in self._edges]
if inplace:
self._genera = genera
self._legs = legs
self._edges = edges
else:
return StableGraph(genera, legs, edges, mutable)
def is_isomorphic(self, other, certificate=False):
r"""
Test whether this stable graph is isomorphic to ``other``.
INPUT:
- ``certificate`` - if set to ``True`` return also a vertex mapping and
a legs mapping
EXAMPLES::
sage: from admcycles import StableGraph
sage: G1 = StableGraph([3,5], [[1,3,5,4],[2]], [(1,2),(3,5)])
sage: G2 = StableGraph([3,5], [[2,3,1,4],[5]], [(2,5),(3,1)])
sage: G3 = StableGraph([5,3], [[5],[2,3,4,1]], [(2,5),(3,1)])
sage: G1.is_isomorphic(G2) and G1.is_isomorphic(G3)
True
Graphs with distinct markings are not isomorphic::
sage: G4 = StableGraph([3,5], [[1,3,5,4],[2]], [(1,2),(3,4)])
sage: G1.is_isomorphic(G4) or G2.is_isomorphic(G4) or G3.is_isomorphic(G4)
False
Graph with marking multiplicities::
sage: H1 = StableGraph([0], [[1,1]], [])
sage: H2 = StableGraph([0], [[1,1]], [])
sage: H1.is_isomorphic(H2)
True
sage: H3 = StableGraph([0,0], [[1,2,4],[1,3]], [(2,3)])
sage: H4 = StableGraph([0,0], [[1,2],[1,3,4]], [(2,3)])
sage: H3.is_isomorphic(H4)
True
TESTS::
sage: from admcycles import StableGraph
sage: G = StableGraph([0, 0], [[5, 8, 4, 3], [9, 2, 1]], [(8, 9)])
sage: H = StableGraph([0, 0], [[1, 2, 6], [3, 4, 5, 7]], [(6, 7)])
sage: G.is_isomorphic(H)
True
sage: ans, (vm, lm) = G.is_isomorphic(H, certificate=True)
sage: assert ans
sage: G.relabel(vm, lm)
[0, 0] [[6, 2, 1], [5, 7, 4, 3]] [(7, 6)]
sage: G = StableGraph([0, 0], [[4, 8, 2], [3, 9, 1]], [(8, 9)])
sage: H = StableGraph([0, 0], [[1, 3, 5], [2, 4, 6]], [(5, 6)])
sage: G.is_isomorphic(H)
True
sage: ans, (vm, lm) = G.is_isomorphic(H, certificate=True)
sage: assert ans
sage: G.relabel(vm, lm)
[0, 0] [[3, 5, 1], [4, 6, 2]] [(6, 5)]
sage: G = StableGraph([0, 1, 1], [[1, 3, 5], [2, 4], [6]], [(1, 2), (3, 4), (5, 6)])
sage: H = StableGraph([1, 0, 1], [[1], [2, 3, 5], [4, 6]], [(1, 2), (3, 4), (5, 6)])
sage: _ = G.is_isomorphic(H, certificate=True)
Check for https://gitlab.com/jo314schmitt/admcycles/issues/22::
sage: g1 = StableGraph([0, 0], [[1, 3], [2,4]], [(1, 2), (3, 4)])
sage: g2 = StableGraph([0, 0], [[1], [2]], [(1, 2)])
sage: g1.is_isomorphic(g2)
False
Check for https://gitlab.com/jo314schmitt/admcycles/issues/24::
sage: gr1 = StableGraph([0, 0, 0, 2, 1, 2], [[1, 2, 6], [3, 7, 8], [4, 5, 9], [10], [11], [12]], [(6, 7), (8, 9), (3, 10), (4, 11), (5, 12)])
sage: gr2 = StableGraph([0, 0, 1, 1, 1, 2], [[1, 2, 5, 6, 7], [3, 4, 8], [9], [10], [11], [12]], [(7, 8), (3, 9), (4, 10), (5, 11), (6, 12)])
sage: gr1.is_isomorphic(gr2)
False
"""
if type(self) != type(other):
raise TypeError
sG, svdat, slegs, spart = self._graph()
oG, ovdat, olegs, opart = other._graph()
if svdat != ovdat or any(len(p) != len(q) for p,q in zip(spart, opart)):
return (False, None) if certificate else False
sH, sphi = self._canonical_label()
oH, ophi = other._canonical_label()
if sH != oH:
return (False, None) if certificate else False
if certificate:
ophi_inv = {j: i for i,j in ophi.items()}
vertex_map = {i: ophi_inv[sphi[i]] for i in range(len(self._genera))}
legs_map = {}
for l in svdat:
for i in l[1:]:
legs_map[i] = i
for (i,j),sl in slegs.items():
m = sG.edge_label(i, j)
assert len(sl) == m, (m, sl, self, other)
ii = ophi_inv[sphi[i]]
jj = ophi_inv[sphi[j]]
if ii <= jj:
ol = olegs[ii,jj]
else:
ol = [(b,a) for (a,b) in olegs[jj,ii]]
assert len(ol) == m, (m, sl, ol, self, other)
for (a,b),(c,d) in zip(sl,ol):
legs_map[a] = c
legs_map[b] = d
return True, (vertex_map, legs_map)
else:
return True
def vertex_automorphism_group(self, *args, **kwds):
r"""
Return the action of the automorphism group on the vertices.
All arguments provided are forwarded to the method `automorphism_group`
of Sage graphs.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0], [[1, 2, 3, 4, 5, 6]], [(3, 4), (5, 6)])
sage: G.vertex_automorphism_group()
Permutation Group with generators [()]
sage: G = StableGraph([0, 0], [[1, 1, 2], [1, 1, 3]], [(2, 3)])
sage: G.vertex_automorphism_group()
Permutation Group with generators [(0,1)]
sage: G = StableGraph([0, 0], [[4, 1, 2], [1, 3, 4]], [(3, 2)])
sage: G.vertex_automorphism_group()
Permutation Group with generators [(0,1)]
sage: G = StableGraph([0, 0, 0], [[1,2], [3,4], [5,6]],
....: [(2,3),(4,5),(6,1)])
sage: A = G.vertex_automorphism_group()
sage: A
Permutation Group with generators [(1,2), (0,1)]
sage: A.cardinality()
6
Using extra arguments::
sage: G.vertex_automorphism_group(algorithm='sage')
Permutation Group with generators [(1,2), (0,1)]
sage: G.vertex_automorphism_group(algorithm='bliss') # optional - bliss
Permutation Group with generators [(1,2), (0,1)]
"""
G, _, _, partition = self._graph()
return G.automorphism_group(partition=partition,
edge_labels=True,
*args, **kwds)
def leg_automorphism_induce(self, g, A=None, check=True):
r"""
Given a leg automorphism ``g`` return its action on the vertices.
Note that there is no check that the element ``g`` is a valid automorphism.
INPUT:
- ``g`` - a permutation acting on the legs
- ``A`` - ambient permutation group for the result
- ``check`` - (default ``True``) parameter forwarded to the constructor
of the permutation group acting on vertices.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0, 0, 0, 0], [[1,8,9,16], [2,3,10,11], [4,5,12,13], [6,7,14,15]],
....: [(1,2),(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)])
sage: Averts = G.vertex_automorphism_group()
sage: Alegs = G.leg_automorphism_group()
sage: g = Alegs('(1,14)(2,13)(3,4)(5,10)(6,9)(7,8)(11,12)(15,16)')
sage: assert G.leg_automorphism_induce(g) == Averts('(0,3)(1,2)')
sage: g = Alegs('(3,11)(4,12)(5,13)(6,14)')
sage: assert G.leg_automorphism_induce(g) == Averts('')
sage: g = Alegs('(1,11,13,15,9,3,5,7)(2,12,14,16,10,4,6,8)')
sage: assert G.leg_automorphism_induce(g) == Averts('(0,1,2,3)')
TESTS::
sage: G = StableGraph([3], [[]], [])
sage: S = SymmetricGroup([0])
sage: G.leg_automorphism_induce(S(''))
()
"""
if A is None:
A = SymmetricGroup(list(range(len(self._genera))))
if len(self._genera) == 1:
return A('')
p = [self.vertex(g(self._legs[u][0])) for u in range(len(self._genera))]
return A(p, check=check)
def vertex_automorphism_lift(self, g, A=None, check=True):
r"""
Provide a canonical lift of vertex automorphism to leg automorphism.
Note that there is no check that ``g`` defines a valid automorphism of
the vertices.
INPUT::
- ``g`` - permutation automorphism of the vertices
- ``A`` - an optional permutation group in which the result belongs to
- ``check`` -- (default ``True``) parameter forwarded to the constructor
of the permutation group
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0, 0, 0, 0], [[1,8,9,16], [2,3,10,11], [4,5,12,13], [6,7,14,15]],
....: [(1,2),(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)])
sage: Averts = G.vertex_automorphism_group()
sage: G.vertex_automorphism_lift(Averts(''))
()
sage: G.vertex_automorphism_lift(Averts('(0,3)(1,2)'))
(1,6)(2,5)(3,4)(7,8)(9,14)(10,13)(11,12)(15,16)
sage: G.vertex_automorphism_lift(Averts('(0,1,2,3)'))
(1,3,5,7)(2,4,6,8)(9,11,13,15)(10,12,14,16)
"""
p = sorted(sum(self._legs, []))
if A is None:
A = SymmetricGroup(p)
leg_pos = {j:i for i,j in enumerate(p)}
G, _, edge_to_legs, partition = self._graph()
for u,v,lab in G.edges():
gu = g(u)
gv = g(v)
if u < v:
start = edge_to_legs[u,v]
else:
start = [(t,s) for s,t in edge_to_legs[v,u]]
if gu < gv:
end = edge_to_legs[gu,gv]
else:
end = [(t,s) for s,t in edge_to_legs[gv,gu]]
for (lu, lv), (glu, glv) in zip(start, end):
p[leg_pos[lu]] = glu
p[leg_pos[lv]] = glv
return A(p, check=check)
def leg_automorphism_group_vertex_stabilizer(self, *args, **kwds):
r"""
Return the group of automorphisms of this stable graph stabilizing the vertices.
All arguments are forwarded to the subgroup method of the Sage symmetric group.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0],[[1,2,3,4,5,6,7,8]], [(1,2),(3,4),(5,6),(7,8)])
sage: G.leg_automorphism_group_vertex_stabilizer()
Subgroup generated by [(1,2), (1,3)(2,4), (1,3,5,7)(2,4,6,8)] of (Symmetric group of order 8! as a permutation group)
sage: G = StableGraph([1,1],[[1,2],[3,4]], [(1,3),(2,4)])
sage: G.leg_automorphism_group_vertex_stabilizer()
Subgroup generated by [(1,2)(3,4)] of (Symmetric group of order 4! as a permutation group)
"""
legs = sorted(sum(self._legs, []))
G, _, edge_to_legs, partition = self._graph()
S = SymmetricGroup(legs)
gens = []
for u,v,lab in G.edges():
if lab == 1 and u != v:
continue
if u < v:
multiedge = edge_to_legs[u,v]
else:
multiedge = edge_to_legs[v,u]
if lab >= 2:
(lu0, lv0) = multiedge[0]
(lu1, lv1) = multiedge[1]
gens.append( S.element_class([(lu0, lu1), (lv0, lv1)], S, check=False) )
if lab >= 3:
gens.append( S.element_class([ tuple(x for x,y in multiedge),
tuple(y for x,y in multiedge) ], S, check=False) )
if u == v:
(lu, lv) = multiedge[0]
gens.append( S.element_class([ (lu, lv) ], S, check=False) )
return S.subgroup(gens, *args, **kwds)
def leg_automorphism_group(self, *args, **kwds):
r"""
Return the action of the automorphism group on the legs.
The arguments provided to this function are forwarded to the
constructor of the subgroup of the symmetric group.
EXAMPLES::
sage: from admcycles import StableGraph
A triangle::
sage: G = StableGraph([0, 0, 0], [[1,2], [3,4], [5,6]],
....: [(2,3),(4,5),(6,1)])
sage: Alegs = G.leg_automorphism_group()
sage: assert Alegs.cardinality() == G.automorphism_number()
A vertex with four loops::
sage: G = StableGraph([0], [[1,2,3,4,5,6,7,8]], [(1,2),(3,4),(5,6),(7,8)])
sage: Alegs = G.leg_automorphism_group()
sage: assert Alegs.cardinality() == G.automorphism_number()
sage: a = Alegs.random_element()
Using extra arguments::
sage: G = StableGraph([0,0,0], [[6,1,7,8],[2,3,9,10],[4,5,11,12]],
....: [(1,2), (3,4), (5,6), (7,8), (9,10), (11,12)])
sage: G.leg_automorphism_group()
Subgroup generated by [(11,12), (9,10), (7,8), (1,2)(3,6)(4,5)(7,9)(8,10), (1,6)(2,5)(3,4)(9,11)(10,12)] of (Symmetric group of order 12! as a permutation group)
sage: G.leg_automorphism_group(canonicalize=False)
Subgroup generated by [(1,6)(2,5)(3,4)(9,11)(10,12), (1,2)(3,6)(4,5)(7,9)(8,10), (11,12), (9,10), (7,8)] of (Symmetric group of order 12! as a permutation group)
"""
legs = sorted(sum(self._legs, []))
G, _, edge_to_legs, partition = self._graph()
S = SymmetricGroup(legs)
gens = []
for g in self.vertex_automorphism_group().gens():
gens.append(self.vertex_automorphism_lift(g, S))
for g in self.leg_automorphism_group_vertex_stabilizer().gens():
gens.append(g)
return S.subgroup(gens, *args, **kwds)
def automorphism_number(self):
r"""
Return the size of the automorphism group (acting on legs).
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0, 2], [[1, 2, 4], [3, 5]], [(4, 5)])
sage: G.automorphism_number()
1
sage: G = StableGraph([0, 0, 0], [[1,2,7,8], [3,4,9,10], [5,6,11,12]],
....: [(2,3),(4,5),(6,1),(8,9),(10,11),(12,7)])
sage: G.automorphism_number()
48
sage: G.leg_automorphism_group().cardinality()
48
sage: G = StableGraph([0, 0], [[1, 1, 2], [1, 1, 3]], [(2, 3)])
sage: G.automorphism_number()
Traceback (most recent call last):
...
NotImplementedError: automorphism_number not valid for repeated marking
"""
G, _, _, _ = self._graph()
aut = self.vertex_automorphism_group().cardinality()
for i,j,lab in G.edges():
aut *= factorial(lab)
if i == j:
aut *= 2**lab
markings = self.list_markings()
if len(markings) != len(set(markings)):
raise NotImplementedError("automorphism_number not valid for repeated marking")
return aut
def g(self):
r"""
Return the genus of this stable graph
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([1,2],[[1,2], [3,4]], [(1,3),(2,4)])
sage: G.g()
4
"""
return sum(self._genera) + len(self._edges) - len(self._genera) + ZZ.one()
def n(self):
r"""
Return the number of legs of the stable graph.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([1,2],[[1,2],[3,4,5,6]],[(1,3),(2,4)]);G.n()
2
"""
return len(self.list_markings())
def genera(self, i=None, copy=True):
"""
Return the list of genera of the stable graph.
If an integer argument is given, return the genus at this vertex.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([1,2],[[1,2],[3,4,5,6]],[(1,3),(2,4)])
sage: G.genera()
[1, 2]
sage: G.genera(0), G.genera(1)
(1, 2)
"""
if i is None:
return self._genera[:] if copy else self._genera
else:
return self._genera[i]
def edges(self, copy=True):
return self._edges[:] if copy else self._edges
def num_verts(self):
return len(self._genera)
def legs(self, v=None, copy=True):
if v is None:
return [l[:] for l in self._legs] if copy else self._legs
else:
return self._legs[v][:] if copy else self._legs[v]
numvert = num_verts
def num_edges(self):
r"""
Return the number of edges.
"""
return len(self._edges)
def num_loops(self):
r"""
Return the number of loops (ie edges attached twice to a vertex).
"""
n = 0
for h0,h1 in self._edges:
n += self.vertex(h0) == self.vertex(h1)
return n
def num_legs(self, i=None):
r"""
Return the number of legs.
"""
if i is None:
return sum(len(l) for l in self._legs)
else:
return len(self._legs[i])
def _graph_(self):
r"""
Return the Sage graph object encoding the stable graph
This inserts a vertex with label (i,j) in the middle of the edge (i,j).
Also inserts a vertex with label ('L',i) at the end of each leg l.
EXAMPLES::
sage: from admcycles import StableGraph
sage: Gr = StableGraph([3,5],[[1,3,5,7],[2]],[(1,2),(3,5)])
sage: SageGr = Gr._graph_()
sage: SageGr
Multi-graph on 5 vertices
sage: SageGr.vertices(sort=False) # random
[(1, 2), 0, 1, (3, 5), ('L', 7)]
"""
G = Graph(multiedges=True)
for i, j in self._edges:
G.add_vertex((i, j))
G.add_edge((i, j), self.vertex(i))
G.add_edge((i, j), self.vertex(j))
for i in self.list_markings():
G.add_edge(('L', i), self.vertex(i))
return G
def dim(self, v=None):
"""
Return dimension of moduli space at vertex v.
If v=None, return dimension of entire stratum parametrized by graph.
EXAMPLES::
sage: from admcycles import StableGraph
sage: Gr = StableGraph([3,5],[[1,3,5,7],[2]],[(1,2),(3,5)])
sage: Gr.dim(0), Gr.dim(1), Gr.dim()
(10, 13, 23)
"""
if v is None:
return sum([self.dim(v) for v in range(len(self._genera))])
return 3 * self._genera[v] - 3 + len(self._legs[v])
def invariant(self):
r"""
Return a graph-invariant in form of a tuple of integers or tuples
At the moment this assumes that we only compare stable graph with same total
g and set of markings
currently returns sorted list of (genus,degree) for vertices
IDEAS:
* number of self-loops for each vertex
EXAMPLES::
sage: from admcycles import StableGraph
sage: Gr = StableGraph([3,5],[[1,3,5,7],[2]],[(1,2),(3,5)])
sage: Gr.invariant()
((3, 4, (7,)), (5, 1, ()))
"""
return tuple(sorted([(self._genera[v], len(self._legs[v]), tuple(sorted(self.list_markings(v)))) for v in range(len(self._genera))]))
def tidy_up(self):
r"""
Sort legs and edges.
EXAMPLES::
sage: from admcycles import StableGraph
sage: S = StableGraph([1, 3, 2], [[1, 5, 4], [2, 3, 6], [9, 8, 7]], [(9,3), (1,2)], mutable=True)
sage: S.tidy_up()
sage: S
[1, 3, 2] [[1, 4, 5], [2, 3, 6], [7, 8, 9]] [(1, 2), (3, 9)]
"""
if not self._mutable:
raise ValueError("the graph is immutable; use a copy instead")
for e in range(len(self._edges)):
if self._edges[e][0] > self._edges[e][1]:
self._edges[e] = (self._edges[e][1],self._edges[e][0])
for legs in self._legs:
legs.sort()
self._edges.sort()
self._maxleg = max([max(j+[0]) for j in self._legs])
def vertex(self, l):
r"""
Return vertex number of leg l
"""
for v in range(len(self._legs)):
if l in self._legs[v]:
return v
return -1
def list_markings(self, v=None):
r"""
Return the list of markings (non-edge legs) of self at vertex v.
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.list_markings(0)
(3, 7)
sage: gam.list_markings()
(3, 7, 4)
"""
if v is None:
return tuple([j for v in range(len(self._genera))
for j in self.list_markings(v)])
s = set(self._legs[v])
for e in self._edges:
s -= set(e)
return tuple(s)
def leglist(self):
r"""
Return the list of legs
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.leglist()
[1, 3, 7, 2, 4]
"""
return [j for leg in self._legs for j in leg]
def halfedges(self):
r"""
Return the tuple containing all half-edges, i.e. legs belonging to an edge
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.halfedges()
(1, 2)
"""
return tuple(j for ed in self._edges for j in ed)
def edges_between(self, i, j):
r"""
Return the list [(l1,k1),(l2,k2), ...] of edges from i to j, where l1 in i, l2 in j; for i==j return each edge only once
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.edges_between(0, 1)
[(1, 2)]
sage: gam.edges_between(0, 0)
[]
"""
if i == j:
return [e for e in self._edges if (e[0] in self._legs[i] and e[1] in self._legs[j] ) ]
else:
return [e for e in self._edges if (e[0] in self._legs[i] and e[1] in self._legs[j] ) ]+ [(e[1],e[0]) for e in self._edges if (e[0] in self._legs[j] and e[1] in self._legs[i] ) ]
def forget_markings(self, markings):
r"""
Erase all legs in the list markings, do not check if this gives well-defined graph
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
for m in markings:
self._legs[self.vertex(m)].remove(m)
return self
def leginversion(self, l):
r"""
Returns l' if l and l' form an edge, otherwise returns l
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.leginversion(1)
2
"""
for a, b in self._edges:
if a == l:
return b
if b == l:
return a
return l
def stabilize(self):
r"""
Stabilize this stable graph.
(all vertices with genus 0 have at least three markings) and returns
``(dicv,dicl,dich)`` where
- dicv a dictionary sending new vertex numbers to the corresponding old
vertex numbers
- dicl a dictionary sending new marking names to the label of the last
half-edge that they replaced during the stabilization this happens
for instance if a g=0 vertex with marking m and half-edge l
(belonging to edge (l,l')) is stabilized: l' is replaced by m, so
dicl[m]=l'
- dich a dictionary sending half-edges that vanished in the
stabilization process to the last half-edge that replaced them this
happens if a g=0 vertex with two half-edges a,b (whose corresponding
half-edges are c,d) is stabilized: we obtain an edge (c,d) and a ->
d, b -> d we assume here that a stabilization exists (all connected
components have 2g-2+n>0)
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)], mutable=True)
sage: gam.stabilize()
({0: 0, 1: 1}, {}, {})
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.stabilize()
Traceback (most recent call last):
...
ValueError: the graph is not mutable; use a copy instead
sage: g = StableGraph([0,0,0], [[1,5,6],[2,3],[4,7,8]], [(1,2),(3,4),(5,6),(7,8)], mutable=True)
sage: g.stabilize()
({0: 0, 1: 2}, {}, {2: 4, 3: 1})
sage: h = StableGraph([0, 0, 0], [[1], [2,3], [4]], [(1,2), (3,4)], mutable=True)
sage: h.stabilize()
({0: 2}, {}, {})
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
markings = self.list_markings()
stable = False
verteximages = list(range(len(self._genera)))
dicl = {}
dich = {}
while not stable:
numvert = len(self._genera)
count = 0
stable = True
while count < numvert:
if self._genera[count] == 0 and len(self._legs[count]) == 1:
stable = False
e0 = self._legs[count][0]
e1 = self.leginversion(e0)
v1 = self.vertex(e1)
self._genera.pop(count)
verteximages.pop(count)
numvert -= 1
self._legs[v1].remove(e1)
self._legs.pop(count)
try:
self._edges.remove((e0,e1))
except:
self._edges.remove((e1,e0))
elif self._genera[count] == 0 and len(self._legs[count]) == 2:
stable = False
e0 = self._legs[count][0]
e1 = self._legs[count][1]
if e1 in markings:
swap = e0
e0 = e1
e1 = swap
e1prime = self.leginversion(e1)
v1 = self.vertex(e1prime)
self._genera.pop(count)
verteximages.pop(count)
numvert -= 1
if e0 in markings:
dicl[e0] = e1prime
self._legs[v1].remove(e1prime)
self._legs[v1].append(e0)
self._legs.pop(count)
try:
self._edges.remove((e1,e1prime))
except:
self._edges.remove((e1prime,e1))
else:
e0prime = self.leginversion(e0)
self._legs.pop(count)
try:
self._edges.remove((e0,e0prime))
except:
self._edges.remove((e0prime,e0))
try:
self._edges.remove((e1,e1prime))
except:
self._edges.remove((e1prime,e1))
self._edges.append((e0prime,e1prime))
dich[e0] = e1prime
dich[e1] = e0prime
dich.update({h:e1prime for h in dich if dich[h]==e0})
dich.update({h:e0prime for h in dich if dich[h]==e1})
else:
count += 1
return ({i:verteximages[i] for i in range(len(verteximages))},dicl,dich)
def degenerations(self, v=None, mutable=False):
r"""
Run through the list of all possible degenerations of this graph.
A degeneration happens by adding an edge at v or splitting it
into two vertices connected by an edge the new edge always
comes last in the list of edges.
If v is None, return all degenerations at all vertices.
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: list(gam.degenerations(1))
[[3, 4] [[1, 3, 7], [2, 4, 8, 9]] [(1, 2), (8, 9)],
[3, 0, 5] [[1, 3, 7], [2, 4, 8], [9]] [(1, 2), (8, 9)],
[3, 1, 4] [[1, 3, 7], [8], [2, 4, 9]] [(1, 2), (8, 9)],
[3, 1, 4] [[1, 3, 7], [2, 8], [4, 9]] [(1, 2), (8, 9)],
[3, 1, 4] [[1, 3, 7], [4, 8], [2, 9]] [(1, 2), (8, 9)],
[3, 1, 4] [[1, 3, 7], [2, 4, 8], [9]] [(1, 2), (8, 9)],
[3, 2, 3] [[1, 3, 7], [8], [2, 4, 9]] [(1, 2), (8, 9)],
[3, 2, 3] [[1, 3, 7], [2, 8], [4, 9]] [(1, 2), (8, 9)],
[3, 2, 3] [[1, 3, 7], [4, 8], [2, 9]] [(1, 2), (8, 9)],
[3, 2, 3] [[1, 3, 7], [2, 4, 8], [9]] [(1, 2), (8, 9)]]
All these graphs are immutable (or mutable when ``mutable=True``)::
sage: any(g.is_mutable() for g in gam.degenerations())
False
sage: all(g.is_mutable() for g in gam.degenerations(mutable=True))
True
TESTS::
sage: from admcycles import StableGraph
sage: G = StableGraph([2,2,2], [[1],[2,3],[4]], [(1,2),(3,4)])
sage: sum(1 for v in range(3) for _ in G.degenerations(v))
8
sage: sum(1 for _ in G.degenerations())
8
"""
if v is None:
for v in range(self.num_verts()):
for h in self.degenerations(v, mutable):
yield h
return
g = self._genera[v]
l = len(self._legs[v])
if g > 0:
G = self.copy()
G.degenerate_nonsep(v)
if not mutable:
G.set_immutable()
yield G
for g1 in range(floor(g/2)+1):
for M in Subsets(set(self._legs[v])):
if (g1 == 0 and len(M) < 2) or \
(g == g1 and l-len(M) < 2) or \
(2*g1 == g and l > 0 and (not self._legs[v][0] in M)):
continue
G = self.copy()
G.degenerate_sep(v,g1,M)
if not mutable:
G.set_immutable()
yield G
def newleg(self):
r"""
Create two new leg-indices that can be used to create an edge
This modifies ``self._maxleg``.
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.newleg()
(8, 9)
"""
self._maxleg += 2
return (self._maxleg - 1, self._maxleg)
def rename_legs(self, di, shift=0):
r"""
Renames legs according to dictionary di, all other leg labels are shifted by shift (useful to keep half-edge labels separate from legs)
TODO: no check that this renaming is legal, i.e. produces well-defined graph
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
for v in self._legs:
for j in range(len(v)):
v[j] = di.get(v[j],v[j]+shift)
for e in range(len(self._edges)):
self._edges[e] = (di.get(self._edges[e][0],self._edges[e][0]+shift) ,di.get(self._edges[e][1],self._edges[e][1]+shift))
self.tidy_up()
def degenerate_sep(self, v, g1, M):
r"""
degenerate vertex v into two vertices with genera g1 and g(v)-g1 and legs M and complement
add new edge (e[0],e[1]) such that e[0] is in new vertex v, e[1] in last vertex, which is added
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)], mutable=True)
sage: G.degenerate_sep(1, 2, [4])
sage: G
[3, 2, 3] [[1, 3, 7], [4, 8], [2, 9]] [(1, 2), (8, 9)]
sage: G = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: G.degenerate_sep(1, 2, [4])
Traceback (most recent call last):
...
ValueError: the graph is not mutable; use a copy instead
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
g = self._genera[v]
oldleg = self._legs[v]
e = self.newleg()
self._genera[v] = g1
self._genera += [g-g1]
self._legs[v] = list(M)+[e[0]]
self._legs += [list(set(oldleg)-set(M))+[e[1]]]
self._edges += [e]
def degenerate_nonsep(self, v):
"""
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)], mutable=True)
sage: G.degenerate_nonsep(1)
sage: G
[3, 4] [[1, 3, 7], [2, 4, 8, 9]] [(1, 2), (8, 9)]
sage: G = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: G.degenerate_nonsep(1)
Traceback (most recent call last):
...
ValueError: the graph is not mutable; use a copy instead
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
e = self.newleg()
self._genera[v] -= 1
self._legs[v] += [e[0], e[1]]
self._edges += [e]
def contract_edge(self, e, adddata=False):
r"""
Contracts the edge e=(e0,e1).
This method returns nothing by default. But if ``adddata`` is set to
``True``, then it returns a tuple ``(av, edgegraph, vnum)`` where
- ``av`` is the the vertex in the modified graph on which previously
the edge ``e`` had been attached
- ``edgegraph`` is a stable graph induced in self by the edge e
(1-edge graph, all legs at the ends of this edge are considered as
markings)
- ``vnum`` is a list of one or two vertices e was attached before the
contraction (in the order in which they appear)
- ``diccv`` is a dictionary mapping old vertex numbers to new vertex
numbers
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2),(3,7)], mutable=True)
sage: G.contract_edge((1,2))
sage: G
[8] [[3, 7, 4]] [(3, 7)]
sage: G.contract_edge((3,7))
sage: G
[9] [[4]] []
sage: G2 = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2),(3,7)], mutable=True)
sage: G2.contract_edge((3,7))
sage: G2.contract_edge((1,2))
sage: G == G2
True
sage: G2 = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2),(3,7)], mutable=True)
sage: G2.contract_edge((3,7), adddata=True)
(0, [3] [[1, 3, 7]] [(3, 7)], [0], {0: 0, 1: 1})
sage: G = StableGraph([1,1,1,1],[[1],[2,4],[3,5],[6]],[(1,2),(3,4),(5,6)],mutable=True)
sage: G.contract_edge((3,4),True)
(1, [1, 1] [[2, 4], [3, 5]] [(3, 4)], [1, 2], {0: 0, 1: 1, 2: 1, 3: 2})
sage: G = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: G.contract_edge((1,2))
Traceback (most recent call last):
...
ValueError: the graph is not mutable; use a copy instead
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
v0 = self.vertex(e[0])
v1 = self.vertex(e[1])
if v0 == v1:
if adddata:
H = StableGraph([self._genera[v0]], [self._legs[v0][:]], [e])
self._genera[v0] += 1
self._legs[v0].remove(e[0])
self._legs[v0].remove(e[1])
self._edges.remove(e)
if adddata:
return (v0, H, [v0], {v:v for v in range(len(self._genera))})
else:
if v0 > v1:
v0, v1 = v1, v0
if adddata:
diccv = {v:v for v in range(v1)}
diccv[v1] = v0
diccv.update({v:v-1 for v in range(v1+1, len(self._genera))})
H = StableGraph([self._genera[v0],self._genera[v1]], [self._legs[v0][:], self._legs[v1][:]], [e])
g1 = self._genera.pop(v1)
self._genera[v0] += g1
l1 = self._legs.pop(v1)
self._legs[v0]+=l1
self._legs[v0].remove(e[0])
self._legs[v0].remove(e[1])
self._edges.remove(e)
if adddata:
return (v0, H, [v0,v1], diccv)
def glue_vertex(self, i, Gr, divGr={}, divs={}, dil={}):
r"""
Glues the stable graph ``Gr`` at the vertex ``i`` of this stable graph
optional arguments: if divGr/dil are given they are supposed to be a
dictionary, which will be cleared and updated with the
renaming-convention to pass from leg/vertex-names in Gr to
leg/vertex-names in the glued graph similarly, divs will be a
dictionary assigning vertex numbers in the old self the corresponding
number in the new self necessary condition:
- every leg of i is also a leg in Gr
- every leg of Gr that is not a leg of i in self gets a new name
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
divGr.clear()
divs.clear()
dil.clear()
selfedges_old = self.edges_between(i,i)
self._genera.pop(i)
legs_old = self._legs.pop(i)
for e in selfedges_old:
self._edges.remove(e)
m = max(self._maxleg, Gr._maxleg)
Gr_new = Gr.copy()
a = []
for l in Gr._legs:
a += l
a = set(a)
b = set(legs_old)
e = a - b
for l in e:
m += 1
dil[l] = m
Gr_new.rename_legs(dil)
for j in range(i):
divs[j] = j
for j in range(i+1, len(self._genera)+1):
divs[j] = j-1
for j in range(len(Gr._genera)):
divGr[j] = len(self._genera)+j
self._genera += Gr_new._genera
self._legs += Gr_new._legs
self._edges += Gr_new._edges
self.tidy_up()
def reorder_vertices(self, vord):
r"""
Reorders vertices according to tuple given (permutation of range(len(self._genera)))
"""
if not self._mutable:
raise ValueError("the graph is not mutable; use a copy instead")
new_genera=[self._genera[j] for j in vord]
new_legs=[self._legs[j] for j in vord]
self._genera=new_genera
self._legs=new_legs
def extract_subgraph(self, vertices, outgoing_legs=None, rename=True, mutable=False):
r"""
Extracts from self a subgraph induced by the list vertices
if the list outgoing_legs is given, the markings of the subgraph are
called 1,2,..,m corresponding to the elements of outgoing_legs in this
case, all edges involving outgoing edges should be cut returns a triple
(Gamma,dicv,dicl), where
- Gamma is the induced subgraph
- dicv, dicl are (surjective) dictionaries associating vertex/leg
labels in self to the vertex/leg labels in Gamma
if ``rename=False``, do not rename any legs when extracting
EXAMPLES::
sage: from admcycles import StableGraph
sage: gam = StableGraph([3,5],[[1,3,7],[2,4]],[(1,2)])
sage: gam.extract_subgraph([0])
([3] [[1, 2, 3]] [], {0: 0}, {1: 1, 3: 2, 7: 3})
"""
attachedlegs = set(l for v in vertices for l in self._legs[v])
if outgoing_legs is None:
alllegs = attachedlegs.copy()
for (e0,e1) in self._edges:
if e0 in alllegs and e1 in alllegs:
alllegs.remove(e0)
alllegs.remove(e1)
outgoing_legs=list(alllegs)
shift = len(outgoing_legs) + 1
if rename:
dicl={outgoing_legs[i]:i+1 for i in range(shift-1)}
else:
dicl={l:l for l in self.leglist()}
genera = [self._genera[v] for v in vertices]
legs = [[dicl.setdefault(l,l+shift) for l in self._legs[v]] for v in vertices]
edges = [(dicl[e0],dicl[e1]) for (e0,e1) in self._edges if (e0 in attachedlegs and e1 in attachedlegs and (e0 not in outgoing_legs) and (e1 not in outgoing_legs))]
dicv={vertices[i]:i for i in range(len(vertices))}
return (StableGraph(genera, legs, edges, mutable=mutable), dicv, dicl)
def boundary_pushforward(self, classes=None):
r"""
Computes the pushforward of a product of tautological classes (one for each vertex) under the
boundary gluing map for this stable graph.
INPUT:
- ``classes`` -- list (default: `None`); list of tautclasses, one for each vertex of the stable
graph. The genus of the ith class is assumed to be the genus of the ith vertex, the markings
of the ith class are supposed to be 1, ..., ni where ni is the number of legs at the ith vertex.
Note: the jth leg at vertex i corresponds to the marking j of the ith class.
For classes=None, place the fundamental class at each vertex.
EXAMPLES::
sage: from admcycles import StableGraph, psiclass, fundclass
sage: B=StableGraph([2,1],[[4,1,2],[3,5]],[(4,5)])
sage: Bclass=B.boundary_pushforward() # class of undecorated boundary divisor
sage: Bclass*Bclass
Graph : [2, 1] [[4, 1, 2], [3, 5]] [(4, 5)]
Polynomial : (-1)*psi_5^1
<BLANKLINE>
Graph : [2, 1] [[4, 1, 2], [3, 5]] [(4, 5)]
Polynomial : (-1)*psi_4^1
sage: si1=B.boundary_pushforward([fundclass(2,3),-psiclass(2,1,2)]); si1
Graph : [2, 1] [[4, 1, 2], [3, 5]] [(4, 5)]
Polynomial : (-1)*psi_5^1
sage: si2=B.boundary_pushforward([-psiclass(1,2,3),fundclass(1,2)]); si2
Graph : [2, 1] [[4, 1, 2], [3, 5]] [(4, 5)]
Polynomial : (-1)*psi_4^1
sage: (Bclass*Bclass-si1-si2).simplify()
<BLANKLINE>
"""
from .admcycles import prodtautclass
return prodtautclass(self.copy(mutable=False), protaut=classes).pushforward()
def boundary_pullback(self,other):
r"""
pulls back the tautclass/decstratum other to self and returns a prodtautclass with gamma=self
"""
from .admcycles import tautclass, decstratum
if isinstance(other,tautclass):
from .admcycles import prodtautclass
result = prodtautclass(self.copy(mutable=False), [])
for t in other.terms:
result+=self.boundary_pullback(t)
return result
if isinstance(other,decstratum):
from .admcycles import (common_degenerations, prodtautclass,
onekppoly, kppoly, kappacl, psicl)
commdeg = common_degenerations(self, other.gamma, modiso=True)
result = prodtautclass(self.copy(mutable=False), [])
for (Gamma,dicv1,dicl1,dicv2,dicl2) in commdeg:
numvert = len(Gamma._genera)
legcount = {l:0 for l in Gamma.leglist()}
for l in dicl1.values():
legcount[l] += 1
for l in dicl2.values():
legcount[l] += 1
excesspoly = onekppoly(numvert)
for e in Gamma._edges:
if legcount[e[0]] == 2:
excesspoly*=( (-1)*(psicl(e[0],numvert) + psicl(e[1],numvert)) )
v1preim=[[] for v in range(len(self._genera))]
for w in dicv1:
v1preim[dicv1[w]].append(w)
graphpartition = [Gamma.extract_subgraph(v1preim[v],outgoing_legs=[dicl1[l] for l in self._legs[v]]) for v in range(len(self._genera))]
v2preim = [[] for v in range(len(other.gamma._genera))]
for w in dicv2:
v2preim[dicv2[w]].append(w)
resultpoly = kppoly([],[])
for (kappa,psi,coeff) in other.poly:
psipolydict = {dicl2[l]: psi[l] for l in psi}
psipoly = kppoly([([[] for i in range(numvert)],psipolydict)],[1])
kappapoly = prod([prod([sum([kappacl(w,k+1,numvert) for w in v2preim[v] ])**kappa[v][k] for k in range(len(kappa[v]))]) for v in range(len(other.gamma._genera))])
resultpoly += coeff*psipoly*kappapoly
resultpoly *= excesspoly
for (kappa,psi,coeff) in resultpoly:
decstratlist = []
for v in range(len(self._genera)):
kappav = [kappa[w] for w in v1preim[v]]
psiv = {graphpartition[v][2][l] : psi[l] for l in graphpartition[v][2] if l in psi}
decstratlist.append(decstratum(graphpartition[v][0],kappa=kappav,psi=psiv))
tempresu = prodtautclass(self,[decstratlist])
tempresu *= coeff
result += tempresu
return result
def to_tautclass(self):
r"""
Returns pure boundary stratum associated to self; note: does not divide by automorphisms!
"""
from .admcycles import tautclass, decstratum
return tautclass([decstratum(self)])
def _vertex_module(self):
nv = len(self._genera)
return FreeModule(ZZ, nv)
def _edge_module(self):
ne = len(self._edges)
return FreeModule(ZZ, ne)
def spanning_tree(self, root=0):
r"""
Return a spanning tree.
INPUT:
- ``root`` - optional vertex for the root of the spanning tree
OUTPUT: a triple
- list of triples ``(vertex ancestor, sign, edge index)`` where the
triple at position ``i`` correspond to vertex ``i``.
- the set of indices of extra edges not in the tree
- vertices sorted according to their heights in the tree (first element is the root
and the end of the list are the leaves). In other words, a topological sort of
the vertices with respect to the spanning tree.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0,0,0], [[1,2],[3,4,5],[6,7]], [(1,3),(4,6),(5,7)])
sage: G.spanning_tree()
([None, (0, -1, 0), (1, -1, 1)], {2}, [0, 1, 2])
sage: G.spanning_tree(1)
([(1, 1, 0), None, (1, -1, 1)], {2}, [1, 0, 2])
sage: G.spanning_tree(2)
([(1, 1, 0), (2, 1, 1), None], {2}, [2, 1, 0])
"""
from collections import deque
nv = len(self._genera)
ne = len(self._edges)
out_edges = [[] for _ in range(nv)]
for i,(lu,lv) in enumerate(self._edges):
u = self.vertex(lu)
v = self.vertex(lv)
out_edges[u].append((v, -1, i))
out_edges[v].append((u, 1, i))
ancestors = [None] * nv
ancestors[root] = None
unseen = [True] * nv
unseen[root] = False
todo = deque()
todo.append(root)
extra_edges = set(range(ne))
vertices = [root]
while todo:
u = todo.popleft()
for v,s,i in out_edges[u]:
if unseen[v]:
ancestors[v] = (u,s,i)
todo.append(v)
unseen[v] = False
extra_edges.remove(i)
vertices.append(v)
return ancestors, extra_edges, vertices
def cycle_basis(self):
r"""
Return a basis of the cycles as vectors of length the number of edges in the graph.
The coefficient at a given index in a vector corresponds to the edge
of this index in the list of edges of the stable graph. The coefficient is
+1 or -1 depending on the orientation of the edge in the cycle.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0,0,0], [[1,2,3], [4,5,6], [7,8]], [(1,4),(5,2),(3,7),(6,8)])
sage: G.cycle_basis()
[(1, 1, 0, 0), (1, 0, -1, 1)]
"""
ne = len(self._edges)
V = self._edge_module()
ancestors, extra_edges, _ = self.spanning_tree()
basis = []
for i in extra_edges:
vec = [0] * ne
vec[i] = 1
lu,lv = self._edges[i]
u = self.vertex(lu)
v = self.vertex(lv)
while ancestors[u] is not None:
u, s, i = ancestors[u]
vec[i] -= s
while ancestors[v] is not None:
v, s, i = ancestors[v]
vec[i] += s
basis.append(V(vec))
return basis
def cycle_space(self):
r"""
Return the subspace of the edge module generated by the cycles.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0,0,0], [[1,2,3], [4,5,6], [7,8]], [(1,4),(5,2),(3,7),(6,8)])
sage: C = G.cycle_space()
sage: C
Free module of degree 4 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1 0 -1 1]
[ 0 1 1 -1]
sage: G.flow_divergence(C.random_element()).is_zero()
True
"""
return self._edge_module().submodule(self.cycle_basis())
def flow_divergence(self, flow):
r"""
Return the divergence of the given ``flow``.
The divergence at a given vertex is the sum of the flow on the outgoing
edges at this vertex.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([1,0,0], [[1,2],[3,4,5,6],[7,8]], [(1,3),(4,2),(5,8),(7,6)])
sage: G.flow_divergence([1,1,1,1])
(0, 0, 0)
sage: G.flow_divergence([1,0,0,0])
(1, -1, 0)
"""
flow = self._edge_module()(flow)
deriv = self._vertex_module()()
for i, (lu, lv) in enumerate(self._edges):
u = self.vertex(lu)
v = self.vertex(lv)
deriv[u] += flow[i]
deriv[v] -= flow[i]
return deriv
def flow_solve(self, vertex_weights):
r"""
Return a solution for the flow equation with given vertex weights.
EXAMPLES::
sage: from admcycles import StableGraph
sage: G = StableGraph([0,0,0], [[1,2,3], [4,5,6], [7,8]], [(1,4),(5,2),(3,7),(6,8)])
sage: flow = G.flow_solve((-3, 2, 1))
sage: flow
(-2, 0, -1, 0)
sage: G.flow_divergence(flow)
(-3, 2, 1)
sage: div = vector((-34, 27, 7))
sage: flow = G.flow_solve(div)
sage: G.flow_divergence(flow) == div
True
sage: C = G.cycle_space()
sage: G.flow_divergence(flow + C.random_element()) == div
True
sage: G = StableGraph([0,0,0], [[1],[2,3],[4]], [(1,2),(3,4)])
sage: G.flow_solve((-1, 0, 1))
(-1, -1)
sage: G.flow_divergence((-1, -1))
(-1, 0, 1)
sage: G.flow_solve((-1, 3, -2))
(-1, 2)
sage: G.flow_divergence((-1, 2))
(-1, 3, -2)
TESTS::
sage: V = ZZ**4
sage: vectors = [V((-1, 0, 0, 1)), V((-3, 1, -2, 4)), V((5, 2, -13, 6))]
sage: G1 = StableGraph([0,0,0,0], [[1], [2,3], [4,5], [6]], [(1,2), (3,4), (5,6)])
sage: G2 = StableGraph([0,0,0,0], [[1], [2,3], [4,5], [6]], [(1,2), (3,4), (6,5)])
sage: G3 = StableGraph([0,0,0,0], [[1], [2,3], [4,5], [6]], [(2,1), (3,4), (6,5)])
sage: G4 = StableGraph([0,0,0,0], [[1], [2,3], [4,5], [6]], [(1,2), (4,3), (5,6)])
sage: for G in [G1,G2,G3,G4]:
....: for v in vectors:
....: flow = G.flow_solve(v)
....: assert G.flow_divergence(flow) == v, (v,flow,G)
sage: V = ZZ**6
sage: G = StableGraph([0,0,0,0,0,0], [[1,5], [2,3], [4,6,7,10], [8,9,11,13], [14,16], [12,15]], [(1,2),(4,3),(5,6),(7,8),(9,10),(12,11),(13,14),(15,16)])
sage: for _ in range(10):
....: v0 = V.random_element()
....: for u in V.basis():
....: v = v0 - sum(v0) * u
....: flow = G.flow_solve(v)
....: assert G.flow_divergence(flow) == v, (v, flow)
"""
nv = len(self._genera)
if len(vertex_weights) != nv or sum(vertex_weights) != 0:
raise ValueError("vertex_weights must have length nv and sum up to zero")
ancestors, _, vertices = self.spanning_tree()
vertices.reverse()
vertices.pop()
new_vertex_weights = self._vertex_module()(vertex_weights)
if new_vertex_weights is vertex_weights and vertex_weights.is_mutable():
new_vertex_weights = vertex_weights.__copy__()
vertex_weights = new_vertex_weights
V = self._edge_module()
vec = V()
for u in vertices:
v, s, i = ancestors[u]
vec[i] += s * vertex_weights[u]
vertex_weights[v] += vertex_weights[u]
return vec
def plot(self, vord=None, vpos=None, eheight=None):
r"""
Return a graphics object in which ``self`` is plotted.
If ``vord`` is ``None``, the method uses the default vertex order.
If ``vord`` is ``[]``, the parameter ``vord`` is used to give back the vertex order.
EXAMPLES::
sage: from admcycles import *
sage: G = StableGraph([1,2],[[1,2],[3,4,5,6]],[(1,3),(2,4)])
sage: G.plot()
Graphics object consisting of 12 graphics primitives
TESTS::
sage: from admcycles import *
sage: G = StableGraph([1,2],[[1,2],[3,4,5,6]],[(1,3),(2,4)])
sage: vertex_order = []
sage: P = G.plot(vord=vertex_order)
sage: vertex_order
[0, 1]
"""
mark_dx = 1
mark_dy = 1
mark_rad = 0.2
v_dxmin = 1
ed_dy = 0.7
vsize = 0.4
if not vord:
default_vord = list(range(len(self._genera)))
if vord is None:
vord = default_vord
else:
vord += default_vord
reord_self = self.copy()
reord_self.reorder_vertices(vord)
if not vpos:
default_vpos = [(0, 0)]
for i in range(1, len(self._genera)):
default_vpos+=[(default_vpos[i-1][0]+mark_dx*(len(reord_self.list_markings(i-1))+2 *len(reord_self.edges_between(i-1 ,i-1 ))+len(reord_self.list_markings(i))+2 *len(reord_self.edges_between(i,i)))/ZZ(2)+v_dxmin,0)]
if vpos is None:
vpos = default_vpos
else:
vpos += default_vpos
if not eheight:
ned={(i,j): 0 for i in range(len(reord_self._genera)) for j in range(i+1 ,len(reord_self._genera))}
default_eheight = {}
for e in reord_self._edges:
ver1=reord_self.vertex(e[0])
ver2=reord_self.vertex(e[1])
if ver1!=ver2:
default_eheight[e]=abs(ver1-ver2)-1+ned[(min(ver1,ver2), max(ver1,ver2))]*ed_dy
ned[(min(ver1,ver2), max(ver1,ver2))]+=1
if eheight is None:
eheight = default_eheight
else:
eheight.update(default_eheight)
vertex_graph = [polygon2d([[vpos[i][0]-vsize,vpos[i][1]-vsize],[vpos[i][0]+vsize,vpos[i][1]-vsize],[vpos[i][0]+vsize,vpos[i][1]+vsize],[vpos[i][0]-vsize,vpos[i][1]+vsize]], color='white',fill=True, edgecolor='black', thickness=1,zorder=2) + text('g='+repr(reord_self._genera[i]), vpos[i], fontsize=20 , color='black',zorder=3) for i in range(len(reord_self._genera))]
edge_graph=[]
for e in reord_self._edges:
ver1=reord_self.vertex(e[0])
ver2=reord_self.vertex(e[1])
if ver1!=ver2:
x=(vpos[ver1][0]+vpos[ver2][0])/ZZ(2)
y=(vpos[ver1][1]+vpos[ver2][1])/ZZ(2)+eheight[e]
edge_graph+=[bezier_path([[vpos[ver1], (x,y) ,vpos[ver2] ]],color='black',zorder=1)]
marking_graph=[]
for v in range(len(reord_self._genera)):
se_list=reord_self.edges_between(v,v)
m_list=reord_self.list_markings(v)
v_x0=vpos[v][0]-(2*len(se_list)+len(m_list)-1)*mark_dx/ZZ(2)
for e in se_list:
edge_graph+=[bezier_path([[vpos[v], (v_x0,-mark_dy), (v_x0+mark_dx,-mark_dy) ,vpos[v] ]],zorder=1)]
v_x0+=2*mark_dx
for l in m_list:
marking_graph+=[line([vpos[v],(v_x0,-mark_dy)],color='black',zorder=1)+circle((v_x0,-mark_dy),mark_rad, fill=True, facecolor='white', edgecolor='black',zorder=2)+text(repr(l),(v_x0,-mark_dy), fontsize=10, color='black',zorder=3)]
v_x0+=mark_dx
G = sum(marking_graph) + sum(edge_graph) + sum(vertex_graph)
G.axes(False)
return G
def _unicode_art_(self):
"""
Return unicode art for the stable graph ``self``.
EXAMPLES::
sage: from admcycles import *
sage: A = StableGraph([1, 2],[[1, 2, 3], [4]],[(3, 4)])
sage: unicode_art(A)
╭────╮
3 4
╭┴─╮ ╭┴╮
│1 │ │2│
╰┬┬╯ ╰─╯
12
sage: A = StableGraph([333, 4444],[[1, 2, 3], [4]],[(3, 4)])
sage: unicode_art(A)
╭─────╮
3 4
╭┴──╮ ╭┴───╮
│333│ │4444│
╰┬┬─╯ ╰────╯
12
sage: B = StableGraph([3,5], [[1,3,5],[2]], [(1,2),(3,5)])
sage: unicode_art(B)
╭─────╮
│╭╮ │
135 2
╭┴┴┴╮ ╭┴╮
│3 │ │5│
╰───╯ ╰─╯
sage: C = StableGraph([3,5], [[3,1,5],[2,4]], [(1,2),(3,5)])
sage: unicode_art(C)
╭────╮
╭─╮ │
315 2
╭┴┴┴╮ ╭┴╮
│3 │ │5│
╰───╯ ╰┬╯
4
"""
from sage.typeset.unicode_art import UnicodeArt
N = self.num_verts()
all_half_edges = self.halfedges()
half_edges = {i: [j for j in legs_i if j in all_half_edges]
for i, legs_i in zip(range(N), self._legs)}
open_edges = {i: [j for j in legs_i if j not in all_half_edges]
for i, legs_i in zip(range(N), self._legs)}
left_box = [u' ', u'╭', u'│', u'╰', u' ']
right_box = [u' ', u'╮ ', u'│ ', u'╯ ', u' ']
positions = {}
boxes = UnicodeArt()
total_width = 0
for vertex in range(N):
t = list(left_box)
for v in half_edges[vertex]:
w = str(v)
positions[v] = total_width + len(t[0])
t[0] += w
t[1] += u'┴' + u'─' * (len(w) - 1)
for v in open_edges[vertex]:
w = str(v)
t[4] += w
t[3] += u'┬' + u'─' * (len(w) - 1)
t[2] += str(self._genera[vertex])
length = max(len(line) for line in t)
for i in [0, 2, 4]:
t[i] += u' ' * (length - len(t[i]))
for i in [1, 3]:
t[i] += u'─' * (length - len(t[i]))
for i in range(5):
t[i] += right_box[i]
total_width += length + 2
boxes += UnicodeArt(t)
num_edges = self.num_edges()
matchings = [[u' '] * (1 + max(positions.values()))
for _ in range(num_edges)]
for i, (a, b) in enumerate(self.edges()):
xa = positions[a]
xb = positions[b]
if xa > xb:
xa, xb = xb, xa
for j in range(xa + 1, xb):
matchings[i][j] = u'─'
matchings[i][xa] = u'╭'
matchings[i][xb] = u'╮'
for j in range(i + 1, num_edges):
matchings[j][xa] = u'│'
matchings[j][xb] = u'│'
matchings = [u''.join(line) for line in matchings]
return UnicodeArt(matchings + list(boxes))
from sage.combinat.permutation import Permutations
import itertools
def dicunion(*dicts):
return dict(itertools.chain.from_iterable(dct.items() for dct in dicts))
def GraphIsom(G,H,check=False):
if (G.invariant() != H.invariant()):
return []
Isomlist=[]
IsoV={}
IsoL={j:j for j in G.list_markings()}
for j in G.list_markings():
vG=G.vertex(j)
vH=H.vertex(j)
if (G._genera[vG] != H._genera[vH]) or (len(G._legs[vG]) != len(H._legs[vH])) or (vG in IsoV and IsoV[vG] != vH):
return []
IsoV[vG]=vH
gdG={}
gdH={}
for v in range(len(G._genera)):
if v not in IsoV:
gd=(G._genera[v],len(G._legs[v]))
if gd in gdG:
gdG[gd]+=[v]
else:
gdG[gd]=[v]
for v in range(len(H._genera)):
if not v in IsoV.values():
gd=(H._genera[v],len(H._legs[v]))
if gd in gdH:
gdH[gd]+=[v]
else:
gdH[gd]=[v]
if set(gdG) != set(gdH):
return []
VertIm=[]
for gd in gdG:
if len(gdG[gd]) != len(gdH[gd]):
return []
P=Permutations(len(gdG[gd]))
ind=list(range(len(gdG[gd])))
VertIm+=[ [ {gdG[gd][i]:gdH[gd][p[i]-1 ] for i in ind} for p in P] ]
for VI in itertools.product(*VertIm):
continueloop=False
IsoV2=dicunion(IsoV,*VI)
LegIm=[]
for v in range(len(G._genera)):
EdG=G.edges_between(v,v)
EdH=H.edges_between(IsoV2[v],IsoV2[v])
if len(EdG) != len(EdH):
continueloop=True
break
LegImvv=[]
P=Permutations(len(EdG))
ran=list(range(len(EdG)))
choic=len(EdG)*[[0 ,1 ]]
for p in P:
for o in itertools.product(*choic):
di=dicunion({EdG[i][0 ] : EdH[p[i]-1 ][o[i]] for i in ran},{EdG[i][1 ] : EdH[p[i]-1 ][1 -o[i]] for i in ran})
LegImvv+=[di]
LegIm+=[LegImvv]
if continueloop:
continue
for v in range(len(G._genera)):
if continueloop:
break
for w in range(v+1 ,len(G._genera)):
EdG=G.edges_between(v,w)
EdH=H.edges_between(IsoV2[v],IsoV2[w])
if len(EdG) != len(EdH):
continueloop=True
break
LegImvw=[]
P=Permutations(len(EdG))
ran=list(range(len(EdG)))
for p in P:
di=dicunion({EdG[i][0 ] : EdH[p[i]-1 ][0 ] for i in ran},{EdG[i][1 ] : EdH[p[i]-1 ][1 ] for i in ran})
LegImvw+=[di]
LegIm+=[LegImvw]
if continueloop:
continue
Isomlist += [[IsoV2, dicunion(IsoL,*LegDics)] for LegDics in itertools.product(*LegIm)]
if check and Isomlist:
return Isomlist
return Isomlist
