# Source code for thompson.infinite

"""
.. testsetup::

from collections import deque
from fractions   import gcd
from pprint      import pprint

from thompson          import *
from thompson.word     import format
from thompson.infinite import *
"""
from collections import defaultdict
from functools   import partial
from io          import StringIO
from itertools   import chain, permutations

from .number_theory import prod
from .word          import Word, root, format
from .generators    import Generators
from .homomorphism  import format_table
from .automorphism  import Automorphism
from .mixed         import MixedAut

__all__ = ["InfiniteAut"]

def get_factor_class(infinite):
return InfiniteAut if infinite else PeriodicAut

[docs]class InfiniteAut(Automorphism):
"""A purely infinite automorphism which may have been extracted from a mixed automorphism.

InfiniteAut: V(2, 1) -> V(2, 1) specified by 6 generators (after expansion and reduction).
This automorphism was derived from a parent automorphism.
'x' and 'y' represent root words of the parent and current derived algebra, respectively.
x1 a1 a1 a1 a1 ~>    y1 a1 a1 a1 => y1 a1 a1       ~> x1 a1 a1 a1
x1 a1 a1 a1 a2 ~>    y1 a1 a1 a2 => y1 a1 a2 a1    ~> x1 a1 a1 a2 a1
x1 a1 a1 a2    ~>    y1 a1 a2    => y1 a1 a2 a2    ~> x1 a1 a1 a2 a2
x1 a2 a1       ~>    y1 a2 a1    => y1 a2 a1 a1    ~> x1 a2 a1 a1
x1 a2 a2 a1    ~>    y1 a2 a2 a1 => y1 a2 a1 a2    ~> x1 a2 a1 a2
x1 a2 a2 a2    ~>    y1 a2 a2 a2 => y1 a2 a2       ~> x1 a2 a2
>>> phi = random_infinite_automorphism()
>>> phi.order
inf
>>> len(phi.cycle_type)
0
>>> len(phi.characteristics) != 0
True
"""

[docs]	def test_conjugate_to(self, other):
"""We can determine if two purely infinite automorphisms are conjugate by breaking down the quasi-normal basis into :meth:equivalence classes <equivalence_data>.

>>> for psi_i, phi_i in (
...   random_conjugate_infinite_pair()):
... 	rho_i = psi_i.test_conjugate_to(phi_i)
... 	print('Conjugate:', rho_i is not None, ' Conjugator works:', rho_i * phi_i == psi_i * rho_i)
Conjugate: True  Conjugator works: True
Conjugate: True  Conjugator works: True
Conjugate: True  Conjugator works: True

>>> f, g = (load_example('not_conjugate_' + c) for c in 'fg')
>>> f.is_conjugate_to(g)
False

.. doctest::
:hide:

>>> rho is None
True
>>> f, g, h = (load_example('olga_' + c) for c in 'fgh')
>>> rho = f.test_conjugate_to(g)
>>> rho is not None
True
>>> f * rho == rho * g
True
>>> f * h == h * g
True

>>> d, e = ( load_example('two_flow_components_' + c) for c in 'de')
>>> d.is_conjugate_to(e)
True

.. seealso:: This implements Algorithm :paperref:alg:reginf of the paper---see Section :paperref:subsectionRI.
"""
#todo another doctest.
if not isinstance(other, InfiniteAut):
return None
#1. The QNF bases are computed automatically.
#2. Compute the equivalence classes X_1, ... X_m of \equiv on self's QNF basis
type_b, type_c = self._split_basis()
roots, graph = self.equivalence_data(type_b, type_c)
verify_graph(self, roots, graph)
#3. Find the initial and terminal elements of SI *other*-orbits.
#4. Construct the sets R_i
potential_endpoints = other.potential_image_endpoints(type_b)

#5. Type B representitives for each class are stored in *roots*.
#6. Iterate through all the automorphisms which could be conjugators.
for rho in self._potential_conjugators(other, roots, graph, potential_endpoints, type_c):
if self * rho == rho * other:
return rho
return None

