Coverage for local/lib/python2.7/site-packages/sage/combinat/fully_packed_loop.py : 96%

r""" 

Fully packed loops 

AUTHORS: 

- Vincent Knight, James Campbell, Kevin Dilks, Emily Gunawan (2015): Initial version 

- Vincent Delecroix (2017): cleaning and enhanced plotting function 

""" 

#***************************************************************************** 

# Copyright (C) 2015 Vincent Knight <vincent.knight@gmail.com> 

# James Campbell <james.campbell@tanti.org.uk> 

# Kevin Dilks <kdilks@gmail.com> 

# Emily Gunawan <egunawan@umn.edu> 

# 2017 Vincent Delecroix <20100.delecroix@gmail.com> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# 

# This code is distributed in the hope that it will be useful, but 

# WITHOUT ANY WARRANTY; without even the implied warranty of 

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 

# General Public License for more details. 

# 

# The full text of the GPL is available at: 

# 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

# python3 

from __future__ import division, print_function 

from six import add_metaclass 

from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass 

from sage.structure.unique_representation import UniqueRepresentation 

from sage.structure.parent import Parent 

from sage.structure.element import parent, Element 

from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets 

from sage.combinat.six_vertex_model import (SquareIceModel, 

SixVertexConfiguration, 

SixVertexModel) 

from sage.combinat.alternating_sign_matrix import AlternatingSignMatrix 

from sage.misc.decorators import options 

from sage.matrix.constructor import matrix 

from sage.arith.all import factorial 

from sage.rings.integer import Integer 

from sage.misc.all import prod 

# edges of a fpl in terms of the six vertex possible configurations 

R = (1, 0) 

L = (-1, 0) 

U = (0, 1) 

D = (0, -1) 

FPL_edges = ( 

# 0 UD 1 RD, 2 UR, 3 LR, 4 LD 5 LU 

((D,U), (L,D), (D,R), (R,L), (L,U), (R,U)), # even 

((R,L), (R,U), (L,U), (D,U), (D,R), (L,D)) # odd 

) 

FPL_turns = ( 

# 0 UD 1 RD 2 UR 3 LR 4 LD 5 LU 

({U: U, D: D}, {R: D, U: L}, {U: R, L: D}, {L: L, R: R}, {R: U, D: L}, {L: U, D: R}), # even 

({L: L, R: R}, {L: U, D: R}, {R: U, D: L}, {U: U, D: D}, {U: R, L: D}, {R: D, U: L}) # odd 

) 

def _make_color_list(n, colors=None, color_map=None, randomize=False): 

r""" 

TESTS:: 

sage: from sage.combinat.fully_packed_loop import _make_color_list 

sage: _make_color_list(5) 

sage: _make_color_list(5, ['blue', 'red']) 

['blue', 'red', 'blue', 'red', 'blue'] 

sage: _make_color_list(5, color_map='summer') 

[(0.0, 0.5, 0.40000000000000002), 

(0.25098039215686274, 0.62549019607843137, 0.40000000000000002), 

(0.50196078431372548, 0.75098039215686274, 0.40000000000000002), 

(0.75294117647058822, 0.87647058823529411, 0.40000000000000002), 

(1.0, 1.0, 0.40000000000000002)] 

sage: _make_color_list(8, ['blue', 'red'], randomize=True) 

['blue', 'blue', 'red', 'blue', 'red', 'red', 'red', 'blue'] 

""" 

if colors: 

dim = len(colors) 

colors = [colors[i % dim] for i in range(n)] 

elif color_map: 

from matplotlib import cm 

if not color_map in cm.datad: 

raise ValueError('unknown color map %s' % color_map) 

cmap = cm.__dict__[color_map] 

colors = [cmap(i/float(n-1))[:3] for i in range(n)] 

if colors and randomize: 

from sage.misc.prandom import shuffle 

shuffle(colors) 

return colors 

@add_metaclass(InheritComparisonClasscallMetaclass) 

class FullyPackedLoop(Element): 

