Implement Fully Packed Loop class

[kdilks]

The closest this ticket is from is 6.9beta4.

Create the FullyPackedLoop class which does the following:

• Add methods for ascii/graphical representation by modifying corresponding code for six vertex model.
• Add method to_alternating_sign_matrix.
• Add method link_pattern to extract link pattern/ non-crossing partition.

[egunawan]

I'm sorry Vince for using trac for development process, but I don't have everyone's email addresses. This is from the latest u/jcampbell/lp pull:

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: mat [ 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) sage: ncp = fpl.link_pattern()

---

KeyError? Traceback (most recent call last) <ipython-input-62-beb825ee7c96> in <module>()

---

/Users/eg/sageMar2015/sage/local/lib/python2.7/site-packages/sage/combinat/fully_packed_loop.pyc in link_pattern(self)

637 vertices_d[position] = 0 # allows us to start 638

--> 639 while not vertices_d[position]:

640 vertices_d.pop(position) 641 choices = self._get_coordinates(position)

KeyError?: (0, 2)

[jcampbell]

yeah it's not currently working quite right, i'll keep working on it over the flight though and hopefully figure out what's going wrong. G+ is probably the best way to contact me so add me on there :)

[egunawan]

Last 10 new commits:

​7e38bd9	Fixing merge conflict and a minor relic in init doc
​2eab0f1	Merge branch 'u/vinceknight/fpl' of trac.sagemath.org:sage into 18003
​457dbb4	creates _get_coordinates function
​8e569c2	completes algorithm
​b29b31e	iterates over keys and values
​5af8c34	fixes a few bugs
​8843710	adds tests and cleans up a few bugs
​8e9fd93	changes gap to space
​c0b0365	adds more tests
​e68af68	fixes get_coordinate function

[egunawan]

Last 10 new commits:

​b29b31e	iterates over keys and values
​5af8c34	fixes a few bugs
​8843710	adds tests and cleans up a few bugs
​8e9fd93	changes gap to space
​c0b0365	adds more tests
​e68af68	fixes get_coordinate function
​e154b0c	adds another test to get_coordinate
​176e328	code now produces correct answers, but tests are wrong
​5f3d15d	adds some bigger tests and fixes old ones
​0719175	#18003 Add tests for link_pattern and fix doc to say it returns a list. I did not check docbuild.

[kdilks]

I think the code for link pattern isn't properly tab aligned. Right now when I take an ASM and send it to a link pattern, I get the right result the first time, and then subsequent times I only get the last pair.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3d1fad1	copies dicitonary to ensure it can be run again
​44bf8f2	adds emilys tests
​1024081	James fixed bug which shows up when you call link_pattern() twice

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8e33669	#18003: Add test for previous bug which showed up when link_pattern in called twice for the same FullyPackedLoop self.
​0cbd4f6	#18003: Add __eq__ function for FullyPackedLoop

[egunawan]

I believe this is ready to be reviewed by Travis?

I added the equality functionality. I wanted to do a test like isinstance(other,FullyPackedLoop?), but I did not because of this behavior which I don't understand:

sage: A=AlternatingSignMatrices?(3) sage: M=A.random_element() sage: f=FullyPackedLoop?(M) sage: type(f) <class 'sage.combinat.fully_packed_loop.FullyPackedLoop?'> sage: isinstance(f,FullyPackedLoop?) False

[tscrim]

On my todo list.

[tscrim]

Okay, some comments after a quick look-over:

• I think you should implement a toggle map which swaps 2 vertical lines and 2 horizontal lines.
• You should make a parent class for all fully packed loops (on an n x n (m?) grid). The iterator could be a TransitiveIdeal generated by the toggles (or some other type of search using toggles), but perhaps there is a better way to do this. Also FullyPackedLoop then should be a subclass of Element.
• The .. math:: should be .. MATH::.
• You need more docuemntation for the class FullyPackedLoop, and the first line should be something like A fully packed loop. (a sentence which does not say "class", "implement", or other similar things). Also, it would be good to have some more references.
• Perhaps the vertices could be + instead of #, or we set that as a global_option (this is something I could do if you want)?
• Remove the commented out lines.
• The fpl.plot().description() output could potentially be machine dependent, so it would be better to test the number of such elements.

I will possibly have more comments as I make a more detailed review. However it's looking quite good.