def _split_basis(self):
"""Partition X into type B and type C parts."""
#todo docstring and test
type_b = {}
type_c = {}
basis = self.quasinormal_basis
for gen in basis:
type, _, type_b_data = self.orbit_type(gen, basis)
if type.is_type_B():
type_b[gen] = type.characteristic
elif type.is_type_C():
type_c[gen] = type_b_data
else:
raise ValueError('Incorrect orbit type.')
return type_b, type_c

[docs]	def equivalence_data(self, type_b, type_c):
r"""Let :math:X be the quasi-normal basis for the current automorphism :math:\psi. We can define an equivalence relation :math:\equiv on :math:X by taking the non-transitive relation

.. math:: x \equiv y \iff \exists k, \Gamma, \Delta : x\Gamma\psi^k = y\Delta

and allowing it to generate an equivalence relation. This method returns a pair *(roots, graph)* where

- *graph* is a :func:~nx:networkx.DiGraph

- vertices are type B words in :math:X
- directed edges :math:x \to y correspond to the direct relation :math:x \equiv y
- the *graph* is a directed forest

- *roots* is a list of type B words in :math:X

- Each *root* is the root of a different tree in the forest *graph*.

This information allows us to (attempt to) compute the images of :math:X under a conjugator given only the images of *roots*.

.. seealso:: Definition :paperref:EqCl through to Lemma :paperref:lem:effsplit.
"""
G = self._congruence_graph()
self._simplify_graph(G, type_c)
roots = self._reduce_to_forest(G)
return roots, G

def _congruence_graph(self):
"""Form a graph whose vertex set is the QNF basis. The edges store the information which makes two vertices congruent."""
from networkx.classes.digraph import DiGraph
basis = self.quasinormal_basis
min_exp = basis.minimal_expansion_for(self)
terminal, initial = self.semi_infinite_end_points()
endpts = sorted(terminal + initial)
G = DiGraph()
orbit_generators = set(min_exp)
orbit_generators.update(endpts)

#1. Add an edge for every direct congruence relationship.
for gen in orbit_generators:
type, images, _ = self.orbit_type(gen, basis)
for power, img in images.items():
images[power] = basis.test_above(img)

congruent_pairs = permutations(images.items(), 2)
for (pow1, (head1, tail1)), (pow2, (head2, tail2)) in congruent_pairs:
continue
data = dict(start_tail = tail1, power = pow2 - pow1, end_tail = tail2)
assert self.repeated_image(head1.extend(tail1), pow2 - pow1) == head2.extend(tail2)
return G

# @staticmethod
def _simplify_graph(self, G, type_c):
"""Removes all the type C words from this graph. Edges to and from type C words are removed, but the information they is still stored in the graph."""
#2. Remove the type C elements.
for word, type_b_data in type_c.items():
replacement = type_b_data['target']

assert self.repeated_image(word, type_b_data['power']) == replacement.extend(type_b_data['end_tail'])

#Use the scheme of Lemma 5.24 to avoid type C words.
for source, _, incoming in G.in_edges_iter(word, data=True):
if source == replacement:
continue
data = dict(
start_tail = incoming['start_tail'],
power      = incoming['power'] + type_b_data['power'],
end_tail   = type_b_data['end_tail'] + incoming['end_tail']
)
assert self.repeated_image(source.extend(data['start_tail']), data['power']) == replacement.extend(data['end_tail'])

for _, target, outgoing in G.out_edges_iter(word, data=True):
if target == replacement:
continue
data = dict(
start_tail = type_b_data['end_tail'] + outgoing['start_tail'],
power      = outgoing['power'] - type_b_data['power'],
end_tail   = outgoing['end_tail']
)
assert self.repeated_image(replacement.extend(data['start_tail']), data['power']) == target.extend(data['end_tail'])

G.remove_node(word)

return [], G

@staticmethod
def _reduce_to_forest(G):
"""Removes edges from G so that each connected component is a tree."""
from networkx.algorithms.traversal.depth_first_search import dfs_edges
unseen_nodes = set(G.nodes_iter())
unvisisted_edges = set(G.edges_iter())
roots = []