r""" 

A class for fully packed loops. 

A fully packed loop is a collection of non-intersecting lattice paths on a square 

grid such that every vertex is part of some path, and the paths are either closed 

internal loops or have endpoints corresponding to alternate points on the 

boundary [Propp2001]_. They are known to be in bijection with alternating sign 

matrices. 

.. SEEALSO:: 

:class:`AlternatingSignMatrix` 

To each fully packed loop, we assign a link pattern, which is the non-crossing 

matching attained by seeing which points on the boundary are connected 

by open paths in the fully packed loop. 

We can create a fully packed loop using the corresponding alternating sign 

matrix and also extract the link pattern:: 

sage: A = AlternatingSignMatrix([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) 

sage: fpl = FullyPackedLoop(A) 

sage: fpl.link_pattern() 

[(1, 4), (2, 3), (5, 6)] 

sage: fpl 

| | 

| | 

+ -- + + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ + -- + 

| | 

| | 

sage: B = AlternatingSignMatrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]]) 

sage: fplb = FullyPackedLoop(B) 

sage: fplb.link_pattern() 

[(1, 6), (2, 5), (3, 4)] 

sage: fplb 

| | 

| | 

+ + -- + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ -- + + 

| | 

| | 

The class also has a plot method:: 

sage: fpl.plot() 

Graphics object consisting of 3 graphics primitives 

which gives: 

.. PLOT:: 

:width: 200 px 

A = AlternatingSignMatrix([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) 

fpl = FullyPackedLoop(A) 

p = fpl.plot() 

sphinx_plot(p) 

Note that we can also create a fully packed loop from a six vertex model configuration:: 

sage: S = SixVertexModel(3, boundary_conditions='ice').from_alternating_sign_matrix(A) 

sage: S 

^ ^ ^ 

| | | 

--> # -> # -> # <-- 

^ ^ | 

| | V 

--> # -> # <- # <-- 

^ | | 

| V V 

--> # <- # <- # <-- 

| | | 

V V V 

sage: fpl = FullyPackedLoop(S) 

sage: fpl 

| | 

| | 

+ -- + + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ + -- + 

| | 

| | 

Once we have a fully packed loop we can obtain the corresponding alternating sign matrix:: 

sage: fpl.to_alternating_sign_matrix() 

[0 0 1] 

[0 1 0] 

[1 0 0] 

Here are some more examples using bigger ASMs:: 

sage: A = AlternatingSignMatrix([[0,1,0,0],[0,0,1,0],[1,-1,0,1],[0,1,0,0]]) 

sage: S = SixVertexModel(4, boundary_conditions='ice').from_alternating_sign_matrix(A) 

sage: fpl = FullyPackedLoop(S) 

sage: fpl.link_pattern() 

[(1, 2), (3, 6), (4, 5), (7, 8)] 

sage: fpl 

| | 

| | 

+ -- + -- + + -- 

| 

| 

-- + + -- + -- + 

| | 

| | 

+ + + -- + -- 

| | | 

| | | 

-- + + + -- + 

| | 

| | 

sage: m = AlternatingSignMatrix([[0,0,1,0,0,0], 

....: [1,0,-1,0,1,0], 

....: [0,0,0,1,0,0], 

....: [0,1,0,0,-1,1], 

....: [0,0,0,0,1,0], 

....: [0,0,1,0,0,0]]) 

sage: fpl = FullyPackedLoop(m) 

sage: fpl.link_pattern() 

[(1, 12), (2, 7), (3, 4), (5, 6), (8, 9), (10, 11)] 

sage: fpl 

| | | 

| | | 

+ -- + + + -- + + -- 

| | | | 

| | | | 

-- + -- + + + -- + -- + 

| 

| 

+ -- + + -- + -- + + -- 

| | | | 

| | | | 

-- + + + -- + + + 

| | | | | 

| | | | | 

+ -- + + -- + + + -- 

| | 

| | 

-- + + -- + -- + + -- + 

| | | 

| | | 

sage: m = AlternatingSignMatrix([[0,1,0,0,0,0,0], 

....: [1,-1,0,0,1,0,0], 

....: [0,0,0,1,0,0,0], 

....: [0,1,0,0,-1,1,0], 

....: [0,0,0,0,1,0,0], 

....: [0,0,1,0,-1,0,1], 

....: [0,0,0,0,1,0,0]]) 

sage: fpl = FullyPackedLoop(m) 

sage: fpl.link_pattern() 

[(1, 2), (3, 4), (5, 6), (7, 8), (9, 14), (10, 11), (12, 13)] 

sage: fpl 

| | | | 

| | | | 

+ -- + -- + + -- + + -- + 

| | 

| | 

-- + -- + -- + + -- + -- + + -- 

| | 

| | 

+ -- + + -- + -- + + -- + 

| | | | 

| | | | 

-- + + + -- + + + + -- 

| | | | | | 

| | | | | | 

+ -- + + -- + + + -- + 

| | 

| | 

-- + + -- + -- + + + -- + -- 

| | | | 

| | | | 

+ -- + + -- + + + -- + 

| | | | 

| | | | 

Gyration on an alternating sign matrix/fully packed loop ``fpl`` 

of the link pattern corresponding to ``fpl``:: 

sage: ASMs = AlternatingSignMatrices(3).list() 

sage: ncp = FullyPackedLoop(ASMs[1]).link_pattern() # fpl's gyration orbit size is 2 

sage: rotated_ncp=[] 

sage: for (a,b) in ncp: 

....: for i in range(0,5): 

....: a,b=a%6+1,b%6+1; 

....: rotated_ncp.append((a,b)) 

sage: PerfectMatching(ASMs[1].gyration().to_fully_packed_loop().link_pattern()) ==\ 

PerfectMatching(rotated_ncp) 

True 

sage: fpl = FullyPackedLoop(ASMs[0]) 

sage: ncp = fpl.link_pattern() # fpl's gyration size is 3 

sage: rotated_ncp=[] 

sage: for (a,b) in ncp: 

....: for i in range(0,5): 

....: a,b=a%6+1,b%6+1; 

....: rotated_ncp.append((a,b)) 

sage: PerfectMatching(ASMs[0].gyration().to_fully_packed_loop().link_pattern()) ==\ 

PerfectMatching(rotated_ncp) 

True 

sage: mat = AlternatingSignMatrix([[0,0,1,0,0,0,0],[1,0,-1,0,1,0,0],\ 

[0,0,1,0,0,0,0],[0,1,-1,0,0,1,0],[0,0,1,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,1]]) 

sage: fpl = FullyPackedLoop(mat) # n=7 

sage: ncp = fpl.link_pattern() 

sage: rotated_ncp=[] 

sage: for (a,b) in ncp: 

....: for i in range(0,13): 

....: a,b=a%14+1,b%14+1; 

....: rotated_ncp.append((a,b)) 

sage: PerfectMatching(mat.gyration().to_fully_packed_loop().link_pattern()) ==\ 

PerfectMatching(rotated_ncp) 

True 

sage: mat = AlternatingSignMatrix([[0,0,0,1,0,0], [0,0,1,-1,1,0],\ 

[0,1,0,0,-1,1], [1,0,-1,1,0,0], [0,0,1,0,0,0], [0,0,0,0,1,0]]) 

sage: fpl = FullyPackedLoop(mat) # n =6 

sage: ncp = fpl.link_pattern() 

sage: rotated_ncp=[] 

sage: for (a,b) in ncp: 

....: for i in range(0,11): 

....: a,b=a%12+1,b%12+1; 

....: rotated_ncp.append((a,b)) 

sage: PerfectMatching(mat.gyration().to_fully_packed_loop().link_pattern()) ==\ 

PerfectMatching(rotated_ncp) 

True 

More examples:: 

We can initiate a fully packed loop using an alternating sign matrix:: 

sage: A = AlternatingSignMatrix([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) 

sage: fpl = FullyPackedLoop(A) 

sage: fpl 

| | 

| | 

+ -- + + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ + -- + 

| | 

| | 

sage: FullyPackedLoops(3)(A) == fpl 

True 

We can also input a matrix:: 

sage: FullyPackedLoop([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) 

| | 

| | 

+ -- + + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ + -- + 

| | 

| | 

sage: FullyPackedLoop([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) ==\ 

....: FullyPackedLoops(3)([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) 

True 

Otherwise we initiate a fully packed loop using a six vertex model:: 

sage: S = SixVertexModel(3, boundary_conditions='ice').from_alternating_sign_matrix(A) 

sage: fpl = FullyPackedLoop(S) 

sage: fpl 

| | 

| | 

+ -- + + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ + -- + 

| | 

| | 

sage: FullyPackedLoops(3)(S) == FullyPackedLoop(S) 

True 

sage: fpl.six_vertex_model().to_alternating_sign_matrix() 

[0 0 1] 

[0 1 0] 

[1 0 0] 

We can also input the matrix associated to a six vertex model:: 

sage: SixVertexModel(2)([[3,1],[5,3]]) 

^ ^ 

| | 

--> # <- # <-- 

| ^ 

V | 

--> # -> # <-- 

| | 

V V 

sage: FullyPackedLoop([[3,1],[5,3]]) 

| 

| 

+ + -- 

| | 

| | 

-- + + 

| 

| 

sage: FullyPackedLoops(2)([[3,1],[5,3]]) == FullyPackedLoop([[3,1],[5,3]]) 

True 

Note that the matrix corresponding to a six vertex model without 

the ice boundary condition is not allowed:: 

sage: SixVertexModel(2)([[3,1],[5,5]]) 

^ ^ 

| | 

--> # <- # <-- 

| ^ 

V V 

--> # -> # --> 

| | 

V V 

sage: FullyPackedLoop([[3,1],[5,5]]) 

Traceback (most recent call last): 

... 

ValueError: invalid alternating sign matrix 

sage: FullyPackedLoops(2)([[3,1],[5,5]]) 

Traceback (most recent call last): 

... 

ValueError: invalid alternating sign matrix 

Note that if anything else is used to generate the fully packed loop an error will occur:: 

sage: fpl = FullyPackedLoop(5) 

Traceback (most recent call last): 

... 

ValueError: invalid alternating sign matrix 

sage: fpl = FullyPackedLoop((1, 2, 3)) 

Traceback (most recent call last): 

... 

ValueError: The alternating sign matrices must be square 

sage: SVM = SixVertexModel(3)[0] 

sage: FullyPackedLoop(SVM) 

Traceback (most recent call last): 

... 

ValueError: invalid alternating sign matrix 

REFERENCES: 

.. [Propp2001] James Propp. 

*The Many Faces of Alternating Sign Matrices*, 

Discrete Mathematics and Theoretical Computer Science 43 (2001): 58 

:arxiv:`math/0208125` 

.. [Striker2015] Jessica Striker. 

*The toggle group, homomesy, and the Razumov-Stroganov correspondence*, 

Electron. J. Combin. 22 (2015) no. 2 

:arxiv:`1503.08898` 

""" 