This is more a note for myself to look at in more detail, but I think contains some interesting followup ideas: ​http://www.lpthe.jussieu.fr/~pzinn/semi/steklov.pdf.

[kdilks]

• I think we were putting off adding toggles and further functionality until we had things settled with defining the FPL class and extracting a link pattern. But it might not be too hard to add right now.
• Right now we're just assuming square ice boundary conditions, which forces n by n. At some point we'd like to have arbitrary boundary conditions (which would allow n by m, and would probably require some modification of previous code that implicitly assumes square shape). But again, conscious decision to try and limit how much we're taking on.
• Couldn't we just inherit whatever iterator SixVertexModel? or AlternatingSignMatrices? uses?
• I'm fine with vertices being '+' .
• I've been meaning to remove those commented lines, and make some other small edits to the documentation.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7289da2

#18003:Per tscrim's comment, replace # with + for vertices of ascii fully packed loop; replace lowercase .. math with .. MATH; remove lines that were commented out

[jessicapalencia]

Hi all, What's going on with this ticket at the moment? I see Emily addressed some of Travis's comments in the most recently pushed branch. Has anyone worked on the rest? (It looks like what is left is making a parent class, is this right?) Kevin, you said you have something to add to the doc, but I didn't see a commit. I'd be happy to work on the doc as well, but I don't think I can add the parent class. Could we either close this ticket without that, or can someone implement that? Thanks!

[vinceknight]

I'm a bit confused... When the gyration ticket got merged in I assumed that meant that this also got merged in. Did gyration not depend on this ticket?

[jessicapalencia]

No, I think #18021 just implemented gyration orbits in alternating_sign_matrix.py, but didn't do anything with the fpl class. There was #17988 which was closed since it was a duplicate of #18003 (this ticket). But this ticket is what implements fpl's and link patterns, and it's still at 'needs review'. I'd be happy to review this ticket as is and we could just open another ticket for adding the parent class if need be. I think I'll work on this tomorrow or Tuesday unless I hear otherwise.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cc75cae

Updated documentation for patch 18003.

[kdilks]

Added some sort of definition to the beginning of the file, and touched up a few typos/grammar problems. Definition at the beginning could probably use some touching up, and per Travis's  comment, could still use some more citations.

[tscrim]

Something else to change would be to make self._six_vertex_model (add the underscore) and then access it via a method so the FPL class acts as immutable. I'm also not happy with comparing equality by the repr's. I think it would be better to compare the underlying 6 vertex models. Also you should consider implementing a __ne__ method as well.

I also believe we should not merge this ticket without a corresponding parent class. The basic framework would be

class FullyPackedLoops(Parent, UniqueRepresentation):
    def __init__(self, n):
        self._n = n
        Parent.__init__(self, category=FiniteEnumeratedSets())

    def __iter__(self):
        for X in SixVertexModel(self._n):
            yield self.element_class(self, X)

    Element = FullyPackedLoops

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ab764e6

18003: try to fix merge conflict. Now in Sage 6.7 master

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​11fc275

18003:in alternating_sign_matrix.py test for method to_fully_packed_loop, replace # symbol with + symbol.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​09171de	18003: Add Jessica's March 2015 paper as a second reference. Add underscore to self._six_vertex_model. Add method self.six_vertex_model()
​1203adb	18003: equality is checked by comparing the underlying six vertex model as well as repr and end_points

[egunawan]

I added a method six_vertex_model and add underscore to self._six_vertex_model, but I'm not sure how to make sure that the FPL class acts as immutable or how to make it so.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​78dc525

18003:add parent class FullyPackedLoops. More functions still need to be added so that the following tests do not fail: _test_an_element, _test_elements, _test_enumerated_set_contains, _test_some_elements

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​636eafd	Merge branch 'public/ticket/18003' of http://trac.sagemath.org/sage into fpl18003
​f40f27c	Merge branch 'public/ticket/18003' of http://trac.sagemath.org/sage into fpl18003
​2bc5b37	18003: added missing closing asterisk in added reference

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7910b17	18003:add containment check and other functions (like AlternatingSignMatrices). Doc tests pass but SuiteTest does not pass. I'm not sure how to make SuiteTest Pass.
​dfcbaa8	merge emily's changes with kevin's. Merge branch 'public/ticket/18003' of trac.sagemath.org:sage into fullypackedloopSage67Master

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​310eb70