while unseen_nodes:
root = unseen_nodes.pop()
roots.append(root)
for edge in dfs_edges(G, root):
unvisisted_edges.remove(edge)
_, target = edge
unseen_nodes.remove(target)

to_remove = [e for e in G.edges_iter() if e in unvisisted_edges]
G.remove_edges_from(to_remove)
return roots

[docs]	def potential_image_endpoints(other, self_type_b):
"""Let x be a type B word with respect to the current automorphism. This returns a mapping which takes x and produces the set of words w which are endpoints of *other*-orbits which have the same characteristic as x.

.. seealso:: The sets :math:\mathcal R_i of defintion :paperref:def:potential_image_endpoints.
"""
#todo doctest
images_by_char = defaultdict(set)
basis = other.quasinormal_basis
terminal, initial = other.semi_infinite_end_points()
for word in terminal + initial:
type, _, _ = other.orbit_type(word, basis)
if type.is_type_B():

orbit_endpts = {word : images_by_char[char] for word, char in self_type_b.items()}
return orbit_endpts

def _potential_conjugators(self, other, roots, graph, choices, type_c, verbose=False):
log = get_logger(verbose)
#1. Flatten and glue the graph components together to form the ladder
from networkx.algorithms.traversal.depth_first_search import dfs_preorder_nodes
for root in roots:

#2. Define the test function. See the docstring for maps_satisfying_choices
deduce_images = partial(image_for_type_b, roots=roots, graph=graph, aut=other)

#3. Now the hard part---the iteration.
for images in maps_satisfying_choices(ladder, choices, deduce_images, verbose):
domain = Generators(self.signature, sorted(images))
range = Generators(self.signature, (images[d] for d in domain))

log("deducing images for type C words")
#Add in type C images to domain and range
for word, data in type_c.items():
domain.append(word)
img = image_for_type_c(word, data, images, other)
range.append(img)

try:
rho = Automorphism(domain, range)
except ValueError as e:
log("This didn't define an automorphism")
continue
else:
log("These images DID build an automorphism")
yield rho

[docs]	def find_power_conjugators(self, other, cheat=False):
"""Tests two infinite factors to see if they are power conjugate. Yields minimal solutions :math:(a, b, \rho).

>>> example_6_8_psi, example_6_8_phi = load_example_pair('example_6_8')
>>> solns = example_6_8_psi.find_power_conjugators(example_6_8_phi)
>>> for a, b, rho in solns:
... 	print(a, b)
... 	assert example_6_8_psi ** a * rho == rho * example_6_8_phi ** b
3 1
-3 -1

.. warning:: If the :meth:~thompson.infinite.InfiniteAut.power_conjugacy_bounds are reasonable large (say > 30), this method could potentially take a long time!

.. seealso:: Algorithm :paperref:alg:pcRI of the paper.
"""
if not isinstance(other, InfiniteAut):
raise StopIteration
if cheat:
from .examples.random import random_power_bounds
bounds = random_power_bounds
else:
bounds = self.power_conjugacy_bounds(other)
yield from self._test_power_conjugate_upto(other, *bounds, inverses=True)

[docs]	def test_power_conjugate_to(self, other, cheat=False):
r"""Tests two infinite factors to see if they are power conjugate. If a solution exists, returns :math:(a, b, \rho) such that :math:\rho^{-1}\psi^a\rho = \phi^b. Otherwise returns None.

>>> result = example_6_8_psi.test_power_conjugate_to(example_6_8_phi)
>>> result is not None
True
>>> a, b, rho = result
>>> (example_6_8_psi ** a) * rho == rho * (example_6_8_phi ** b)
True

.. warning:: If the :meth:~thompson.infinite.InfiniteAut.power_conjugacy_bounds are reasonable large (say > 30), this method could potentially take a long time!

.. seealso:: Algorithm :paperref:alg:pcRI of the paper.
"""
try:
return next(self.find_power_conjugators(other, cheat=cheat))
except StopIteration:
# print('No infinite conjugators')
return None