@staticmethod 

def __classcall_private__(cls, generator): 

""" 

Create a FPL. 

EXAMPLES:: 

sage: A = AlternatingSignMatrix([[1, 0, 0],[0, 1, 0],[0, 0, 1]]) 

sage: FullyPackedLoop(A) 

| | 

| | 

+ + -- + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ -- + + 

| | 

| | 

sage: SVM = SixVertexModel(4, boundary_conditions='ice')[0] 

sage: FullyPackedLoop(SVM) 

| | 

| | 

+ + -- + + -- 

| | | 

| | | 

-- + + + -- + 

| | 

| | 

+ -- + + + -- 

| | | 

| | | 

-- + + -- + + 

| | 

| | 

""" 

if isinstance(generator, AlternatingSignMatrix): 

SVM = generator.to_six_vertex_model() 

elif isinstance(generator, SquareIceModel.Element): 

SVM = generator 

elif isinstance(generator, SixVertexConfiguration): 

# Check that this is an ice square model 

generator = SixVertexModel(generator.parent()._nrows, \ 

boundary_conditions='ice')(generator) 

M = generator.to_alternating_sign_matrix().to_matrix() 

M = AlternatingSignMatrix(M) 

SVM = generator 

else: # Not ASM nor SVM 

try: 

SVM = AlternatingSignMatrix(generator).to_six_vertex_model() 