18003: TestSuites for both FullyPackedLoop and FullyPackedLoops pass. Doc builds. Ideally we should check that a given SixVertexConfiguration is also a SquareIceModel - how should we do that?

[tscrim]

Some notes about your _element_constructor_, you don't need to check fpl.parent() is self, as the coercion model has already checked that and would have returned that. Which is why your test actually works. If you try to pass in the ASM, your _element_constructor_ will return None. I think what you should do is copy the implementation from __classcall_private__ into _element_constructor_ and then have __classcall_private__ return FPLs(generator). You might also want to consider passing other types of data to a corresponding SVM in the _element_constructor_.

You can test for a SVM to be the square ice configuration by isinstance(SVM, SquareIceModel.Element).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e570958

18003: Check whether a generator is an ASM or SquareIceModel.element (instead of any SixVertexConfiguration)

[egunawan]

How come AlternatingSignMatrices?._element_constructor_ checks if asm.parent() is self? Is that also redundant?

[tscrim]

Replying to egunawan:

How come AlternatingSignMatrices?._element_constructor_ checks if asm.parent() is self? Is that also redundant?

It is also redundant (I might have suggested it, or at least thought it was necessary, before Nicolas told me about the fact the coercion framework handles that case before _element_constructor_ even sees it).

[egunawan]

Does it matter which line we write "Element = FullyPackedLoop?"? Anywhere under "class FullyPackedLoops?(Parent, UniqueRepresentation?):"?

[tscrim]

No, for the same reason the order of the methods doesn't matter.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​94ced9c

18803: Do the following changes: Some notes about your _element_constructor_, you don't need to check fpl.parent() is self, as the coercion model has already checked that and would have returned that. Which is why your test actually works. If you try to pass in the ASM, your _element_constructor_ will return None. I think what you should do is copy the implementation from __classcall_private__ into _element_constructor_ and then have __classcall_private__ return FPLs(generator).

[egunawan]

Replying to tscrim:

You might also want to consider passing other types of data to a corresponding SVM in the _element_constructor_.

What types of data for example?

[tscrim]

Replying to egunawan:

Replying to tscrim:

You might also want to consider passing other types of data to a corresponding SVM in the _element_constructor_.

What types of data for example?

Something that could be used to construct a six-vertex configuration:

SVM = SixVertexModel(2)
SVM([[3,1],[5,3]])

So it would make this work:

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0962f9f	Merge to latest develop. Merge branch 'public/ticket/18003' of git://trac.sagemath.org/sage into fpl
​c5386d9	18003: after merging to sage 6.9beta4, make fixes so that doc builds (I did this by following alternating_sign_matrix.py)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cd67eed	18003
​2704814	18003:
​38e19ec	18003: doc is not run this time.

[egunawan]

I'm not sure what is causing the PluginOnlyFailed?.

[tscrim]

The coverage failure, I'm no so sure (FYI you can click on the patchbot info to see details). However the import modules failure is reflecting the fact that you are not lazily importing this new file (which is there in an effort to try and keep startup time down). So I would add this line instead of the straight import:

lazy_import('sage.combinat.fully_packed_loop', ['FullyPackedLoop', 'FullyPackedLoops'])

A couple of things about the ticket/code itself:

• matrix and also extract the link pattern.:: either remove the period or put a space after it.
• You should not put examples/information for the user in the __init__, instead move it to the class level docstring (for FullyPackedLoop). The __init__ still needs to have a doctest, and a good one is to typically create an element X and then do TestSuite(X).run(), but you already have this, so leave the TESTS:: block.
• In to_alternating_sign_matrix, remove the blank line at the beginning of the docstring and start with Return.
• You don't need :math:`x = y`, just `x = y` with the backticks is sufficient. If you want it similar to equation mode in latex, do

  .. MATH::
  
      x = y
  