[docs]	def power_conjugacy_bounds(self, other):
"""Compute the bounds :math:\hat a, \hat b on powers which could solve the power conjugacy problem.

>>> example_6_8_psi.power_conjugacy_bounds(example_6_8_phi)
(9, 1)

.. seealso:: Proposition :paperref:divisors and Corollary :paperref:AJDCOROLLARYPC.
"""
s_parts = self.minimal_partition()
o_parts = other.minimal_partition()
#If the root sets are different, there's no hope of power conjugacy.
if s_parts.keys() != o_parts.keys():
return 0, 0
s_bound = self.compute_bounds(s_parts, o_parts)
o_bound = self.compute_bounds(o_parts, s_parts)
return s_bound, o_bound

[docs]	def minimal_partition(self):
r"""Let :math:\psi be the current automorphism. This method partitions the characteristics :math:M_\psi into cells :math:P_1 \sqcup \dots \sqcup P_L, where
- The multipliers :math:\Gamma all have the same :func:~thompson.word.root, for all :math:(m, \Gamma) in each :math:P_i.
- :math:L is minimal with this property.

>>> def print_partition(p):
... 	for root in sorted(p.keys(), reverse=True):
... 		print(format(root), end = ':')
... 		for power, mult, _ in p[root]:
... 			print(' ({}, {})'.format(power, format(mult)), end='')
... 		print()
>>> print_partition(example_6_8_psi.minimal_partition())
a1: (-1, a1)
a2: (1, a2)
>>> print_partition(example_6_8_phi.minimal_partition())
a1: (-1, a1 a1 a1)
a2: (1, a2 a2 a2)
>>> example_6_9_psi, example_6_9_phi = load_example_pair('example_6_9')
>>> print_partition(example_6_9_phi.minimal_partition())
a1: (-2, a1)
a2: (1, a2)

:returns: a dictionary of sets. The keys of this dictionary are the roots :math:\sqrt\Gamma; the values are the cells :math:P_i. An element of a cell looks like :math:m, \Gamma, r where :math:m, \Gamma is a characteristic and :math:r is the root power corresponding to :math:\sqrt\Gamma.

.. seealso:: the discussion following Corollary :paperref:AJDCOROLLARYPC.
"""
chars = self.characteristics
parts = defaultdict(set)
for power, mult in chars:
root_mult, root_power = root(mult)
return parts

[docs]	@staticmethod
def compute_bounds(s_parts, o_parts):
"""Computes the bounds :math:\hat a, \hat b (in terms of the partitions :math:P, Q given by *s_parts* and *o_parts*) as in eqns (14) and (15) of the paper.

>>> def bounds(s, o):
... 	P = s.minimal_partition()
... 	Q = o.minimal_partition()
... 	a_hat = InfiniteAut.compute_bounds(P, Q)
... 	b_hat = InfiniteAut.compute_bounds(Q, P)
... 	return a_hat, b_hat
>>> bounds(example_6_8_psi, example_6_8_phi)
(9, 1)
>>> bounds(example_6_9_psi, example_6_9_phi)
(1, 2)
"""
bound = 1
for root in s_parts:
P_i = s_parts[root]
Q_i = o_parts[root]
bound *= prod(abs(power) for power, mult, root_power in P_i) ** len(Q_i)
bound *= prod(root_power for power, mult, root_power in Q_i) ** len(P_i)
return bound

def maps_satisfying_choices(domain, choices, image_for, verbose=False):
r"""Suppose we have a list of elements :math:d belonging to some list *domain*. We would like to efficiently enumerate the functions :math:f\colon\text{domain} -> I where :math:I is some set. We would also like these functions :math:f to abide by certain rules described below.

For each such :math:d we have a set of *choices* to make: say :math:\text{choices}(d) = \{c_{d,1}, \dots c_{d,n_d}\}. Making a choice :math:c_{d,i} for :math:d will determine the set of potential images for :math:d. This set is allowed to depend on:

- the element :math:d being mapped;
- the choice :math:c_{d, i} which was made for d;
- the images which have been proposed thus far for the elements preceeding :math:d in *domain*.

We also ask that each choice produces at most one image for :math:d. This should be determined by the call image_for(d, choice, images), where images is the proposed mapping which has been constructed so far. If no image is available, this function should return None.

.. warning:: Make sure that None isn't a valid image for :math:d!

:returns: yields mappings which satisfy all the constraints until it is no longer possible to do so.
"""
log = get_logger(verbose)
#2. Setup the state we need
images = {}                             #mapping from ladder to images
choice_iterators = [None] * len(domain) #iterators yielding the choices at each rung
depth  = 0                              #current position on the ladder
ascend = False                          #do we go up or down?
yield_images = False                    #have we found a possible mapping?