except (TypeError, ValueError): 

generator = matrix(generator) 

generator = SixVertexModel(generator.nrows(), boundary_conditions='ice')(generator) 

# Check that this is an ice square model 

M = generator.to_alternating_sign_matrix() 

SVM = generator 

if not SVM: 

raise TypeError('generator for FullyPackedLoop must either be an \ 

AlternatingSignMatrix or a SquareIceModel.Element') 

FPLs = FullyPackedLoops(len(SVM)) 

return FPLs(generator) 

def __init__(self, parent, generator): 

""" 

Initialise object, can take ASM of FPL as generator. 

TESTS:: 

sage: A = AlternatingSignMatrix([[0, 0, 1], [0, 1, 0], [1, 0, 0]]) 

sage: fpl = FullyPackedLoop(A) 

sage: TestSuite(fpl).run() 

""" 

if isinstance(generator, AlternatingSignMatrix): 

self._six_vertex_model = generator.to_six_vertex_model() 

elif isinstance(generator, SquareIceModel.Element): 

self._six_vertex_model = generator 

Element.__init__(self, parent) 

def _repr_(self): 

""" 

Return a string representation of ``self``. 

EXAMPLES:: 

sage: A = AlternatingSignMatrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]]) 

sage: fpl = FullyPackedLoop(A) 

sage: fpl 

| | 

| | 

+ + -- + 

| | 

| | 

-- + + + -- 

| | 

| | 

+ -- + + 

| | 

| | 

sage: A = AlternatingSignMatrix([[0,1,0,0],[0,0,1,0],[1,-1,0,1],[0,1,0,0]]) 

sage: S = SixVertexModel(4, boundary_conditions='ice').from_alternating_sign_matrix(A) 

sage: fpl = FullyPackedLoop(S) 

sage: fpl 

| | 

| | 

+ -- + -- + + -- 

| 

| 

-- + + -- + -- + 

| | 

| | 

+ + + -- + -- 

| | | 

| | | 

-- + + + -- + 

| | 

| | 

""" 

# List are in the order of URDL 

# One set of rules for how to draw around even vertex, one set of rules for odd vertex 

n = len(self._six_vertex_model) - 1 

ascii1 = [[r' ', ' -', r' ', '- '], # LR 

[r' | ', ' ', r' ', '- '], # LU 

[r' ', ' ', r' | ', '- '], # LD 

[r' | ', ' ', r' | ', ' '], # UD 

[r' | ', ' -', r' ', ' '], # UR 

[r' ', ' -', r' | ', ' ']] # RD 

ascii2 = [[r' | ', ' ', r' | ', ' '], # LR 

[r' ', ' -', r' | ', ' '], # LU 

[r' | ', ' -', r' ', ' '], # LD 

[r' ', ' -', r' ', '- '], # UD 

[r' ', ' ', r' | ', '- '], # UR 

[r' | ', ' ', r' ', '- ']] # RD 

ret = ' ' 

# Do the top line 

for i,entry in enumerate(self._six_vertex_model[0]): 

if i % 2 == 0: 

ret += ' | ' 

else: 

ret += ' ' 

plus_sign = '+' 

# Do the meat of the ascii art 

for j,row in enumerate(self._six_vertex_model): 

ret += '\n ' 

# Do the top row 

for i,entry in enumerate(row): 

if (i+j) % 2 == 0: 

ret += ascii1[entry][0] 

else: 

ret += ascii2[entry][0] 

ret += '\n' 

# Do the left-most entry 

if (j) % 2 == 0: 

ret += ' ' 

else: 

ret += ' -' 

# Do the middle row 

for i,entry in enumerate(row): 

if (i+j) % 2 == 0: 

ret += ascii1[entry][3] + plus_sign + ascii1[entry][1] 

else: 

ret += ascii2[entry][3] + plus_sign + ascii2[entry][1] 

# Do the right-most entry 

if (j+n) % 2 ==0: 

ret += ' ' 

else: 

ret += '- ' 

# Do the bottom row 

ret += '\n ' 

for i,entry in enumerate(row): 

if (i+j) % 2 ==0: 

ret += ascii1[entry][2] 

else: 

ret += ascii2[entry][2] 

# Do the bottom line 

ret += '\n ' 

for i,entry in enumerate(self._six_vertex_model[-1]): 

if (i+n+1) % 2 ==0: 

ret += ' ' 

else: 

ret += ' | ' 

return ret 

def _richcmp_(self, other, op): 

""" 

Check equality or inequality. 

EXAMPLES:: 

sage: A = AlternatingSignMatrices(3) 

sage: M = A.random_element() 

sage: FullyPackedLoop(M) == M.to_fully_packed_loop() 

True 

sage: FullyPackedLoop(A([[1, 0, 0],[0, 1, 0],[0, 0, 1]])) ==\ 

FullyPackedLoop(A([[1, 0, 0],[0, 0, 1],[0, 1, 0]])) 

False 

sage: FullyPackedLoop(M) == M 

False 

sage: M = A.random_element() 

sage: FullyPackedLoop(M) != M.to_fully_packed_loop() 

False 

sage: f0 = FullyPackedLoop(A([[1, 0, 0],[0, 1, 0],[0, 0, 1]])) 

sage: f1 = FullyPackedLoop(A([[1, 0, 0],[0, 0, 1],[0, 1, 0]])) 

sage: f0 != f1 

True 

""" 

return self._six_vertex_model._richcmp_(other._six_vertex_model, op) 

def to_alternating_sign_matrix(self): 

""" 

Return the alternating sign matrix corresponding to this class. 

.. SEEALSO:: 

:class:`AlternatingSignMatrix` 

EXAMPLES:: 

sage: A = AlternatingSignMatrix([[0, 1, 0], [1, -1, 1], [0, 1, 0]]) 

sage: S = SixVertexModel(3, boundary_conditions='ice').from_alternating_sign_matrix(A) 

sage: fpl = FullyPackedLoop(S) 

sage: fpl.to_alternating_sign_matrix() 

[ 0 1 0] 

[ 1 -1 1] 

[ 0 1 0] 

sage: A = AlternatingSignMatrix([[0,1,0,0],[0,0,1,0],[1,-1,0,1],[0,1,0,0]]) 

sage: S = SixVertexModel(4, boundary_conditions='ice').from_alternating_sign_matrix(A) 

sage: fpl = FullyPackedLoop(S) 

sage: fpl.to_alternating_sign_matrix() 

[ 0 1 0 0] 

[ 0 0 1 0] 

[ 1 -1 0 1] 

[ 0 1 0 0] 

""" 

return self._six_vertex_model.to_alternating_sign_matrix() 

@options(link=True, loop=True, loop_fill=False) 

def plot(self, **options): 

r""" 

Return a graphical object of the Fully Packed Loop. 

Each option can be specified separately for links (the curves that join 

boundary points) and the loops. In order to do so, you need to prefix 

its name with either ``'link_'`` or ``'loop_'``. As an example, setting 

``color='red'`` will color both links and loops in red while setting 

``link_color='red'`` will only apply the color option for the links. 

INPUT: 

- ``link``, ``loop`` - (boolean, default ``True``) whether to plot the links 

or the loops 

- ``color``, ``link_color``, ``loop_color`` - (optional, a string or a 

RGB triple) 

- ``colors``, ``link_colors``, ``loop_colors`` - (optional, list) a list of 

colors 

- ``color_map``, ``link_color_map``, ``loop_color_map`` - (string, 

optional) a name of a matplotlib color map for the link or the loop 

- ``link_color_randomize`` - (boolean, default ``False``) when 

``link_colors`` or ``link_color_map`` is specified it randomizes 

its order. Setting this option to ``True`` makes it unlikely to 

have two neighboring links with the same color. 

- ``loop_fill`` - (boolean, optional) whether to fill the interior of the loops 

EXAMPLES: 

To plot the fully packed loop associated to the following alternating sign 

matrix 

.. MATH:: 

\begin{pmatrix} 0&1&1 \\ 1&-1&1 \\ 0&1&0 \end{pmatrix} 

simply do:: 

sage: A = AlternatingSignMatrix([[0, 1, 0], [1, -1, 1], [0, 1, 0]]) 

sage: fpl = FullyPackedLoop(A) 

sage: fpl.plot() 

Graphics object consisting of 3 graphics primitives 

The resulting graphics is as follows 

.. PLOT:: 

:width: 200 px 

A = AlternatingSignMatrix([[0, 1, 0], [1, -1, 1], [0, 1, 0]]) 

fpl = FullyPackedLoop(A) 

p = fpl.plot() 

sphinx_plot(p) 

You can also have the three links in different colors with:: 

sage: A = AlternatingSignMatrix([[0, 1, 0], [1, -1, 1], [0, 1, 0]]) 

sage: fpl = FullyPackedLoop(A) 

sage: fpl.plot(link_color_map='rainbow') 

Graphics object consisting of 3 graphics primitives 

.. PLOT:: 

:width: 200 px 

A = AlternatingSignMatrix([[0, 1, 0], [1, -1, 1], [0, 1, 0]]) 

fpl = FullyPackedLoop(A) 

p = fpl.plot(link_color_map='rainbow') 

sphinx_plot(p) 

You can plot the 42 fully packed loops of size `4 \times 4` using:: 

sage: G = [fpl.plot(link_color_map='winter', loop_color='black') for fpl in FullyPackedLoops(4)] 

sage: graphics_array(G, 7, 6) 

Graphics Array of size 7 x 6 

.. PLOT:: 

:width: 600 px 

G = [fpl.plot(link_color_map='winter', loop_color='black') for fpl in FullyPackedLoops(4)] 

p = graphics_array(G, 7, 6) 

sphinx_plot(p) 

Here is an example of a `20 \times 20` fully packed loop:: 

sage: s = "00000000000+0000000000000000+00-0+00000000000+00-00+0-+00000\ 

....: 0000+-00+00-+00000000+00-0000+0000-+00000000+000-0+0-+0-+000\ 

....: 000+-000+-00+0000000+-+-000+00-+0-000+000+-000+-0+0000000-0+\ 

....: 0000+0-+0-+00000-+00000+-+0-0+-00+0000000000+-0000+0-00+0000\ 

....: 000000+0-000+000000000000000+0000-00+00000000+0000-000+00000\ 

....: 00+0-00+0000000000000000+-0000+000000-+000000+00-0000+-00+00\ 

....: 00000000+-0000+00000000000000+0000000000" 

sage: a = matrix(20, [{'0':0, '+':1, '-': -1}[i] for i in s]) 

sage: fpl = FullyPackedLoop(a) 

sage: fpl.plot(loop_fill=True, loop_color_map='rainbow') 

Graphics object consisting of 27 graphics primitives 

.. PLOT:: 

:width: 400 px 

s = "00000000000+0000000000000000+00-0+00000000000+00-00+0-+00000\ 

0000+-00+00-+00000000+00-0000+0000-+00000000+000-0+0-+0-+000\ 

000+-000+-00+0000000+-+-000+00-+0-000+000+-000+-0+0000000-0+\ 

0000+0-+0-+00000-+00000+-+0-0+-00+0000000000+-0000+0-00+0000\ 

000000+0-000+000000000000000+0000-00+00000000+0000-000+00000\ 

00+0-00+0000000000000000+-0000+000000-+000000+00-0000+-00+00\ 

00000000+-0000+00000000000000+0000000000" 

a = matrix(20, [{'0':0, '+':1, '-': -1}[i] for i in s]) 

p = FullyPackedLoop(a).plot(loop_fill=True, loop_color_map='rainbow') 

sphinx_plot(p) 

""" 

from sage.plot.graphics import Graphics 

from sage.plot.line import line2d 

from sage.plot.polygon import polygon2d 

link_options = {} 

loop_options = {} 

extra_options = {} 

for k,v in options.items(): 

if k == 'link': 

link = v 

elif k == 'loop': 

loop = v 

elif k.startswith('link_'): 

link_options[k[5:]] = v 

elif k.startswith('loop_'): 

loop_options[k[5:]] = v 

else: 

link_options[k] = v 

loop_options[k] = v 

sv = self._six_vertex_model 

n = len(sv) 

# LR boudaries => odd sum 

# UD boundaries => even sum 

rank = self.parent()._boundary_index 

unrank = self.parent()._boundary 

seen = [False] * (2*n) 

squares = set((i,j) for i in range(n) for j in range(n)) 

colors = _make_color_list(2*n, 

colors = link_options.pop('colors', None), 

color_map = link_options.pop('color_map', None), 

randomize = link_options.pop('color_randomize', False)) 

G = Graphics() 

for i in range(2*n): 

if seen[i]: 

continue 

orbit = self._link_or_loop_from(unrank(i)) 

j = rank(orbit[-1]) 

seen[i] = seen[j] = True 

squares.difference_update(orbit) 

if link: 

if colors: 

link_options['color'] = colors.pop() 

# make it upside down 

orbit = [(j, n - i - 1) for i, j in orbit] 

G += line2d(orbit, **link_options) 

loops = [] 

while squares: 

orbit = self._link_or_loop_from(squares.pop()) 

loops.append(orbit) 

squares.difference_update(orbit) 

if loop: 

colors = _make_color_list(len(loops), 

colors = loop_options.pop('colors', None), 

color_map = loop_options.pop('color_map', None), 

randomize = loop_options.pop('color_randomize', False)) 

fill = loop_options.pop('fill') 

for orbit in loops: 

if colors: 

loop_options['color'] = colors.pop() 

# make it upside down 

orbit = [(j, n - i - 1) for i,j in orbit] 

if fill: 

G += polygon2d(orbit, **loop_options) 

else: 

G += line2d(orbit, **loop_options) 

G.axes(False) 

G.set_aspect_ratio(1) 

return G 

def gyration(self): 

r""" 

Return the fully packed loop obtained by applying gyration 

to the alternating sign matrix in bijection with ``self``. 

Gyration was first defined in [Wieland00]_ as an action on 

fully-packed loops. 

REFERENCES: 

.. [Wieland00] \B. Wieland. *A large dihedral symmetry of the set of 

alternating sign matrices*. Electron. J. Combin. 7 (2000). 

EXAMPLES:: 

sage: A = AlternatingSignMatrix([[1, 0, 0],[0, 1, 0],[0, 0, 1]]) 

sage: fpl = FullyPackedLoop(A) 

sage: fpl.gyration().to_alternating_sign_matrix() 

[0 0 1] 

[0 1 0] 

[1 0 0] 

sage: asm = AlternatingSignMatrix([[0, 0, 1],[1, 0, 0],[0, 1, 0]]) 

sage: f = FullyPackedLoop(asm) 

sage: f.gyration().to_alternating_sign_matrix() 

[0 1 0] 

[0 0 1] 

[1 0 0] 

""" 

return FullyPackedLoop(self.to_alternating_sign_matrix().gyration()) 

def _link_or_loop_from(self, pos, d0=None): 

r""" 

Return the coordinates of the line passing through ``pos``. 

EXAMPLES: 

A link:: 

sage: fpl = FullyPackedLoops(4).first() 

sage: fpl._link_or_loop_from((2,2)) 

[(0, 4), (0, 3), (1, 3), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1)] 

sage: fpl._link_or_loop_from((-1, 0)) 

[(-1, 0), (0, 0), (1, 0), (1, -1)] 

A loop:: 

sage: a = AlternatingSignMatrix([[0,1,0,0], [0,0,0,1], [1,0,0,0], [0,0,1,0]]) 

sage: fpl = FullyPackedLoop(a) 

sage: fpl._link_or_loop_from((1,1)) 

[(1, 1), (2, 1), (2, 2), (1, 2), (1, 1)] 

""" 

global R, L, U, D, FPL_turns, FPL_edges 

orbit = [pos] 

sv = self._six_vertex_model 

n = len(sv) 

i,j = pos 

# deal with boundary cases 

if i < -1 or i > n or j < -1 or j > n: 

raise ValueError('indices out of range') 

if (i == -1 or i == n) and (i+j)%2 != 1: 

raise ValueError('left and right boundary values must have odd sum') 

if (j == -1 or j == n) and (i+j)%2 != 0: 

raise ValueError('up and down boundary values must have even sum') 

if i == -1: 

d = R 

elif i == n: 

d = L 

elif j == -1: 

d = U 

elif j == n: 

d = D 

elif d0 is None: 

d = FPL_edges[(i + j)%2][sv[i][j]][0] 

elif d0 in FPL_edges[(i+j)%2][sv[i][j]]: 

d = d0 

else: 

raise ValueError('invalid direction') 

# compute the link or loop 

while True: 

i += d[0] 

j += d[1] 

orbit.append((i,j)) 

if (i,j) == orbit[0] or \ 

i == -1 or j == -1 or \ 

i == n or j == n: 

break 

conf = sv[i][j] 

parity = (i + j) % 2 

d = FPL_turns[parity][conf][d] 

if d is None: 

raise RuntimeError 

if i == -1 or j == -1 or i == n or j == n: 

i0,j0 = orbit[0] 

if d0 is None and i0 != -1 and i0 != n and j0 != -1 and j0 != n: 

# only half of a link -> compute the other half 

i1,j1 = orbit[1] 

d = (i0-i1, j0-j1) 

orbit2 = self._link_or_loop_from(orbit[1], d) 

assert orbit2[0] == (i1,j1) and orbit2[1] == (i0,j0) 

return orbit2[:1:-1] + orbit 

return orbit 

else: 

return orbit 

def link_pattern(self): 

""" 

Return a link pattern corresponding to a fully packed loop. 

Here we define a link pattern `LP` to be a partition of the list 

`[1, ..., 2k]` into 2-element sets (such a partition is also known as 

a perfect matching) such that the following non-crossing condition holds: 

Let the numbers `1, ..., 2k` be written on the perimeter of a circle. 

For every 2-element set `(a,b)` of the partition `LP`, draw an arc 

linking the two numbers `a` and `b`. We say that `LP` is non-crossing