• The EXAMPLES:: block in plot is indented one to many times.
• For notes, you might want to consider using the .. NOTE:: block (in link_pattern).
• Period missing in six_vertex_model one-line sentence.
• I would make _vertex_dictionary a lazy attribute (grep for @lazy_attribute). FYI - This means it's created on-demand and acts like a regular attribute, so self._vertex_dictionary[i] works. Essentially it is cached, so the downside to this is that the dictionary gets kept alive as long as that FPL is, but I think each instance is not kept alive too long. It's up to you.
• Same for _end_point_dictionary. In a similar vein, I would remove the (public) attribute end_points and just use _end_point_dictionary.
• First line of FullyPackedLoops needs a period and an empty line of space.
• cardinality is missing a period at the end of the equation.
• Remove the commented out code in _element_constructor_.
• You need to provide a description of link_pattern.
• You should describe the bijection with ASMs somewhere, most likely in the FullyPackedLoops (resp. FullyPackedLoop) class and add .. SEEALSO:: to that class in FullyPackedLoop (resp. FullyPackedLoops) and to_fully_packed_loop.
• The documentation at the top of the file is good, but you can't read it interactively (only on the online/compiled documentation). I would suggest moving it to either FullyPackedLoops or FullyPackedLoop, depending on which you think is the more common entry point.
• I think the variable name of current in _get_coordinates is confusing and you should rename it to something more descriptive.

Looking very good overall, as almost all of these are trivial to minor tweaks. That's all for now.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0593ac7	18003: In all.py, add: lazy_import('sage.combinat.fully_packed_loop', ['FullyPackedLoop', 'FullyPackedLoops’]). Doc builds here.
​b7dac93	18003: Doc builds and HTML doc looks good. Minor doc clean up per comments from reviewer.
​1b5ddd4	18003: In :meth:, should say self==other (previously self==self). In general, remove (public) attribute end_points and just use _end_point_dictionary().
​6329e6a	18003: Make _vertex_dictionary and _end_point_dictionary lazy attributes (@lazy_attribute). Fix bug in link_pattern (again) by copying self._vertex_dictionary. This bug shows up when :meth: is called twice.
​cab09b1	18003: Doc builds and HTML doc looks fine. In :meth:`_get_coordinates`, change variable name from current to current_pos to make it more descriptive. Move doc at the top of file to FullyPackedLoop
​968f0a4	18003: Doc builds. Add description to :meth:

[egunawan]

I don't understand your comment about :math:x = y?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​09c5de4

18003: Add SEEALSO:: to AlternatingSignMatrix.to_fully_packed_loop and FullyPackedLoop.to_alternating_matrix.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​98f691d

18003: Fix the link to [Striker2015]. Add SEEALSO:: AMSs to FullyPackedLoop and FullyPackedLoops

[nadialafreniere]

New commits:

​98f691d

18003: Fix the link to [Striker2015]. Add SEEALSO:: AMSs to FullyPackedLoop and FullyPackedLoops

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​96b3a1b

18003: Improve doc for _end_point_dictionary and _endpoints_

[tscrim]

In regard to the :math:`...` comment, I would make this change:

     def plot(self):
-        """
+        r"""
         Return a graphical object of the Fully Packed Loop
 
         EXAMPLES:
 
-         Here is the fully packed for :math:`\\begin{pmatrix}0&1&1\\\\1&-1&1\\\\0&1&0\end{pmatrix}`:
+         Here is the fully packed for
+
+         .. MATH::
+
+             \begin{pmatrix} 0&1&1 \\ 1&-1&1 \\ 0&1&0 \end{pmatrix}:
 

There is also a [TODO] that you added that needs to be either removed, expanded (and put in a .. TODO:: block), or done. Thanks.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1416b48

18003: Fix incorrect matrix latex. Add publication info to [Striker2015] and remove [TODO]. Html doc looks fine.

[tscrim]

Looks good to me now. Thanks!

[jessicapalencia]

That's really exciting - great work everyone!

[vinceknight]

Nice job guys! :)

[egunawan]

Hi all, Why did we choose FullyPackedLoop? to be an Element class (as opposed to, say, ClonableArray? like SixVertexConfiguration?)? (I am working on a creating a new combinatorial object now and deciding which data type to use.) Thank you!

[tscrim]

Replying to egunawan:

Hi all, Why did we choose FullyPackedLoop? to be an Element class (as opposed to, say, ClonableArray? like SixVertexConfiguration?)? (I am working on a creating a new combinatorial object now and deciding which data type to use.) Thank you!

Because internally it is not a list but essentially a wrapper around a SixVertexConfiguration. Feel free to send me an email if you want to talk in more detail.