while True:
log("\ndepth", depth, "and going", "up" if ascend else "down")
log("candidate images from ladder:")
for key in domain:
try:
log(key, "->", images[key])
except KeyError:
break

if yield_images:
log("yielding these images")
yield images
yield_images = False

#If the last choice we made didn't work (or we reached the bottom of the ladder) go up
if ascend:
current = domain[depth]
try:
del images[current]
except KeyError:
pass
choice_iterators[depth] = None
depth -= 1
if depth < 0:
log("all choices considered; ending loop")
break
ascend = False

#Select the next choice for this depth
current = domain[depth]
log("where should we map", current)
if choice_iterators[depth] is None:
choice_iterators[depth] = iter(choices[current])
try:
choice = next(choice_iterators[depth])
log("next choice:", choice)
except StopIteration:
log("no more choices at depth", depth)
ascend = True
continue

#Does this choice give us an image?
img = image_for(current, choice, images)
if img is None:
log("no suitable image")
continue
if img in images.values():
log("already mapped something to this image")
continue
log("corresponding image:", img)
images[current] = img

#If we've made it this far, we've chosen an image. Try to go down the ladder.
if depth + 1 == len(domain):
yield_images = True
ascend = True
else:
depth += 1

def image_for_type_b(word, chosen_endpoint, images, roots, graph, aut):
"""Is it possible to map *word* into the *aut*-orbit ending with *chosen_endpoint* when we have already constructed a mapping described by *images*?"""
#In the paper's notation,
#chosen_endpoint is w
#word is x
if word in roots:
return chosen_endpoint

predecessor, _, edge_data = next(graph.in_edges_iter(word, data=True))
predecessor_image = images[predecessor]

u = chosen_endpoint.extend(edge_data['end_tail'])     #w   Delta
v = predecessor_image.extend(edge_data['start_tail']) #y_i Gamma
solns = aut.share_orbit(u, v)
if solns.is_empty():
return None
assert not solns.is_sequence(), (u, v, solns)
return aut.repeated_image(chosen_endpoint, solns.base + edge_data['power'])

def image_for_type_c(word, type_b_data, images, aut):
"""The end of Lemma 5.24 shows how we can calculate the image of a type C word given the images of all type B words."""
power, gen, tail = type_b_data['power'], type_b_data['target'], type_b_data['end_tail']
w = images[gen].extend(tail)
return aut.repeated_image(w, -power)

#For debugging only
def fmt_triple(edge_data):
return "({}, {}, {})".format(
format(edge_data['start_tail']), edge_data['power'], format(edge_data['end_tail'])
)

def print_edge(source, target, data):
print("{} --> {} with data {}".format(source, target, fmt_triple(data)))

def dump_graph(roots, graph):
from networkx.algorithms.traversal.depth_first_search import dfs_preorder_nodes
for i, root in enumerate(roots):
print('component', i, 'with root', root)
print('type B elements:')
for node in dfs_preorder_nodes(graph, root):
print('\tEdges out of', node)
for source, target in graph.out_edges_iter(node):
data = graph[source][target]
print('\t\tto', target, 'with data\n\t\t\t', fmt_triple(data))

def verify_graph(aut, roots, graph):
from networkx.algorithms.traversal.depth_first_search import dfs_preorder_nodes
for i, root in enumerate(roots):
for node in dfs_preorder_nodes(graph, root):
for source, target in graph.out_edges_iter(node):
data = graph[source][target]
assert aut.repeated_image(source.extend(data['start_tail']), data['power']) == target.extend(data['end_tail'])

def get_logger(verbose):
if verbose:
log = print
else:
def log(*args, **kwargs): pass
return log