# Ticket #26771: cluster_algebra.py

File cluster_algebra.py, 82.1 KB (added by gh-EBanaian, 4 years ago)
Line
1r"""
2Cluster algebras
3
4This file constructs cluster algebras using the Parent-Element framework.
5The implementation mainly utilizes structural theorems from [FZ2007]_.
6
7The key points being used here are these:
8
9- cluster variables are parametrized by their g-vectors;
10
11- g-vectors (together with c-vectors) provide a self-standing model for the
12  combinatorics behind any cluster algebra;
13
14- each cluster variable in any cluster algebra can be computed, by the
15  separation of additions formula, from its g-vector and F-polynomial.
16
17Accordingly this file provides three classes:
18
19- :class:ClusterAlgebra
20
21- :class:ClusterAlgebraSeed
22
23- :class:ClusterAlgebraElement
24
25:class:ClusterAlgebra, constructed as a subobject of
26:class:sage.rings.polynomial.laurent_polynomial_ring.LaurentPolynomialRing_generic,
27is the frontend of this implementation. It provides all the algebraic
28features (like ring morphisms), it computes cluster variables, it is
29responsible for controlling the exploration of the exchange graph and
30serves as the repository for all the data recursively computed so far.
31In particular, all g-vectors and all F-polynomials of known cluster
32variables as well as a mutation path by which they can be obtained
33are recorded. In the optic of efficiency, this implementation does not
34store directly the exchange graph nor the exchange relations. Both of
35these could be added to :class:ClusterAlgebra with minimal effort.
36
37:class:ClusterAlgebraSeed provides the combinatorial backbone
38for :class:ClusterAlgebra. It is an auxiliary class and therefore its
39instances should **not** be directly created by the user. Rather it
40should be accessed via :meth:ClusterAlgebra.current_seed
41and :meth:ClusterAlgebra.initial_seed. The task of performing current
42seed mutations is delegated to this class. Seeds are considered equal if
43they have the same parent cluster algebra and they can be obtained from
44each other by a permutation of their data (i.e. if they coincide as
45unlabelled seeds).  Cluster algebras whose initial seeds are equal in the
46above sense are not considered equal but are endowed with coercion maps
47to each other.  More generally, a cluster algebra is endowed with coercion
48maps from any cluster algebra which is obtained by freezing a collection
49of initial cluster variables and/or permuting both cluster variables
50and coefficients.
51
52:class:ClusterAlgebraElement is a thin wrapper around
53:class:sage.rings.polynomial.laurent_polynomial.LaurentPolynomial
54providing all the functions specific to cluster variables.
55Elements of a cluster algebra with principal coefficients have special methods
56and these are grouped in the subclass :class:PrincipalClusterAlgebraElement.
57
59:class:ClusterAlgebra are built by identifying the initial cluster variables
60with the generators of :meth:ClusterAlgebra.ambient. In particular, this
61forces a specific embedding into the ambient field of rational expressions. In
62view of this, although cluster algebras themselves are independent of the
63choice of initial seed, :meth:ClusterAlgebra.mutate_initial is forced to
64return a different instance of :class:ClusterAlgebra. At the moment there
65is no coercion implemented among the two instances but this could in
66principle be added to :meth:ClusterAlgebra.mutate_initial.
67
68REFERENCES:
69
70- [FZ2007]_
71- [LLZ2014]_
72- [NZ2012]_
73
74AUTHORS:
75
76- Dylan Rupel (2015-06-15): initial version
77
78- Salvatore Stella (2015-06-15): initial version
79
80EXAMPLES:
81
82We begin by creating a simple cluster algebra and printing its
83initial exchange matrix::
84
85    sage: A = ClusterAlgebra(['A', 2]); A
86    A Cluster Algebra with cluster variables x0, x1 and no coefficients over Integer Ring
87    sage: A.b_matrix()
88    [ 0  1]
89    [-1  0]
90
91A is of finite type so we can explore all its exchange graph::
92
93    sage: A.explore_to_depth(infinity)
94
95and get all its g-vectors, F-polynomials, and cluster variables::
96
97    sage: sorted(A.g_vectors_so_far())
98    [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, 0)]
99    sage: sorted(A.F_polynomials_so_far(), key=str)
100    [1, 1, u0 + 1, u0*u1 + u0 + 1, u1 + 1]
101    sage: sorted(A.cluster_variables_so_far(), key=str)
102    [(x0 + 1)/x1, (x0 + x1 + 1)/(x0*x1), (x1 + 1)/x0, x0, x1]
103
104Simple operations among cluster variables behave as expected::
105
106    sage: s = A.cluster_variable((0, -1)); s
107    (x0 + 1)/x1
108    sage: t = A.cluster_variable((-1, 1)); t
109    (x1 + 1)/x0
110    sage: t + s
111    (x0^2 + x1^2 + x0 + x1)/(x0*x1)
112    sage: _.parent() == A
113    True
114    sage: t - s
115    (-x0^2 + x1^2 - x0 + x1)/(x0*x1)
116    sage: _.parent() == A
117    True
118    sage: t*s
119    (x0*x1 + x0 + x1 + 1)/(x0*x1)
120    sage: _.parent() == A
121    True
122    sage: t/s
123    (x1^2 + x1)/(x0^2 + x0)
124    sage: _.parent() == A
125    False
126
127Division is not guaranteed to yield an element of A so it returns an
128element of A.ambient().fraction_field() instead::
129
130    sage: (t/s).parent() == A.ambient().fraction_field()
131    True
132
133We can compute denominator vectors of any element of A::
134
135    sage: (t*s).d_vector()
136    (1, 1)
137
138Since we are in rank 2 and we do not have coefficients we can compute the
139greedy element associated to any denominator vector::
140
141    sage: A.rank() == 2 and A.coefficients() == ()
142    True
143    sage: A.greedy_element((1, 1))
144    (x0 + x1 + 1)/(x0*x1)
145    sage: _ == t*s
146    False
147
148not surprising since there is no cluster in A containing
149both t and s::
150
151    sage: seeds = A.seeds(mutating_F=false)
152    sage: [ S for S in seeds if (0, -1) in S and (-1, 1) in S ]
153    []
154
155indeed::
156
157    sage: A.greedy_element((1, 1)) == A.cluster_variable((-1, 0))
158    True
159
160Disabling F-polynomials in the computation just done was redundant because we
161already explored the whole exchange graph before. Though in different
162circumstances it could have saved us considerable time.
163
164g-vectors and F-polynomials can be computed from elements of A only if
165A has principal coefficients at the initial seed::
166
167    sage: (t*s).g_vector()
168    Traceback (most recent call last):
169    ...
170    AttributeError: 'ClusterAlgebra_with_category.element_class' object has no attribute 'g_vector'
171    sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
172    sage: A.explore_to_depth(infinity)
173    sage: s = A.cluster_variable((0, -1)); s
174    (x0*y1 + 1)/x1
175    sage: t = A.cluster_variable((-1, 1)); t
176    (x1 + y0)/x0
177    sage: (t*s).g_vector()
178    (-1, 0)
179    sage: (t*s).F_polynomial()
180    u0*u1 + u0 + u1 + 1
181    sage: (t*s).is_homogeneous()
182    True
183    sage: (t+s).is_homogeneous()
184    False
185    sage: (t+s).homogeneous_components()
186    {(-1, 1): (x1 + y0)/x0, (0, -1): (x0*y1 + 1)/x1}
187
188Each cluster algebra is endowed with a reference to a current seed;
189it could be useful to assign a name to it::
190
191    sage: A = ClusterAlgebra(['F', 4])
192    sage: len(A.g_vectors_so_far())
193    4
194    sage: A.current_seed()
195    The initial seed of a Cluster Algebra with cluster variables x0, x1, x2, x3
196     and no coefficients over Integer Ring
197    sage: A.current_seed() == A.initial_seed()
198    True
199    sage: S = A.current_seed()
200    sage: S.b_matrix()
201    [ 0  1  0  0]
202    [-1  0 -1  0]
203    [ 0  2  0  1]
204    [ 0  0 -1  0]
205    sage: S.g_matrix()
206    [1 0 0 0]
207    [0 1 0 0]
208    [0 0 1 0]
209    [0 0 0 1]
210    sage: S.cluster_variables()
211    [x0, x1, x2, x3]
212
213and use S to walk around the exchange graph of A::
214
215    sage: S.mutate(0); S
216    The seed of a Cluster Algebra with cluster variables x0, x1, x2, x3
217     and no coefficients over Integer Ring obtained from the initial
218     by mutating in direction 0
219    sage: S.b_matrix()
220    [ 0 -1  0  0]
221    [ 1  0 -1  0]
222    [ 0  2  0  1]
223    [ 0  0 -1  0]
224    sage: S.g_matrix()
225    [-1  0  0  0]
226    [ 1  1  0  0]
227    [ 0  0  1  0]
228    [ 0  0  0  1]
229    sage: S.cluster_variables()
230    [(x1 + 1)/x0, x1, x2, x3]
231    sage: S.mutate('sinks'); S
232    The seed of a Cluster Algebra with cluster variables x0, x1, x2, x3
233     and no coefficients over Integer Ring obtained from the initial
234     by mutating along the sequence [0, 2]
235    sage: S.mutate([2, 3, 2, 1, 0]); S
236    The seed of a Cluster Algebra with cluster variables x0, x1, x2, x3
237     and no coefficients over Integer Ring obtained from the initial
238     by mutating along the sequence [0, 3, 2, 1, 0]
239    sage: S.g_vectors()
240    [(0, 1, -2, 0), (-1, 2, -2, 0), (0, 1, -1, 0), (0, 0, 0, -1)]
241    sage: S.cluster_variable(3)
242    (x2 + 1)/x3
243
244Walking around by mutating S updates the informations stored in A::
245
246    sage: len(A.g_vectors_so_far())
247    10
248    sage: A.current_seed().path_from_initial_seed()
249    [0, 3, 2, 1, 0]
250    sage: A.current_seed() == S
251    True
252
253Starting from A.initial_seed() still records data in A but does not
254update A.current_seed()::
255
256    sage: S1 = A.initial_seed()
257    sage: S1.mutate([2, 1, 3])
258    sage: len(A.g_vectors_so_far())
259    11
260    sage: S1 == A.current_seed()
261    False
262
263Since :class:ClusterAlgebra inherits from :class:UniqueRepresentation,
264computed data is shared across instances::
265
266    sage: A1 = ClusterAlgebra(['F', 4])
267    sage: A1 is A
268    True
269    sage: len(A1.g_vectors_so_far())
270    11
271
272It can be useful, at times to forget all computed data. Because of
273:class:UniqueRepresentation this cannot be achieved by simply creating a
274new instance; instead it has to be manually triggered by::
275
276    sage: A.clear_computed_data()
277    sage: len(A.g_vectors_so_far())
278    4
279
280Given a cluster algebra A we may be looking for a specific cluster
281variable::
282
283    sage: A = ClusterAlgebra(['E', 8, 1])
284    sage: v = (-1, 1, -1, 1, -1, 1, 0, 0, 1)
285    sage: A.find_g_vector(v, depth=2)
286    sage: seq = A.find_g_vector(v); seq  # random
287    [0, 1, 2, 4, 3]
288    sage: v in A.initial_seed().mutate(seq, inplace=False).g_vectors()
289    True
290
291This also performs mutations of F-polynomials::
292
293    sage: A.F_polynomial((-1, 1, -1, 1, -1, 1, 0, 0, 1))
294    u0*u1*u2*u3*u4 + u0*u1*u2*u4 + u0*u2*u3*u4 + u0*u1*u2 + u0*u2*u4
295     + u2*u3*u4 + u0*u2 + u0*u4 + u2*u4 + u0 + u2 + u4 + 1
296
297which might not be a good idea in algebras that are too big. One workaround is
298to first disable F-polynomials and then recompute only the desired mutations::
299
300    sage: A.reset_exploring_iterator(mutating_F=False)  # long time
301    sage: v = (-1, 1, -2, 2, -1, 1, -1, 1, 1)  # long time
302    sage: seq = A.find_g_vector(v); seq  # long time random
303    [1, 0, 2, 6, 5, 4, 3, 8, 1]
304    sage: S = A.initial_seed().mutate(seq, inplace=False)   # long time
305    sage: v in S.g_vectors()   # long time
306    True
307    sage: A.current_seed().mutate(seq)    # long time
308    sage: A.F_polynomial((-1, 1, -2, 2, -1, 1, -1, 1, 1))   # long time
309    u0*u1^2*u2^2*u3*u4*u5*u6*u8 +
310    ...
311    2*u2 + u4 + u6 + 1
312
313We can manually freeze cluster variables and get coercions in between
314the two algebras::
315
316    sage: A = ClusterAlgebra(['F', 4]); A
317    A Cluster Algebra with cluster variables x0, x1, x2, x3 and no coefficients
318     over Integer Ring
319    sage: A1 = ClusterAlgebra(A.b_matrix().matrix_from_columns([0, 1, 2]), coefficient_prefix='x'); A1
320    A Cluster Algebra with cluster variables x0, x1, x2 and coefficient x3
321     over Integer Ring
322    sage: A.has_coerce_map_from(A1)
323    True
324
325and we also have an immersion of A.base() into A and of A
326into A.ambient()::
327
328    sage: A.has_coerce_map_from(A.base())
329    True
330    sage: A.ambient().has_coerce_map_from(A)
331    True
332
333but there is currently no coercion in between algebras obtained by
334mutating at the initial seed::
335
336    sage: A1 = A.mutate_initial(0); A1
337    A Cluster Algebra with cluster variables x0, x1, x2, x3 and no coefficients
338     over Integer Ring
339    sage: A.b_matrix() == A1.b_matrix()
340    False
341    sage: [X.has_coerce_map_from(Y) for X, Y in [(A, A1), (A1, A)]]
342    [False, False]
343"""
344
345# ****************************************************************************
346#       Copyright (C) 2015 Dylan Rupel and Salvatore Stella
347#
348# This program is free software: you can redistribute it and/or modify
350# the Free Software Foundation, either version 2 of the License, or
351# (at your option) any later version.
353# ****************************************************************************
354from __future__ import absolute_import
355
356from six.moves import range, map
357
358from copy import copy
359
360from sage.categories.homset import Hom
361from sage.categories.morphism import SetMorphism
362from sage.categories.rings import Rings
363from sage.combinat.cluster_algebra_quiver.quiver import ClusterQuiver
364from sage.combinat.permutation import Permutation
365from sage.functions.generalized import sign
366from sage.functions.other import binomial
367from sage.geometry.cone import Cone
368from sage.geometry.fan import Fan
369from sage.matrix.constructor import identity_matrix, matrix
370from sage.matrix.special import block_matrix
371from sage.misc.cachefunc import cached_method
372from sage.misc.misc_c import prod
373from sage.modules.free_module_element import vector
374from sage.rings.infinity import infinity
375from sage.rings.integer import Integer
376from sage.rings.integer_ring import ZZ
377from sage.rings.polynomial.laurent_polynomial_ring import (LaurentPolynomialRing_generic,
378                                                           LaurentPolynomialRing)
379from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
380from sage.rings.rational_field import QQ
381from sage.structure.element_wrapper import ElementWrapper
382from sage.structure.parent import Parent
383from sage.structure.sage_object import SageObject
384from sage.structure.unique_representation import UniqueRepresentation
385
386
387##############################################################################
388# Elements of a cluster algebra
389##############################################################################
390
391class ClusterAlgebraElement(ElementWrapper):
392    """
393    An element of a cluster algebra.
394    """
397        r"""
398        Return the sum of self and other.
399
400        INPUT:
401
402        - other -- an element of self.parent()
403
404        EXAMPLES::
405
406            sage: A = ClusterAlgebra(['F', 4])
407            sage: A.an_element() + A.an_element()
408            2*x0
409        """
410        return self.parent().retract(self.lift() + other.lift())
411
412    def _neg_(self):
413        r"""
414        Return  the negative of self.
415
416        EXAMPLES::
417
418            sage: A = ClusterAlgebra(['F', 4])
419            sage: -A.an_element()
420            -x0
421        """
422        return self.parent().retract(-self.lift())
423
424    def _div_(self, other):
425        r"""
426        Return the quotient of self and other.
427
428        .. WARNING::
429
430            The result of a division is not guaranteed to be inside
431            :meth:parent therefore this method does not return an
432            instance of :class:ClusterAlgebraElement.
433
434        EXAMPLES::
435
436            sage: A = ClusterAlgebra(['F', 4])
437            sage: x = A.an_element()
438            sage: x/x
439            1
440            sage: _.parent()
441            Multivariate Laurent Polynomial Ring in x0, x1, x2, x3
442             over Integer Ring
443            sage: A.retract(x/x)
444            1
445            sage: _.parent()
446            A Cluster Algebra with cluster variables x0, x1, x2, x3
447             and no coefficients over Integer Ring
448        """
449        return self.lift() / other.lift()
450
451    def d_vector(self):
452        r"""
453        Return the denominator vector of self as a tuple of integers.
454
455        EXAMPLES::
456
457            sage: A = ClusterAlgebra(['F', 4], principal_coefficients=True)
458            sage: A.current_seed().mutate([0, 2, 1])
459            sage: x = A.cluster_variable((-1, 2, -2, 2)) * A.cluster_variable((0, 0, 0, 1))**2
460            sage: x.d_vector()
461            (1, 1, 2, -2)
462        """
463        monomials = self.lift().dict().keys()
464        minimal = map(min, zip(*monomials))
465        return tuple(-vector(minimal))[:self.parent().rank()]
466
467    def _repr_(self):
468        r"""
469        Return the string representation of self.
470
471        EXAMPLES::
472
473            sage: A = ClusterAlgebra(['F', 4], principal_coefficients=True)
474            sage: A.current_seed().mutate([0, 2, 1])
475            sage: A.cluster_variable((-1, 2, -2, 2))
476            (x0*x2^2*y0*y1*y2^2 + x1^3*x3^2 + x1^2*x3^2*y0 + 2*x1^2*x3*y2 + 2*x1*x3*y0*y2 + x1*y2^2 + y0*y2^2)/(x0*x1*x2^2)
477        """
478        numer, denom = self.lift()._fraction_pair()
479        return repr(numer / denom)
480
481
482class PrincipalClusterAlgebraElement(ClusterAlgebraElement):
483    """
484    An element in a cluster algebra with principle coefficients.
485    """
486    def g_vector(self):
487        r"""
488        Return the g-vector of self.
489
490        EXAMPLES::
491
492            sage: A = ClusterAlgebra(['B', 2], principal_coefficients=True)
493            sage: A.cluster_variable((1, 0)).g_vector() == (1, 0)
494            True
495            sage: sum(A.initial_cluster_variables()).g_vector()
496            Traceback (most recent call last):
497            ...
498            ValueError: this element is not homogeneous
499        """
500        components = self.homogeneous_components()
501        if len(components) != 1:
502            raise ValueError("this element is not homogeneous")
503        k, = components.keys()
504        return k
505
506    def F_polynomial(self):
507        r"""
508        Return the F-polynomial of self.
509
510        EXAMPLES::
511
512            sage: A = ClusterAlgebra(['B', 2], principal_coefficients=True)
513            sage: S = A.initial_seed()
514            sage: S.mutate([0, 1, 0])
515            sage: S.cluster_variable(0).F_polynomial() == S.F_polynomial(0)
516            True
517            sage: sum(A.initial_cluster_variables()).F_polynomial()
518            Traceback (most recent call last):
519            ...
520            ValueError: this element is not homogeneous
521        """
522        if not self.is_homogeneous():
523            raise ValueError("this element is not homogeneous")
524        subs_dict = dict()
525        A = self.parent()
526        for x in A.initial_cluster_variables():
527            subs_dict[x.lift()] = A._U(1)
528        for i in range(A.rank()):
529            subs_dict[A.coefficient(i).lift()] = A._U.gen(i)
530        return self.lift().substitute(subs_dict)
531
532    def is_homogeneous(self):
533        r"""
534        Return True if self is a homogeneous element
535        of self.parent().
536
537        EXAMPLES::
538
539            sage: A = ClusterAlgebra(['B', 2], principal_coefficients=True)
540            sage: A.cluster_variable((1, 0)).is_homogeneous()
541            True
542            sage: x = A.cluster_variable((1, 0)) + A.cluster_variable((0, 1))
543            sage: x.is_homogeneous()
544            False
545        """
546        return len(self.homogeneous_components()) == 1
547
548    def homogeneous_components(self):
549        r"""
550        Return a dictionary of the homogeneous components of self.
551
552        OUTPUT:
553
554        A dictionary whose keys are homogeneous degrees and whose values
555        are the summands of self of the given degree.
556
557        EXAMPLES::
558
559            sage: A = ClusterAlgebra(['B', 2], principal_coefficients=True)
560            sage: x = A.cluster_variable((1, 0)) + A.cluster_variable((0, 1))
561            sage: x.homogeneous_components()
562            {(0, 1): x1, (1, 0): x0}
563        """
564        deg_matrix = block_matrix([[identity_matrix(self.parent().rank()),
565                                    -self.parent().b_matrix()]])
566        components = dict()
567        x = self.lift()
568        monomials = x.monomials()
569        for m in monomials:
570            g_vect = tuple(deg_matrix * vector(m.exponents()[0]))
571            if g_vect in components:
572                components[g_vect] += self.parent().retract(x.monomial_coefficient(m) * m)
573            else:
574                components[g_vect] = self.parent().retract(x.monomial_coefficient(m) * m)
575        return components
576
577
578##############################################################################
579# Seeds
580##############################################################################
581
582class ClusterAlgebraSeed(SageObject):
583    """
584    A seed in a Cluster Algebra.
585
586    INPUT:
587
588    - B -- a skew-symmetrizable integer matrix
589    - C -- the matrix of c-vectors of self
590    - G -- the matrix of g-vectors of self
591    - parent -- :class:ClusterAlgebra; the algebra to which the
592      seed belongs
593    - path -- list (default []); the mutation sequence from the
594      initial seed of parent to self
595
596    .. WARNING::
597
598        Seeds should **not** be created manually: no test is performed to
599        assert that they are built from consistent data nor that they
600        really are seeds of parent. If you create seeds with
601        inconsistent data all sort of things can go wrong, even
602        :meth:__eq__ is no longer guaranteed to give correct answers.
603        Use at your own risk.
604    """
605    def __init__(self, B, C, G, ex_d, parent, **kwargs):
606        r"""
607        Initialize self.
608
609        EXAMPLES::
610
611            sage: A = ClusterAlgebra(['F', 4])
612            sage: from sage.algebras.cluster_algebra import ClusterAlgebraSeed
613            sage: ClusterAlgebraSeed(A.b_matrix(), identity_matrix(4), identity_matrix(4), A, path=[1, 2, 3])
614            The seed of a Cluster Algebra with cluster variables x0, x1, x2, x3
615             and no coefficients over Integer Ring obtained from the initial
616             by mutating along the sequence [1, 2, 3]
617        """
618        self._B = copy(B)
619        self._C = copy(C)
620        self._G = copy(G)
621        self._ex_d = copy(ex_d)
622        self._parent = parent
623        self._path = kwargs.get('path', [])
624
625    def __copy__(self):
626        r"""
627        Return a copy of self.
628
629        EXAMPLES::
630
631            sage: A = ClusterAlgebra(['A', 3])
632            sage: S = copy(A.current_seed())
633            sage: S == A.current_seed()
634            True
635            sage: S is not A.current_seed()
636            True
637        """
638        other = type(self).__new__(type(self))
639        other._B = copy(self._B)
640        other._C = copy(self._C)
641        other._G = copy(self._G)
642        other._parent = self._parent
643        other._path = copy(self._path)
644        return other
645
646    def __eq__(self, other):
647        r"""
648        Test equality of two seeds.
649
650        INPUT:
651
652        - other -- a :class:ClusterAlgebraSeed
653
654        ALGORITHM:
655
656        self and other are deemed to be equal if they have the same
657        parent and their set of g-vectors coincide, i.e. this tests
658        equality of unlabelled seeds.
659
660        EXAMPLES::
661
662            sage: A = ClusterAlgebra(['A', 3])
663            sage: A.clear_computed_data()
664            sage: S = copy(A.current_seed())
665            sage: S.mutate([0, 2, 0])
666            sage: S == A.current_seed()
667            False
668            sage: S.mutate(2)
669            sage: S == A.current_seed()
670            True
671
672            sage: A = ClusterAlgebra(['B', 2], principal_coefficients=True)
673            sage: S = A.current_seed()
674            sage: S.mutate(0)
675            sage: S == A.current_seed()
676            True
677        """
678        return (isinstance(other, ClusterAlgebraSeed) and
679                self.parent() == other.parent() and
680                frozenset(self.g_vectors()) == frozenset(other.g_vectors()))
681
682    def __contains__(self, element):
683        r"""
684        Test whether element belong to self.
685
686        INPUT:
687
688        - element -- either a g-vector or an element of :meth:parent
689
690        EXAMPLES::
691
692            sage: A = ClusterAlgebra(['A', 3])
693            sage: S = A.initial_seed()
694            sage: (1, 0, 0) in S
695            True
696            sage: (1, 1, 0) in S
697            False
698            sage: A.cluster_variable((1, 0, 0)) in S
699            True
700        """
701        if isinstance(element, ClusterAlgebraElement):
702            cluster = self.cluster_variables()
703        else:
704            element = tuple(element)
705            cluster = self.g_vectors()
706        return element in cluster
707
708    def __hash__(self):
709        r"""
710        Return the hash of self.
711
712        ALGORITHM:
713
714        For speed purposes the hash is computed on :meth:self.g_vectors.
715        In particular it is guaranteed to be unique only within a given
716        instance of :class:ClusterAlgebra. Moreover unlabelled seeds that
717        have the same set of g-vectors have the same hash.
718
719        EXAMPLES::
720
721            sage: A = ClusterAlgebra(['A', 3])
722            sage: S = A.initial_seed()
723            sage: T = S.mutate(1, inplace=False)
724            sage: hash(S) == hash(S)
725            True
726            sage: hash(S) == hash(T)
727            False
728        """
729        return hash(frozenset(self.g_vectors()))
730
731    def _repr_(self):
732        r"""
733        Return the string representation of self.
734
735        EXAMPLES::
736
737            sage: A = ClusterAlgebra(['A', 3])
738            sage: A.clear_computed_data()
739            sage: S = A.current_seed(); S
740            The initial seed of a Cluster Algebra with cluster variables x0, x1, x2
741             and no coefficients over Integer Ring
742            sage: S.mutate(0); S
743            The seed of a Cluster Algebra with cluster variables x0, x1, x2
744             and no coefficients over Integer Ring obtained from the initial
745             by mutating in direction 0
746            sage: S.mutate(1); S
747            The seed of a Cluster Algebra with cluster variables x0, x1, x2
748             and no coefficients over Integer Ring obtained from the initial
749             by mutating along the sequence [0, 1]
750        """
751        if self._path == []:
752            return "The initial seed of a %s" % str(self.parent())[2:]
753        elif len(self._path) == 1:
754            return "The seed of a %s obtained from the initial by mutating in direction %s" % (str(self.parent())[2:], str(self._path[0]))
755        else:
756            return "The seed of a %s obtained from the initial by mutating along the sequence %s" % (str(self.parent())[2:], str(self._path))
757
758    def parent(self):
759        r"""
760        Return the parent of self.
761
762        EXAMPLES::
763
764            sage: A = ClusterAlgebra(['B', 3])
765            sage: A.current_seed().parent() == A
766            True
767        """
768        return self._parent
769
770    def depth(self):
771        r"""
772        Return the length of a mutation sequence from the initial seed
773         of :meth:parent to self.
774
775        .. WARNING::
776
777            This is the length of the mutation sequence returned by
778            :meth:path_from_initial_seed, which need not be the
779            shortest possible.
780
781        EXAMPLES::
782
783            sage: A = ClusterAlgebra(['A', 2])
784            sage: S1 = A.initial_seed()
785            sage: S1.mutate([0, 1, 0, 1])
786            sage: S1.depth()
787            4
788            sage: S2 = A.initial_seed()
789            sage: S2.mutate(1)
790            sage: S2.depth()
791            1
792            sage: S1 == S2
793            True
794        """
795        return len(self._path)
796
797    def path_from_initial_seed(self):
798        r"""
799        Return a mutation sequence from the initial seed of :meth:parent
800        to self.
801
802        .. WARNING::
803
804            This is the path used to compute self and it does not
805            have to be the shortest possible.
806
807        EXAMPLES::
808
809            sage: A = ClusterAlgebra(['A', 2])
810            sage: S1 = A.initial_seed()
811            sage: S1.mutate([0, 1, 0, 1])
812            sage: S1.path_from_initial_seed()
813            [0, 1, 0, 1]
814            sage: S2 = A.initial_seed()
815            sage: S2.mutate(1)
816            sage: S2.path_from_initial_seed()
817            [1]
818            sage: S1 == S2
819            True
820        """
821        return copy(self._path)
822
823    def b_matrix(self):
824        r"""
825        Return the exchange matrix of self.
826
827        EXAMPLES::
828
829            sage: A = ClusterAlgebra(['A', 3])
830            sage: S = A.initial_seed()
831            sage: S.b_matrix()
832            [ 0  1  0]
833            [-1  0 -1]
834            [ 0  1  0]
835        """
836        return copy(self._B)
837
838    def c_matrix(self):
839        r"""
840        Return the matrix whose columns are the c-vectors of self.
841
842        EXAMPLES::
843
844            sage: A = ClusterAlgebra(['A', 3])
845            sage: S = A.initial_seed()
846            sage: S.c_matrix()
847            [1 0 0]
848            [0 1 0]
849            [0 0 1]
850        """
851        return copy(self._C)
852
853    def c_vector(self, j):
854        r"""
855        Return the j-th c-vector of self.
856
857        INPUT:
858
859        - j -- an integer in range(self.parent().rank());
860          the index of the c-vector to return
861
862        EXAMPLES::
863
864            sage: A = ClusterAlgebra(['A', 3])
865            sage: S = A.initial_seed()
866            sage: S.c_vector(0)
867            (1, 0, 0)
868            sage: S.mutate(0)
869            sage: S.c_vector(0)
870            (-1, 0, 0)
871            sage: S.c_vector(1)
872            (1, 1, 0)
873        """
874        return tuple(self._C.column(j))
875
876    def c_vectors(self):
877        r"""
878        Return all the c-vectors of self.
879
880        EXAMPLES::
881
882            sage: A = ClusterAlgebra(['A', 3])
883            sage: S = A.initial_seed()
884            sage: S.c_vectors()
885            [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
886        """
887        return list(map(tuple, self._C.columns()))
888
889    def g_matrix(self):
890        r"""
891        Return the matrix whose columns are the g-vectors of self.
892
893        EXAMPLES::
894
895            sage: A = ClusterAlgebra(['A', 3])
896            sage: S = A.initial_seed()
897            sage: S.g_matrix()
898            [1 0 0]
899            [0 1 0]
900            [0 0 1]
901        """
902        return copy(self._G)
903
904    def g_vector(self, j):
905        r"""
906        Return the j-th g-vector of self.
907
908        INPUT:
909
910        - j -- an integer in range(self.parent().rank());
911          the index of the g-vector to return
912
913        EXAMPLES::
914
915            sage: A = ClusterAlgebra(['A', 3])
916            sage: S = A.initial_seed()
917            sage: S.g_vector(0)
918            (1, 0, 0)
919        """
920        return tuple(self._G.column(j))
921
922    def g_vectors(self):
923        r"""
924        Return all the g-vectors of self.
925
926        EXAMPLES::
927
928            sage: A = ClusterAlgebra(['A', 3])
929            sage: S = A.initial_seed()
930            sage: S.g_vectors()
931            [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
932        """
933        return list(map(tuple, self._G.columns()))
934
935    def F_polynomial(self, j):
936        r"""
937        Return the j-th F-polynomial of self.
938
939        INPUT:
940
941        - j -- an integer in range(self.parent().rank());
942          the index of the F-polynomial to return
943
944        EXAMPLES::
945
946            sage: A = ClusterAlgebra(['A', 3])
947            sage: S = A.initial_seed()
948            sage: S.F_polynomial(0)
949            1
950        """
951        return self.parent().F_polynomial(self.g_vector(j))
952
953    def F_polynomials(self):
954        r"""
955        Return all the F-polynomials of self.
956
957        EXAMPLES::
958
959            sage: A = ClusterAlgebra(['A', 3])
960            sage: S = A.initial_seed()
961            sage: S.F_polynomials()
962            [1, 1, 1]
963        """
964        return [self.parent().F_polynomial(g) for g in self.g_vectors()]
965
966    def cluster_variable(self, j):
967        r"""
968        Return the j-th cluster variable of self.
969
970        INPUT:
971
972        - j -- an integer in range(self.parent().rank());
973          the index of the cluster variable to return
974
975        EXAMPLES::
976
977            sage: A = ClusterAlgebra(['A', 3])
978            sage: S = A.initial_seed()
979            sage: S.cluster_variable(0)
980            x0
981            sage: S.mutate(0)
982            sage: S.cluster_variable(0)
983            (x1 + 1)/x0
984        """
985        return self.parent().cluster_variable(self.g_vector(j))
986
987    def cluster_variables(self):
988        r"""
989        Return all the cluster variables of self.
990
991        EXAMPLES::
992
993            sage: A = ClusterAlgebra(['A', 3])
994            sage: S = A.initial_seed()
995            sage: S.cluster_variables()
996            [x0, x1, x2]
997        """
998        return [self.parent().cluster_variable(g) for g in self.g_vectors()]
999
1000    def mutate(self, direction, **kwargs):
1001        r"""
1002        Mutate self.
1003
1004        INPUT:
1005
1006        - direction -- in which direction(s) to mutate, it can be:
1007
1008          * an integer in range(self.rank()) to mutate in one direction only
1009          * an iterable of such integers to mutate along a sequence
1010          * a string "sinks" or "sources" to mutate at all sinks or sources simultaneously
1011
1012        - inplace -- bool (default True); whether to mutate in place or to return a new object
1013
1014        - mutating_F -- bool (default True); whether to compute
1015          F-polynomials while mutating
1016
1017        .. NOTE::
1018
1019            While knowing F-polynomials is essential to computing
1020            cluster variables, the process of mutating them is quite slow.
1021            If you care only about combinatorial data like g-vectors and
1022            c-vectors, setting mutating_F=False yields significant
1023            benefits in terms of speed.
1024
1025        EXAMPLES::
1026
1027            sage: A = ClusterAlgebra(['A', 2])
1028            sage: S = A.initial_seed()
1029            sage: S.mutate(0); S
1030            The seed of a Cluster Algebra with cluster variables x0, x1
1031             and no coefficients over Integer Ring obtained from the initial
1032             by mutating in direction 0
1033            sage: S.mutate(5)
1034            Traceback (most recent call last):
1035            ...
1036            ValueError: cannot mutate in direction 5
1037        """
1038        n = self.parent().rank()
1039
1040        # do we want to change self?
1041        inplace = kwargs.pop('inplace', True)
1042        if inplace:
1043            to_mutate = self
1044        else:
1045            to_mutate = copy(self)
1046
1047        # construct mutation sequence
1048        # if you change this be considerate and change also :class:ClusterAlgebra.mutate_initial
1049        if direction == "sinks":
1050            B = self.b_matrix()
1051            seq = [i for i in range(n) if all(x <= 0 for x in B.column(i))]
1052        elif direction == "sources":
1053            B = self.b_matrix()
1054            seq = [i for i in range(n) if all(x >= 0 for x in B.column(i))]
1055        else:
1056            try:
1057                seq = iter(direction)
1058            except TypeError:
1059                seq = iter((direction, ))
1060
1061        # are we mutating F-polynomials?
1062        mutating_F = kwargs.pop('mutating_F', True)
1063
1064        for k in seq:
1065            if k not in range(n):
1066                raise ValueError('cannot mutate in direction ' + str(k))
1067
1068            # store new mutation path
1069            if to_mutate._path != [] and to_mutate._path[-1] == k:
1070                to_mutate._path.pop()
1071            else:
1072                to_mutate._path.append(k)
1073
1074            # find sign of k-th c-vector
1075            if any(x > 0 for x in to_mutate._C.column(k)):
1076                eps = +1
1077            else:
1078                eps = -1
1079
1080            # store the g-vector to be mutated in case we are mutating F-polynomials also
1081            old_g_vector = to_mutate.g_vector(k)
1082
1083            # compute new G-matrix
1084            J = identity_matrix(n)
1085            for j in range(n):
1086                J[j, k] += max(0, -eps * to_mutate._B[j, k])
1087            J[k, k] = -1
1088            to_mutate._G = to_mutate._G * J
1089
1090            # path to new g-vector (we store the shortest encountered so far)
1091            g_vector = to_mutate.g_vector(k)
1092            if g_vector not in to_mutate.parent()._path_dict or len(to_mutate.parent()._path_dict[g_vector]) > len(to_mutate._path):
1093                to_mutate.parent()._path_dict[g_vector] = copy(to_mutate._path)
1094
1095            # compute F-polynomials
1096            if mutating_F and g_vector not in to_mutate.parent()._F_poly_dict:
1097                to_mutate.parent()._F_poly_dict[g_vector] = to_mutate._mutated_F(k, old_g_vector)
1098
1099            # compute new C-matrix
1100            J = identity_matrix(n)
1101            for j in range(n):
1102                J[k, j] += max(0, eps * to_mutate._B[k, j])
1103            J[k, k] = -1
1104            to_mutate._C = to_mutate._C * J
1105
1106            # compute new B-matrix
1107            to_mutate._B.mutate(k)
1108
1109        # return if we need to
1110        if not inplace:
1111            return to_mutate
1112
1113    def _mutated_F(self, k, old_g_vector):
1114        r"""
1115        Compute new F-polynomial obtained by mutating in direction k.
1116
1117        INPUT:
1118
1119        - k --  an integer in range(self.parent().rank());
1120          the direction in which we are mutating
1121
1122        - old_g_vector -- tuple; the k-th g-vector of self
1123          before mutating
1124
1125        .. NOTE::
1126
1127            This function is the bottleneck of :meth:mutate. The problem is
1128            that operations on polynomials are slow. One can get a significant
1129            speed boost by disabling this method calling :meth:mutate with
1130            mutating_F=False.
1131
1132        EXAMPLES::
1133
1134            sage: A = ClusterAlgebra(['A', 2])
1135            sage: S = A.initial_seed()
1136            sage: S.mutate(0)
1137            sage: S._mutated_F(0, (1, 0))
1138            u0 + 1
1139        """
1140        alg = self.parent()
1141        pos = alg._U(1)
1142        neg = alg._U(1)
1143        for j in range(alg.rank()):
1144            if self._C[j, k] > 0:
1145                pos *= alg._U.gen(j) ** self._C[j, k]
1146            else:
1147                neg *= alg._U.gen(j) ** (-self._C[j, k])
1148            if self._B[j, k] > 0:
1149                pos *= self.F_polynomial(j) ** self._B[j, k]
1150            elif self._B[j, k] < 0:
1151                neg *= self.F_polynomial(j) ** (-self._B[j, k])
1152        return (pos + neg) / alg.F_polynomial(old_g_vector)
1153
1154##############################################################################
1155# Cluster algebras
1156##############################################################################
1157
1158
1159class ClusterAlgebra(Parent, UniqueRepresentation):
1160    r"""
1161    A Cluster Algebra.
1162
1163    INPUT:
1164
1165    - data -- some data defining a cluster algebra; it can be anything
1166      that can be parsed by :class:ClusterQuiver
1167
1168    - scalars -- a ring (default \ZZ); the scalars over
1169      which the cluster algebra is defined
1170
1171    - cluster_variable_prefix -- string (default 'x'); it needs to be
1172      a valid variable name
1173
1174    - cluster_variable_names -- a list of strings; each element needs
1175      to be a valid variable name;  supersedes cluster_variable_prefix
1176
1177    - coefficient_prefix -- string (default 'y'); it needs to be
1178      a valid variable name.
1179
1180    - coefficient_names -- a list of strings; each element needs
1181      to be a valid variable name; supersedes cluster_variable_prefix
1182
1183    - principal_coefficients -- bool (default False); supersedes any
1184      coefficient defined by data
1185
1186    ALGORITHM:
1187
1188    The implementation is mainly based on [FZ2007]_ and [NZ2012]_.
1189
1190    EXAMPLES::
1191
1192        sage: B = matrix([(0, 1, 0, 0), (-1, 0, -1, 0), (0, 1, 0, 1), (0, 0, -2, 0), (-1, 0, 0, 0), (0, -1, 0, 0)])
1193        sage: A = ClusterAlgebra(B); A
1194        A Cluster Algebra with cluster variables x0, x1, x2, x3
1195         and coefficients y0, y1 over Integer Ring
1196        sage: A.gens()
1197        (x0, x1, x2, x3, y0, y1)
1198        sage: A = ClusterAlgebra(['A', 2]); A
1199        A Cluster Algebra with cluster variables x0, x1 and no coefficients
1200         over Integer Ring
1201        sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True); A.gens()
1202        (x0, x1, y0, y1)
1203        sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True, coefficient_prefix='x'); A.gens()
1204        (x0, x1, x2, x3)
1205        sage: A = ClusterAlgebra(['A', 3], principal_coefficients=True, cluster_variable_names=['a', 'b', 'c']); A.gens()
1206        (a, b, c, y0, y1, y2)
1207        sage: A = ClusterAlgebra(['A', 3], principal_coefficients=True, cluster_variable_names=['a', 'b'])
1208        Traceback (most recent call last):
1209        ...
1210        ValueError: cluster_variable_names should be a list of 3 valid variable names
1211        sage: A = ClusterAlgebra(['A', 3], principal_coefficients=True, coefficient_names=['a', 'b', 'c']); A.gens()
1212        (x0, x1, x2, a, b, c)
1213        sage: A = ClusterAlgebra(['A', 3], principal_coefficients=True, coefficient_names=['a', 'b'])
1214        Traceback (most recent call last):
1215        ...
1216        ValueError: coefficient_names should be a list of 3 valid variable names
1217    """
1218
1219    @staticmethod
1220    def __classcall__(self, data, **kwargs):
1221        r"""
1222        Preparse input to make it hashable.
1223
1224        EXAMPLES::
1225
1226            sage: A = ClusterAlgebra(['A', 2]); A   # indirect doctest
1227            A Cluster Algebra with cluster variables x0, x1 and no coefficients
1228            over Integer Ring
1229        """
1230        Q = ClusterQuiver(data)
1231        for key in kwargs:
1232            if isinstance(kwargs[key], list):
1233                kwargs[key] = tuple(kwargs[key])
1234        return super(ClusterAlgebra, self).__classcall__(self, Q, **kwargs)
1235
1236    def __init__(self, Q, **kwargs):
1237        """
1238        Initialize self.
1239
1240        TESTS::
1241
1242            sage: B = matrix([(0, 1, 0, 0), (-1, 0, -1, 0), (0, 1, 0, 1), (0, 0, -2, 0), (-1, 0, 0, 0), (0, -1, 0, 0)])
1243            sage: A = ClusterAlgebra(B)
1244            sage: A.clear_computed_data()
1245            sage: TestSuite(A).run()
1246            sage: A = ClusterAlgebra(['A', 2])
1247            sage: A.clear_computed_data()
1248            sage: TestSuite(A).run()
1249            sage: A = ClusterAlgebra(['A', 3], principal_coefficients=True)
1250            sage: A.clear_computed_data()
1251            sage: TestSuite(A).run()
1252            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True, coefficient_prefix='x')
1253            sage: A.clear_computed_data()
1254            sage: TestSuite(A).run()
1255            sage: A = ClusterAlgebra(['A', 3], principal_coefficients=True, cluster_variable_names=['a','b','c'])
1256            sage: A.clear_computed_data()
1257            sage: TestSuite(A).run()
1258            sage: A = ClusterAlgebra(['A', 3], principal_coefficients=True, coefficient_names=['a','b','c'])
1259            sage: A.clear_computed_data()
1260            sage: TestSuite(A).run()
1261        """
1262        # Parse input
1263        self._n = Q.n()
1264        I = identity_matrix(self._n)
1265        if kwargs.get('principal_coefficients', False):
1266            M0 = I
1267        else:
1268            M0 = Q.b_matrix()[self._n:, :]
1269        self._B0 = block_matrix([[Q.b_matrix()[:self._n, :]], [M0]])
1270        m = M0.nrows()
1271        if not kwargs.get('ex_d', False):
1272            self._ex_d = [ ]
1273            for i in range(self._n):
1274                self._ex_d.append(1)
1275            self._ex_d = tuple(self._ex_d)
1276        else:
1277             if len(kwargs.get('ex_d')) == self._n:
1278                 self._ex_d = kwargs.get('ex_d')
1279        # Ambient space for F-polynomials
1280        # NOTE: for speed purposes we need to have QQ here instead of the more
1281        # natural ZZ. The reason is that _mutated_F is faster if we do not cast
1282        # the result to polynomials but then we get "rational" coefficients
1283        self._U = PolynomialRing(QQ, ['u%s' % i for i in range(self._n)])
1284
1285        # Setup infrastructure to store computed data
1286        self.clear_computed_data()
1287
1288        # Determine the names of the initial cluster variables
1289        variables_prefix = kwargs.get('cluster_variable_prefix', 'x')
1290        variables = list(kwargs.get('cluster_variable_names', [variables_prefix + str(i) for i in range(self._n)]))
1291        if len(variables) != self._n:
1292            raise ValueError("cluster_variable_names should be a list of %d valid variable names" % self._n)
1293
1294        # Determine scalars
1295        scalars = kwargs.get('scalars', ZZ)
1296
1297        # Determine coefficients and base
1298        if m > 0:
1299            coefficient_prefix = kwargs.get('coefficient_prefix', 'y')
1300            if coefficient_prefix == variables_prefix:
1301                offset = self._n
1302            else:
1303                offset = 0
1304            coefficients = list(kwargs.get('coefficient_names', [coefficient_prefix + str(i) for i in range(offset, m + offset)]))
1305            if len(coefficients) != m:
1306                raise ValueError("coefficient_names should be a list of %d valid variable names" % m)
1307            base = LaurentPolynomialRing(scalars, coefficients)
1308        else:
1309            base = scalars
1310            coefficients = []
1311
1312        # Have we got principal coefficients?
1313        if M0 == I:
1314            self.Element = PrincipalClusterAlgebraElement
1315        else:
1316            self.Element = ClusterAlgebraElement
1317
1318        # Setup Parent and ambient
1319        self._ambient = LaurentPolynomialRing(scalars, variables + coefficients)
1320        Parent.__init__(self, base=base, category=Rings(scalars).Commutative().Subobjects(),
1321                        names=variables + coefficients)
1322
1323        # Data to compute cluster variables using separation of additions
1324        # NOTE: storing both _B0 as rectangular matrix and _yhat is redundant.
1325        # We keep both around for speed purposes.
1326        self._y = {self._U.gen(j): prod(self._base.gen(i) ** M0[i, j] for i in range(m))
1327                   for j in range(self._n)}
1328        self._yhat = {self._U.gen(j): prod(self._ambient.gen(i) ** self._B0[i, j]
1329                                           for i in range(self._n + m))
1330                      for j in range(self._n)}
1331
1332        # Register embedding into self.ambient()
1333        embedding = SetMorphism(Hom(self, self.ambient()), lambda x: x.lift())
1334        self._populate_coercion_lists_(embedding=embedding)
1335
1336    def _repr_(self):
1337        r"""
1338        Return the string representation of self.
1339
1340        EXAMPLES::
1341
1342            sage: A = ClusterAlgebra(matrix(1), principal_coefficients=True); A
1343            A Cluster Algebra with cluster variable x0
1344             and coefficient y0 over Integer Ring
1345            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True); A
1346            A Cluster Algebra with cluster variables x0, x1
1347             and coefficients y0, y1 over Integer Ring
1348        """
1349        var_names = self.initial_cluster_variable_names()
1350        var_names = (" " if len(var_names) == 1 else "s ") + ", ".join(var_names)
1351        coeff_names = self.coefficient_names()
1352        coeff_prefix = " and" + (" " if len(coeff_names) > 0 else " no ") + "coefficient"
1353        coeff = coeff_prefix + (" " if len(coeff_names) == 1 else "s ") + ", ".join(coeff_names) + (" " if len(coeff_names) > 0 else "")
1354        return "A Cluster Algebra with cluster variable" + var_names + coeff + "over " + repr(self.scalars())
1355
1356    def _an_element_(self):
1357        r"""
1358        Return an element of self.
1359
1360        EXAMPLES::
1361
1362            sage: A = ClusterAlgebra(['A', 2])
1363            sage: A.an_element()
1364            x0
1365        """
1366        return self.initial_cluster_variable(0)
1367
1368    def _coerce_map_from_(self, other):
1369        r"""
1370        Test whether there is a coercion from other to self.
1371
1372        ALGORITHM:
1373
1374        If other is an instance of :class:ClusterAlgebra then allow
1375        coercion if other.ambient() can be coerced into self.ambient()
1376        and other can be obtained from self by permuting variables
1377        and coefficients and/or freezing some initial cluster variables.
1378
1379        Otherwise allow anything that coerces into self.base() to coerce
1380        into self.
1381
1382        EXAMPLES::
1383
1384            sage: B1 = matrix([(0, 1, 0, 0), (-1, 0, -1, 0), (0, 1, 0, 1), (0, 0, -2, 0), (-1, 0, 0, 0), (0, -1, 0, 0)])
1385            sage: B2 = B1.matrix_from_columns([0, 1, 2])
1386            sage: A1 = ClusterAlgebra(B1, coefficient_prefix='x')
1387            sage: A2 = ClusterAlgebra(B2, coefficient_prefix='x')
1388            sage: A1.has_coerce_map_from(A2)
1389            True
1390            sage: A2.has_coerce_map_from(A1)
1391            False
1392            sage: f = A1.coerce_map_from(A2)
1393            sage: seq = A2.find_g_vector((-1, 1, -1)); seq  # random
1394            [0, 2, 1]
1395            sage: S = A1.initial_seed(); S.mutate(seq)
1396            sage: S.cluster_variable(seq[-1]) == f(A2.cluster_variable((-1, 1, -1)))
1397            True
1398            sage: B3 = B1.matrix_from_columns([1, 2, 3]); B3
1399            [ 1  0  0]
1400            [ 0 -1  0]
1401            [ 1  0  1]
1402            [ 0 -2  0]
1403            [ 0  0  0]
1404            [-1  0  0]
1405            sage: G = PermutationGroup(['(1, 2, 3, 4)'])
1406            sage: B3.permute_rows(G.gen(0)); B3
1407            [ 0 -1  0]
1408            [ 1  0  1]
1409            [ 0 -2  0]
1410            [ 1  0  0]
1411            [ 0  0  0]
1412            [-1  0  0]
1413            sage: A3 = ClusterAlgebra(B3, cluster_variable_names=['x1', 'x2', 'x3'], coefficient_names=['x0', 'x4', 'x5'])
1414            sage: A1.has_coerce_map_from(A3)
1415            True
1416            sage: g = A1.coerce_map_from(A3)
1417            sage: seq1 = A3.find_g_vector((1, -2, 2))
1418            sage: seq2 = [G.gen(0)(x + 1) - 1 for x in seq1 ]
1419            sage: S = A1.initial_seed(); S.mutate(seq2)
1420            sage: S.cluster_variable(seq2[-1]) == g(A3.cluster_variable((1, -2, 2)))
1421            True
1422
1423         Check that :trac:23654 is fixed::
1424
1425            sage: A = ClusterAlgebra(['A',2])
1426            sage: AA = ClusterAlgebra(['A',3])
1427            sage: A.has_coerce_map_from(AA)
1428            False
1429        """
1430        if isinstance(other, ClusterAlgebra):
1431            gen_s = self.gens()
1432            gen_o = other.gens()
1433            if len(gen_s) == len(gen_o):
1434                f = self.ambient().coerce_map_from(other.ambient())
1435                if f is not None:
1436                    perm = Permutation([gen_s.index(self(f(v))) + 1 for v in gen_o])
1437                    n = self.rank()
1438                    M = self._B0[n:, :]
1439                    m = M.nrows()
1440                    B = block_matrix([[self.b_matrix(), -M.transpose()], [M, matrix(m)]])
1441                    B.permute_rows_and_columns(perm, perm)
1442                    return B[:, :other.rank()] == other._B0
1443
1444        # everything that is in the base can be coerced to self
1445        return self.base().has_coerce_map_from(other)
1446
1447    def rank(self):
1448        r"""
1449        Return the rank of self, i.e. the number of cluster variables
1450        in any seed.
1451
1452        EXAMPLES::
1453
1454            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True); A
1455            A Cluster Algebra with cluster variables x0, x1
1456             and coefficients y0, y1 over Integer Ring
1457            sage: A.rank()
1458            2
1459        """
1460        return self._n
1461
1462    def current_seed(self):
1463        r"""
1464        Return the current seed of self.
1465
1466        EXAMPLES::
1467
1468            sage: A = ClusterAlgebra(['A', 2])
1469            sage: A.clear_computed_data()
1470            sage: A.current_seed()
1471            The initial seed of a Cluster Algebra with cluster variables x0, x1
1472             and no coefficients over Integer Ring
1473        """
1474        return self._seed
1475
1476    def set_current_seed(self, seed):
1477        r"""
1478        Set the value reported by :meth:current_seed to seed,
1479        if it makes sense.
1480
1481        INPUT:
1482
1483        - seed -- a :class:ClusterAlgebraSeed
1484
1485        EXAMPLES::
1486
1487            sage: A = ClusterAlgebra(['A', 2])
1488            sage: A.clear_computed_data()
1489            sage: S = copy(A.current_seed())
1490            sage: S.mutate([0, 1, 0])
1491            sage: A.current_seed() == S
1492            False
1493            sage: A.set_current_seed(S)
1494            sage: A.current_seed() == S
1495            True
1496            sage: A1 = ClusterAlgebra(['B', 2])
1497            sage: A.set_current_seed(A1.initial_seed())
1498            Traceback (most recent call last):
1499            ...
1500            ValueError: This is not a seed in this cluster algebra
1501        """
1502        if self.contains_seed(seed):
1503            self._seed = seed
1504        else:
1505            raise ValueError("This is not a seed in this cluster algebra")
1506
1507    def reset_current_seed(self):
1508        r"""
1509        Reset the value reported by :meth:current_seed
1510        to :meth:initial_seed.
1511
1512        EXAMPLES::
1513
1514            sage: A = ClusterAlgebra(['A', 2])
1515            sage: A.clear_computed_data()
1516            sage: A.current_seed().mutate([1, 0])
1517            sage: A.current_seed() == A.initial_seed()
1518            False
1519            sage: A.reset_current_seed()
1520            sage: A.current_seed() == A.initial_seed()
1521            True
1522        """
1523        self._seed = self.initial_seed()
1524
1525    def clear_computed_data(self):
1526        r"""
1527        Clear the cache of computed g-vectors and F-polynomials
1528        and reset both the current seed and the exploring iterator.
1529
1530        EXAMPLES::
1531
1532            sage: A = ClusterAlgebra(['A', 2])
1533            sage: A.clear_computed_data()
1534            sage: sorted(A.g_vectors_so_far())
1535            [(0, 1), (1, 0)]
1536            sage: A.current_seed().mutate([1, 0])
1537            sage: sorted(A.g_vectors_so_far())
1538            [(-1, 0), (0, -1), (0, 1), (1, 0)]
1539            sage: A.clear_computed_data()
1540            sage: sorted(A.g_vectors_so_far())
1541            [(0, 1), (1, 0)]
1542        """
1543        I = identity_matrix(self._n)
1544        self._path_dict = dict((v, []) for v in map(tuple, I.columns()))
1545        self._F_poly_dict = dict((v, self._U(1)) for v in self._path_dict)
1546        self.reset_current_seed()
1547        self.reset_exploring_iterator()
1548
1549    def contains_seed(self, seed):
1550        r"""
1551        Test if seed is a seed of self.
1552
1553        INPUT:
1554
1555        - seed -- a :class:ClusterAlgebraSeed
1556
1557        EXAMPLES::
1558
1559            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True); A
1560            A Cluster Algebra with cluster variables x0, x1 and coefficients y0, y1 over Integer Ring
1561            sage: S = copy(A.current_seed())
1562            sage: A.contains_seed(S)
1563            True
1564        """
1565        computed_sd = self.initial_seed()
1566        computed_sd.mutate(seed._path, mutating_F=False)
1567        return computed_sd == seed
1568
1569    def initial_seed(self):
1570        r"""
1571        Return the initial seed of self.
1572
1573        EXAMPLES::
1574
1575            sage: A = ClusterAlgebra(['A', 2])
1576            sage: A.initial_seed()
1577            The initial seed of a Cluster Algebra with cluster variables x0, x1 and no coefficients over Integer Ring
1578        """
1579        n = self.rank()
1580        I = identity_matrix(n)
1581        return ClusterAlgebraSeed(self.b_matrix(), I, I, self._ex_d, self)
1582
1583    def b_matrix(self):
1584        r"""
1585        Return the initial exchange matrix of self.
1586
1587        EXAMPLES::
1588
1589            sage: A = ClusterAlgebra(['A', 2])
1590            sage: A.b_matrix()
1591            [ 0  1]
1592            [-1  0]
1593        """
1594        n = self.rank()
1595        return copy(self._B0[:n, :])
1596
1597    def g_vectors(self, mutating_F=True):
1598        r"""
1599        Return an iterator producing all the g-vectors of self.
1600
1601        INPUT:
1602
1603        - mutating_F -- bool (default True); whether to compute
1604          F-polynomials; disable this for speed considerations
1605
1606        ALGORITHM:
1607
1608        This method does not use the caching framework provided by self,
1609        but recomputes all the g-vectors from scratch. On the other hand it
1610        stores the results so that other methods like :meth:g_vectors_so_far
1611        can access them afterwards.
1612
1613        EXAMPLES::
1614
1615            sage: A = ClusterAlgebra(['A', 3])
1616            sage: len(list(A.g_vectors()))
1617            9
1618        """
1619        seeds = self.seeds(mutating_F=mutating_F)
1620        found_so_far = set()
1621        for g in next(seeds).g_vectors():
1623            yield g
1624        for S in seeds:
1625            j = S.path_from_initial_seed()[-1]
1626            g = S.g_vector(j)
1627            if g not in found_so_far:
1629                yield g
1630
1631    def cluster_variables(self):
1632        r"""
1633        Return an iterator producing all the cluster variables of self.
1634
1635        ALGORITHM:
1636
1637        This method does not use the caching framework provided by self,
1638        but recomputes all the cluster variables from scratch. On the other
1639        hand it stores the results so that other methods like
1640        :meth:cluster_variables_so_far can access them afterwards.
1641
1642        EXAMPLES::
1643
1644            sage: A = ClusterAlgebra(['A', 3])
1645            sage: len(list(A.cluster_variables()))
1646            9
1647        """
1648        return map(self.cluster_variable, self.g_vectors())
1649
1650    def F_polynomials(self):
1651        r"""
1652        Return an iterator producing all the F_polynomials of self.
1653
1654        ALGORITHM:
1655
1656        This method does not use the caching framework provided by self,
1657        but recomputes all the F-polynomials from scratch. On the other hand
1658        it stores the results so that other methods like
1659        :meth:F_polynomials_so_far can access them afterwards.
1660
1661        EXAMPLES::
1662
1663            sage: A = ClusterAlgebra(['A', 3])
1664            sage: len(list(A.F_polynomials()))
1665            9
1666        """
1667        return map(self.F_polynomial, self.g_vectors())
1668
1669    def g_vectors_so_far(self):
1670        r"""
1671        Return a list of the g-vectors of cluster variables encountered so far.
1672
1673        EXAMPLES::
1674
1675            sage: A = ClusterAlgebra(['A', 2])
1676            sage: A.clear_computed_data()
1677            sage: A.current_seed().mutate(0)
1678            sage: sorted(A.g_vectors_so_far())
1679            [(-1, 1), (0, 1), (1, 0)]
1680        """
1681        return list(self._path_dict)
1682
1683    def cluster_variables_so_far(self):
1684        r"""
1685        Return a list of the cluster variables encountered so far.
1686
1687        EXAMPLES::
1688
1689            sage: A = ClusterAlgebra(['A', 2])
1690            sage: A.clear_computed_data()
1691            sage: A.current_seed().mutate(0)
1692            sage: sorted(A.cluster_variables_so_far(), key=str)
1693            [(x1 + 1)/x0, x0, x1]
1694        """
1695        return [self.cluster_variable(v) for v in self.g_vectors_so_far()]
1696
1697    def F_polynomials_so_far(self):
1698        r"""
1699        Return a list of the F-polynomials encountered so far.
1700
1701        EXAMPLES::
1702
1703            sage: A = ClusterAlgebra(['A', 2])
1704            sage: A.clear_computed_data()
1705            sage: A.current_seed().mutate(0)
1706            sage: sorted(A.F_polynomials_so_far(), key=str)
1707            [1, 1, u0 + 1]
1708        """
1709        return list(self._F_poly_dict.values())
1710
1711    @cached_method(key=lambda a, b: tuple(b))
1712    def cluster_variable(self, g_vector):
1713        r"""
1714        Return the cluster variable with g-vector g_vector if it has
1715        been found.
1716
1717        INPUT:
1718
1719        - g_vector -- tuple; the g-vector of the cluster variable to return
1720
1721        ALGORITHM:
1722
1723        This function computes cluster variables from their g-vectors and
1724        F-polynomials using the "separation of additions" formula of
1725        Theorem 3.7 in [FZ2007]_.
1726
1727        EXAMPLES::
1728
1729            sage: A = ClusterAlgebra(['A', 2])
1730            sage: A.initial_seed().mutate(0)
1731            sage: A.cluster_variable((-1, 1))
1732            (x1 + 1)/x0
1733        """
1734        g_vector = tuple(g_vector)
1735        F = self.F_polynomial(g_vector)
1736        F_std = F.subs(self._yhat)
1737        g_mon = prod(self.ambient().gen(i) ** g_vector[i] for i in range(self.rank()))
1738        F_trop = self.ambient()(F.subs(self._y))._fraction_pair()[1]
1739        return self.retract(g_mon * F_std * F_trop)
1740
1741    def F_polynomial(self, g_vector):
1742        r"""
1743        Return the F-polynomial with g-vector g_vector if it has
1744        been found.
1745
1746        INPUT:
1747
1748        - g_vector -- tuple; the g-vector of the F-polynomial to return
1749
1750        EXAMPLES::
1751
1752            sage: A = ClusterAlgebra(['A', 2])
1753            sage: A.clear_computed_data()
1754            sage: A.F_polynomial((-1, 1))
1755            Traceback (most recent call last):
1756            ...
1757            KeyError: 'the g-vector (-1, 1) has not been found yet'
1758            sage: A.initial_seed().mutate(0, mutating_F=False)
1759            sage: A.F_polynomial((-1, 1))
1760            Traceback (most recent call last):
1761            ...
1762            KeyError: 'the F-polynomial with g-vector (-1, 1) has not been computed yet;
1763             you can compute it by mutating from the initial seed along the sequence [0]'
1764            sage: A.initial_seed().mutate(0)
1765            sage: A.F_polynomial((-1, 1))
1766            u0 + 1
1767        """
1768        g_vector = tuple(g_vector)
1769        try:
1770            return self._F_poly_dict[g_vector]
1771        except KeyError:
1772            if g_vector in self._path_dict:
1773                msg = "the F-polynomial with g-vector {} has not been computed yet; ".format(g_vector)
1774                msg += "you can compute it by mutating from the initial seed along the sequence "
1775                msg += str(self._path_dict[g_vector])
1776                raise KeyError(msg)
1777            else:
1778                raise KeyError("the g-vector %s has not been found yet" % str(g_vector))
1779
1780    def find_g_vector(self, g_vector, depth=infinity):
1781        r"""
1782        Return a mutation sequence to obtain a seed containing the g-vector g_vector from the initial seed.
1783
1784        INPUT:
1785
1786        - g_vector -- a tuple: the g-vector to find
1787        - depth -- a positive integer or infinity (default infinity);
1788          the maximum distance from self.current_seed to reach
1789
1790        OUTPUT:
1791
1792        This function returns a list of integers if it can find g_vector,
1793        otherwise it returns None.  If the exploring iterator stops, it
1794        means that the algebra is of finite type and g_vector is not the
1795        g-vector of any cluster variable. In this case the function resets the
1796        iterator and raises an error.
1797
1798        EXAMPLES::
1799
1800            sage: A = ClusterAlgebra(['G', 2], principal_coefficients=True)
1801            sage: A.clear_computed_data()
1802            sage: A.find_g_vector((-2, 3), depth=2)
1803            sage: A.find_g_vector((-2, 3), depth=3)
1804            [0, 1, 0]
1805            sage: A.find_g_vector((1, 1), depth=3)
1806            sage: A.find_g_vector((1, 1), depth=4)
1807            Traceback (most recent call last):
1808            ...
1809            ValueError: (1, 1) is not the g-vector of any cluster variable of a
1810             Cluster Algebra with cluster variables x0, x1 and coefficients y0, y1
1811             over Integer Ring
1812        """
1813        g_vector = tuple(g_vector)
1814        while g_vector not in self.g_vectors_so_far() and self._explored_depth <= depth:
1815            try:
1816                seed = next(self._sd_iter)
1817                if isinstance(seed, ClusterAlgebraSeed):
1818                    self._explored_depth = seed.depth()
1819                else:
1820                    # We got an exception because self._sd_iter caught a KeyboardInterrupt, let's raise it again
1821                    raise seed
1822            except StopIteration:
1823                # Unless self._sd_iter has been manually altered, we checked
1824                # all the seeds of self and did not find g_vector.
1825                # Do some house cleaning before failing
1826                self.reset_exploring_iterator()
1827                raise ValueError("%s is not the g-vector of any cluster variable of a %s" % (str(g_vector), str(self)[2:]))
1828        return copy(self._path_dict.get(g_vector, None))
1829
1830    def ambient(self):
1831        r"""
1832        Return the Laurent polynomial ring containing self.
1833
1834        EXAMPLES::
1835
1836            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1837            sage: A.ambient()
1838            Multivariate Laurent Polynomial Ring in x0, x1, y0, y1 over Integer Ring
1839        """
1840        return self._ambient
1841
1842    def scalars(self):
1843        r"""
1844        Return the ring of scalars over which self is defined.
1845
1846        EXAMPLES::
1847
1848            sage: A = ClusterAlgebra(['A', 2])
1849            sage: A.scalars()
1850            Integer Ring
1851        """
1852        return self.base().base()
1853
1854    def lift(self, x):
1855        r"""
1856        Return x as an element of :meth:ambient.
1857
1858        EXAMPLES::
1859
1860            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1861            sage: x = A.cluster_variable((1, 0))
1862            sage: A.lift(x).parent()
1863            Multivariate Laurent Polynomial Ring in x0, x1, y0, y1 over Integer Ring
1864        """
1865        return self.ambient()(x.value)
1866
1867    def retract(self, x):
1868        r"""
1869        Return x as an element of self.
1870
1871        EXAMPLES::
1872
1873            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1874            sage: L = A.ambient()
1875            sage: x = L.gen(0)
1876            sage: A.retract(x).parent()
1877            A Cluster Algebra with cluster variables x0, x1 and coefficients y0, y1 over Integer Ring
1878        """
1879        return self(x)
1880
1881    @cached_method
1882    def gens(self):
1883        r"""
1884        Return the list of initial cluster variables and coefficients of self.
1885
1886        EXAMPLES::
1887
1888            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1889            sage: A.gens()
1890            (x0, x1, y0, y1)
1891            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True, coefficient_prefix='x')
1892            sage: A.gens()
1893            (x0, x1, x2, x3)
1894        """
1895        return tuple(map(self.retract, self.ambient().gens()))
1896
1897    def coefficient(self, j):
1898        r"""
1899        Return the j-th coefficient of self.
1900
1901        INPUT:
1902
1903        - j -- an integer in range(self.parent().rank());
1904          the index of the coefficient to return
1905
1906        EXAMPLES::
1907
1908            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1909            sage: A.coefficient(0)
1910            y0
1911        """
1912        if not isinstance(self.base(), LaurentPolynomialRing_generic):
1913            raise ValueError("generator not defined")
1914        return self.retract(self.base().gen(j))
1915
1916    @cached_method
1917    def coefficients(self):
1918        r"""
1919        Return the list of coefficients of self.
1920
1921        EXAMPLES::
1922
1923            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1924            sage: A.coefficients()
1925            (y0, y1)
1926            sage: A1 = ClusterAlgebra(['B', 2])
1927            sage: A1.coefficients()
1928            ()
1929        """
1930        if isinstance(self.base(), LaurentPolynomialRing_generic):
1931            return tuple(map(self.retract, self.base().gens()))
1932        else:
1933            return ()
1934
1935    def coefficient_names(self):
1936        r"""
1937        Return the list of coefficient names.
1938
1939        EXAMPLES::
1940
1941            sage: A = ClusterAlgebra(['A', 3])
1942            sage: A.coefficient_names()
1943            ()
1944            sage: A1 = ClusterAlgebra(['B', 2], principal_coefficients=True)
1945            sage: A1.coefficient_names()
1946            ('y0', 'y1')
1947            sage: A2 = ClusterAlgebra(['C', 3], principal_coefficients=True, coefficient_prefix='x')
1948            sage: A2.coefficient_names()
1949            ('x3', 'x4', 'x5')
1950        """
1951        return self.variable_names()[self.rank():]
1952
1953    def initial_cluster_variable(self, j):
1954        r"""
1955        Return the j-th initial cluster variable of self.
1956
1957        INPUT:
1958
1959        - j -- an integer in range(self.parent().rank());
1960          the index of the cluster variable to return
1961
1962        EXAMPLES::
1963
1964            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1965            sage: A.initial_cluster_variable(0)
1966            x0
1967        """
1968        return self.retract(self.ambient().gen(j))
1969
1970    @cached_method
1971    def initial_cluster_variables(self):
1972        r"""
1973        Return the list of initial cluster variables of self.
1974
1975        EXAMPLES::
1976
1977            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1978            sage: A.initial_cluster_variables()
1979            (x0, x1)
1980        """
1981        return tuple(map(self.retract, self.ambient().gens()[:self.rank()]))
1982
1983    def initial_cluster_variable_names(self):
1984        r"""
1985        Return the list of initial cluster variable names.
1986
1987        EXAMPLES::
1988
1989            sage: A = ClusterAlgebra(['A', 2], principal_coefficients=True)
1990            sage: A.initial_cluster_variable_names()
1991            ('x0', 'x1')
1992            sage: A1 = ClusterAlgebra(['B', 2], cluster_variable_prefix='a')
1993            sage: A1.initial_cluster_variable_names()
1994            ('a0', 'a1')
1995        """
1996        return self.variable_names()[:self.rank()]
1997
1998    def seeds(self, **kwargs):
1999        r"""
2000        Return an iterator running over seeds of self.
2001
2002        INPUT:
2003
2004        - from_current_seed -- bool (default False); whether to start
2005          the iterator from :meth:current_seed or :meth:initial_seed
2006
2007        - mutating_F -- bool (default True); whether to compute
2008          F-polynomials also; disable this for speed considerations
2009
2010        - allowed_directions -- iterable of integers
2011          (default range(self.rank())); the directions in which to mutate
2012
2013        - depth -- a positive integer or infinity (default infinity);
2014          the maximum depth at which to stop searching
2015
2016        - catch_KeyboardInterrupt -- bool (default False); whether to
2017          catch KeyboardInterrupt and return it rather then raising an
2018          exception -- this allows the iterator returned by this method to be
2019          resumed after being interrupted
2020
2021        ALGORITHM:
2022
2023        This function traverses the exchange graph in a breadth-first search.
2024
2025        EXAMPLES::
2026
2027            sage: A = ClusterAlgebra(['A', 4])
2028            sage: A.clear_computed_data()
2029            sage: seeds = A.seeds(allowed_directions=[3, 0, 1])
2030            sage: _ = list(seeds)
2031            sage: sorted(A.g_vectors_so_far())
2032            [(-1, 0, 0, 0),
2033             (-1, 1, 0, 0),
2034             (0, -1, 0, 0),
2035             (0, 0, 0, -1),
2036             (0, 0, 0, 1),
2037             (0, 0, 1, 0),
2038             (0, 1, 0, 0),
2039             (1, 0, 0, 0)]
2040        """
2041        # should we begin from the current seed?
2042        if kwargs.get('from_current_seed', False):
2043            seed = copy(self.current_seed())
2044        else:
2045            seed = self.initial_seed()
2046
2047        # yield first seed
2048        yield seed
2049
2050        # keep track of depth
2051        depth_counter = 0
2052
2053        # do we mutate F-polynomials?
2054        mutating_F = kwargs.get('mutating_F', True)
2055
2056        # which directions are we allowed to mutate into
2057        allowed_dirs = sorted(kwargs.get('allowed_directions',
2058                                         range(self.rank())))
2059
2060        # setup seeds storage
2061        cl = frozenset(seed.g_vectors())
2062        clusters = {}
2063        clusters[cl] = [seed, copy(allowed_dirs)]
2064
2066        gets_bigger = True
2067        while gets_bigger and depth_counter < kwargs.get('depth', infinity):
2068            # remember if we got a new seed
2069            gets_bigger = False
2070
2071            for cl in list(clusters):
2072                sd, directions = clusters[cl]
2073                while directions:
2074                    try:
2075                        # we can mutate in some direction
2076                        i = directions.pop()
2077                        new_sd = sd.mutate(i, inplace=False, mutating_F=mutating_F)
2078                        new_cl = frozenset(new_sd.g_vectors())
2079                        if new_cl in clusters:
2080                            # we already had new_sd, make sure it does not mutate to sd during next round
2081                            j = clusters[new_cl][0].g_vectors().index(new_sd.g_vector(i))
2082                            try:
2083                                clusters[new_cl][1].remove(j)
2084                            except ValueError:
2085                                pass
2086                        else:
2087                            # we got a new seed
2088                            gets_bigger = True
2089                            # next round do not mutate back to sd and make sure we only walk three sides of squares
2090                            new_directions = [j for j in allowed_dirs if j > i or new_sd.b_matrix()[j, i] != 0]
2091                            clusters[new_cl] = [new_sd, new_directions]
2092                            yield new_sd
2093                    except KeyboardInterrupt as e:
2094                        if kwargs.get('catch_KeyboardInterrupt', False):
2095                            print("caught a KeyboardInterrupt; cleaning up before returning")
2096                            # mutation in direction i was not completed; put it back in for next round
2097                            directions.append(i)
2098                            yield e
2099                            continue
2100                        else:
2101                            raise e
2102            # we went one step deeper
2103            depth_counter += 1
2104
2105    def reset_exploring_iterator(self, mutating_F=True):
2106        r"""
2107        Reset the iterator used to explore self.
2108
2109        INPUT:
2110
2111        - mutating_F -- bool (default True); whether to also compute
2112          F-polynomials; disable this for speed considerations
2113
2114        EXAMPLES::
2115
2116            sage: A = ClusterAlgebra(['A', 4])
2117            sage: A.clear_computed_data()
2118            sage: A.reset_exploring_iterator(mutating_F=False)
2119            sage: A.explore_to_depth(infinity)
2120            sage: len(A.g_vectors_so_far())
2121            14
2122            sage: len(A.F_polynomials_so_far())
2123            4
2124        """
2125        self._sd_iter = self.seeds(mutating_F=mutating_F, catch_KeyboardInterrupt=True)
2126        self._explored_depth = 0
2127
2128    def explore_to_depth(self, depth):
2129        r"""
2130        Explore the exchange graph of self up to distance depth
2131        from the initial seed.
2132
2133        INPUT:
2134
2135        - depth -- a positive integer or infinity; the maximum depth
2136          at which to stop searching
2137
2138        EXAMPLES::
2139
2140            sage: A = ClusterAlgebra(['A', 4])
2141            sage: A.explore_to_depth(infinity)
2142            sage: len(A.g_vectors_so_far())
2143            14
2144        """
2145        while self._explored_depth <= depth:
2146            try:
2147                seed = next(self._sd_iter)
2148                if isinstance(seed, ClusterAlgebraSeed):
2149                    self._explored_depth = seed.depth()
2150                else:
2151                    # We got an exception because self._sd_iter caught a KeyboardInterrupt, let's raise it again
2152                    raise seed
2153            except StopIteration:
2154                break
2155
2156    def cluster_fan(self, depth=infinity):
2157        r"""
2158        Return the cluster fan (the fan of g-vectors) of self.
2159
2160        INPUT:
2161
2162        - depth -- a positive integer or infinity (default infinity);
2163          the maximum depth at which to compute
2164
2165        EXAMPLES::
2166
2167            sage: A = ClusterAlgebra(['A', 2])
2168            sage: A.cluster_fan()
2169            Rational polyhedral fan in 2-d lattice N
2170        """
2171        seeds = self.seeds(depth=depth, mutating_F=False)
2172        cones = [Cone(S.g_vectors()) for S in seeds]
2173        return Fan(cones)
2174
2175    def mutate_initial(self, direction):
2176        r"""
2177        Return the cluster algebra obtained by mutating self at
2178        the initial seed.
2179
2180        INPUT:
2181
2182        - direction -- in which direction(s) to mutate, it can be:
2183
2184          * an integer in range(self.rank()) to mutate in one direction only
2185          * an iterable of such integers to mutate along a sequence
2186          * a string "sinks" or "sources" to mutate at all sinks or sources simultaneously
2187
2188        ALGORITHM:
2189
2190        This function computes data for the new algebra from known data for
2191        the old algebra using Equation (4.2) from [NZ2012]_ for g-vectors, and
2192        Equation (6.21) from [FZ2007]_ for F-polynomials. The exponent h
2193        in the formula for F-polynomials is -min(0, old_g_vect[k])
2194        due to [NZ2012]_ Proposition 4.2.
2195
2196        EXAMPLES::
2197
2198            sage: A = ClusterAlgebra(['F', 4])
2199            sage: A.explore_to_depth(infinity)
2200            sage: B = A.b_matrix()
2201            sage: B.mutate(0)
2202            sage: A1 = ClusterAlgebra(B)
2203            sage: A1.explore_to_depth(infinity)
2204            sage: A2 = A1.mutate_initial(0)
2205            sage: A2._F_poly_dict == A._F_poly_dict
2206            True
2207
2208        Check that we did not mess up the original algebra because of :class:UniqueRepresentation::
2209
2210            sage: A = ClusterAlgebra(['A',2])
2211            sage: A.mutate_initial(0) is A
2212            False
2213        """
2214        n = self.rank()
2215
2216        # construct mutation sequence
2217        # if you change this be considerate and change also :class:ClusterAlgebraSeed.mutate
2218        if direction == "sinks":
2219            B = self.b_matrix()
2220            seq = [i for i in range(n) if all(x <= 0 for x in B.column(i))]
2221        elif direction == "sources":
2222            B = self.b_matrix()
2223            seq = [i for i in range(n) if all(x >= 0 for x in B.column(i))]
2224        else:
2225            try:
2226                seq = iter(direction)
2227            except TypeError:
2228                seq = iter((direction, ))
2229
2230        # setup
2231        Ugen = self._U.gens()
2232        F_poly_dict = copy(self._F_poly_dict)
2233        path_dict = copy(self._path_dict)
2234        path_to_current = copy(self.current_seed().path_from_initial_seed())
2235        B0 = copy(self._B0)
2236
2237        # go
2238        for k in seq:
2239            if k not in range(n):
2240                raise ValueError('cannot mutate in direction ' + str(k))
2241
2242            # clear storage
2243            tmp_path_dict = {}
2244            tmp_F_poly_dict = {}
2245
2246            # mutate B-matrix
2247            B0.mutate(k)
2248
2249            # here we have \mp B0 rather then \pm B0 because we want the k-th row of the old B0
2250            F_subs = [Ugen[k] ** (-1) if j == k else Ugen[j] * Ugen[k] ** max(B0[k, j], 0) * (1 + Ugen[k]) ** (-B0[k, j]) for j in range(n)]
2251
2252            for old_g_vect in path_dict:
2253                # compute new g-vector
2254                J = identity_matrix(n)
2255                eps = sign(old_g_vect[k])
2256                for j in range(n):
2257                    # here we have -eps*B0 rather than eps*B0 because we want the k-th column of the old B0
2258                    J[j, k] += max(0, -eps * B0[j, k])
2259                J[k, k] = -1
2260                new_g_vect = tuple(J * vector(old_g_vect))
2261
2262                # compute new path
2263                new_path = path_dict[old_g_vect]
2264                new_path = ([k] + new_path[:1] if new_path[:1] != [k] else []) + new_path[1:]
2265                tmp_path_dict[new_g_vect] = new_path
2266
2267                # compute new F-polynomial
2268                if old_g_vect in F_poly_dict:
2269                    h = -min(0, old_g_vect[k])
2270                    new_F_poly = F_poly_dict[old_g_vect](F_subs) * Ugen[k] ** h * (Ugen[k] + 1) ** old_g_vect[k]
2271                    tmp_F_poly_dict[new_g_vect] = new_F_poly
2272
2273            # update storage
2274            path_dict = tmp_path_dict
2275            F_poly_dict = tmp_F_poly_dict
2276            path_to_current = ([k] + path_to_current[:1] if path_to_current[:1] != [k] else []) + path_to_current[1:]
2277
2278        # create new algebra
2279        cv_names = self.initial_cluster_variable_names()
2280        coeff_names = self.coefficient_names()
2281        scalars = self.scalars()
2282        A = ClusterAlgebra(B0, cluster_variable_names=cv_names,
2283                           coefficient_names=coeff_names, scalars=scalars)
2284
2285        # store computed data
2286        A._F_poly_dict.update(F_poly_dict)
2287        A._path_dict.update(path_dict)
2288
2289        # reset self.current_seed() to the previous location
2290        S = A.initial_seed()
2291        S.mutate(path_to_current, mutating_F=False)
2292        A.set_current_seed(S)
2293
2294        return A
2295
2296    def greedy_element(self, d_vector):
2297        r"""
2298        Return the greedy element with denominator vector d_vector.
2299
2300        INPUT:
2301
2302        - d_vector -- tuple of 2 integers; the denominator vector of
2303          the element to compute
2304
2305        ALGORITHM:
2306
2307        This implements greedy elements of a rank 2 cluster algebra using
2308        Equation (1.5) from [LLZ2014]_.
2309
2310        EXAMPLES::
2311
2312            sage: A = ClusterAlgebra(['A', [1, 1], 1])
2313            sage: A.greedy_element((1, 1))
2314            (x0^2 + x1^2 + 1)/(x0*x1)
2315        """
2316        if self.rank() != 2:
2317            raise ValueError('greedy elements are only defined in rank 2')
2318
2319        if len(self.coefficients()) != 0:
2320            raise NotImplementedError('can only compute greedy elements in the coefficient-free case')
2321
2322        b = abs(self.b_matrix()[0, 1])
2323        c = abs(self.b_matrix()[1, 0])
2324        a1, a2 = d_vector
2325        # Here we use the generators of self.ambient() because cluster variables
2326        #   do not have an inverse.
2327        x1, x2 = self.ambient().gens()
2328        if a1 < 0:
2329            if a2 < 0:
2330                return self.retract(x1 ** (-a1) * x2 ** (-a2))
2331            else:
2332                return self.retract(x1 ** (-a1) * ((1 + x2 ** c) / x1) ** a2)
2333        elif a2 < 0:
2334            return self.retract(((1 + x1 ** b) / x2) ** a1 * x2 ** (-a2))
2335        output = 0
2336        for p in range(0, a2 + 1):
2337            for q in range(0, a1 + 1):
2338                output += self._greedy_coefficient(d_vector, p, q) * x1 ** (b * p) * x2 ** (c * q)
2339        return self.retract(x1 ** (-a1) * x2 ** (-a2) * output)
2340
2341    def _greedy_coefficient(self, d_vector, p, q):
2342        r"""
2343        Return the coefficient of the monomial x1 ** (b * p) * x2 ** (c * q)
2344        in the numerator of the greedy element with denominator vector d_vector.
2345
2346        EXAMPLES::
2347
2348            sage: A = ClusterAlgebra(['A', [1, 1], 1])
2349            sage: A.greedy_element((1, 1))
2350            (x0^2 + x1^2 + 1)/(x0*x1)
2351            sage: A._greedy_coefficient((1, 1), 0, 0)
2352            1
2353            sage: A._greedy_coefficient((1, 1), 1, 0)
2354            1
2355        """
2356        b = abs(self.b_matrix()[0, 1])
2357        c = abs(self.b_matrix()[1, 0])
2358        a1, a2 = d_vector
2359        p = Integer(p)
2360        q = Integer(q)
2361        if p == 0 and q == 0:
2362            return Integer(1)
2363        sum1 = 0
2364        for k in range(1, p + 1):
2365            bino = 0
2366            if a2 - c * q + k - 1 >= k:
2367                bino = binomial(a2 - c * q + k - 1, k)
2368            sum1 += (-1) ** (k - 1) * self._greedy_coefficient(d_vector, p - k, q) * bino
2369        sum2 = 0
2370        for l in range(1, q + 1):
2371            bino = 0
2372            if a1 - b * p + l - 1 >= l:
2373                bino = binomial(a1 - b * p + l - 1, l)
2374            sum2 += (-1) ** (l - 1) * self._greedy_coefficient(d_vector, p, q - l) * bino
2375        return Integer(max(sum1, sum2))
2376
2377    # DESIDERATA
2378    # Some of these are probably unrealistic
2379    def upper_cluster_algebra(self):
2380        r"""
2381        Return the upper cluster algebra associated to self.
2382
2383        EXAMPLES::
2384
2385            sage: A = ClusterAlgebra(['F', 4])
2386            sage: A.upper_cluster_algebra()
2387            Traceback (most recent call last):
2388            ...
2389            NotImplementedError: not implemented yet
2390        """
2391        raise NotImplementedError("not implemented yet")
2392
2393    def upper_bound(self):
2394        r"""
2395        Return the upper bound associated to self.
2396
2397        EXAMPLES::
2398
2399            sage: A = ClusterAlgebra(['F', 4])
2400            sage: A.upper_bound()
2401            Traceback (most recent call last):
2402            ...
2403            NotImplementedError: not implemented yet
2404        """
2405        raise NotImplementedError("not implemented yet")
2406
2407    def lower_bound(self):
2408        r"""
2409        Return the lower bound associated to self.
2410
2411        EXAMPLES::
2412
2413            sage: A = ClusterAlgebra(['F', 4])
2414            sage: A.lower_bound()
2415            Traceback (most recent call last):
2416            ...
2417            NotImplementedError: not implemented yet
2418        """
2419        raise NotImplementedError("not implemented yet")
2420
2421    def theta_basis_element(self, g_vector):
2422        r"""
2423        Return the element of the theta basis with g-vector g_vector.
2424
2425        EXAMPLES::
2426
2427            sage: A = ClusterAlgebra(['F', 4])
2428            sage: A.theta_basis_element((1, 0, 0, 0))
2429            Traceback (most recent call last):
2430            ...
2431            NotImplementedError: not implemented yet
2432        """
2433        raise NotImplementedError("not implemented yet")