#18003 closed enhancement (fixed)
Implement Fully Packed Loop class
Reported by:  kdilks  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  fpl, ncp, days64, days65, asm, lp, fully packed loop 
Cc:  tscrim, jessicapalencia, egunawan, vinceknight, jcampbell, kdilks, nadialafreniere, mlapointe  Merged in:  
Authors:  James Campbell, Vince Knight, Jessica Striker, Kevin Dilks, Emily Gunawan  Reviewers:  Jessica Striker, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  1416b48 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
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/ noncrossing partition.
Change History (65)
comment:1 Changed 6 years ago by
 Cc vinceknight jcampbell kdilks added
 Description modified (diff)
comment:2 Changed 6 years ago by
 Cc jessicapalencia added; jstriker removed
 Keywords asm added
comment:3 Changed 6 years ago by
 Description modified (diff)
 Keywords lp added
 Summary changed from Extract noncrossing matching from Fully Packed Loop to Extract noncrossing matching (link pattern) from Fully Packed Loop
comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
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 :)
comment:6 Changed 6 years ago by
 Branch set to u/jcampbell/lp
 Commit set to e68af68a1fd276343a9ad717b0cecb0a523fac02
 Dependencies set to 17988
comment:7 Changed 6 years ago by
 Branch u/jcampbell/lp deleted
 Commit e68af68a1fd276343a9ad717b0cecb0a523fac02 deleted
 Description modified (diff)
comment:8 Changed 6 years ago by
 Branch set to public/ticket/18003
 Commit set to 071917548a5ab9531331bf9f2ee85037875333b9
 Description modified (diff)
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.

comment:9 Changed 6 years ago by
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.
comment:10 Changed 6 years ago by
 Commit changed from 071917548a5ab9531331bf9f2ee85037875333b9 to 1024081e05ad51eade1950b6dcdf501dd6f7de7e
comment:11 Changed 6 years ago by
 Commit changed from 1024081e05ad51eade1950b6dcdf501dd6f7de7e to 0cbd4f6d2306e42b2e801c05ca81f2699df35a2d
comment:12 Changed 6 years ago by
 Dependencies 17988 deleted
 Description modified (diff)
 Keywords fully packed loop added
 Reviewers set to Jessica Striker, Travis Scrimshaw
 Summary changed from Extract noncrossing matching (link pattern) from Fully Packed Loop to Implement Fully Packed Loop class
comment:13 Changed 6 years ago by
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
comment:14 Changed 6 years ago by
 Status changed from new to needs_review
comment:16 Changed 6 years ago by
Okay, some comments after a quick lookover:
 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 aTransitiveIdeal
generated by the toggles (or some other type of search using toggles), but perhaps there is a better way to do this. AlsoFullyPackedLoop
then should be a subclass ofElement
.  The
.. math::
should be.. MATH::
.  You need more docuemntation for the class
FullyPackedLoop
, and the first line should be something likeA 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 aglobal_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.
comment:17 Changed 6 years ago by
 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.
comment:18 Changed 6 years ago by
 Commit changed from 0cbd4f6d2306e42b2e801c05ca81f2699df35a2d to 7289da2f39c98084a24505a4aa74e6fe2a5ca14a
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

comment:19 Changed 6 years ago by
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!
comment:20 Changed 6 years ago by
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?
comment:21 Changed 6 years ago by
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.
comment:22 Changed 6 years ago by
 Commit changed from 7289da2f39c98084a24505a4aa74e6fe2a5ca14a to cc75caeaf1819cd8e27e88c5ba003fb4c3d57cf8
Branch pushed to git repo; I updated commit sha1. New commits:
cc75cae  Updated documentation for patch 18003.

comment:23 Changed 6 years ago by
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.
comment:24 Changed 6 years ago by
 Status changed from needs_review to needs_work
 Work issues set to create a parent class
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
comment:25 Changed 6 years ago by
 Cc VivianePons added
comment:26 Changed 6 years ago by
 Keywords days65 added
comment:27 Changed 6 years ago by
 Commit changed from cc75caeaf1819cd8e27e88c5ba003fb4c3d57cf8 to ab764e6aadec525d37d46502a56d5db40deaa125
Branch pushed to git repo; I updated commit sha1. New commits:
ab764e6  18003: try to fix merge conflict. Now in Sage 6.7 master

comment:28 Changed 6 years ago by
 Commit changed from ab764e6aadec525d37d46502a56d5db40deaa125 to 11fc275fdf2f1b07f11a732b0f015816a0266716
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.

comment:29 Changed 6 years ago by
 Commit changed from 11fc275fdf2f1b07f11a732b0f015816a0266716 to 1203adb99b153640ae3dcf80601bfe7a38fac570
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

comment:30 Changed 6 years ago by
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.
comment:31 Changed 6 years ago by
 Commit changed from 1203adb99b153640ae3dcf80601bfe7a38fac570 to 78dc525a1dd30d7a375c86f32f37e4216577351a
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

comment:32 Changed 6 years ago by
 Commit changed from 78dc525a1dd30d7a375c86f32f37e4216577351a to 2bc5b37a6fcb63902c94e59694e874a58699bb5c
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

comment:33 Changed 6 years ago by
 Commit changed from 2bc5b37a6fcb63902c94e59694e874a58699bb5c to dfcbaa89ae2f272620522be79f87a3b1790c0323
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

comment:34 Changed 6 years ago by
 Commit changed from dfcbaa89ae2f272620522be79f87a3b1790c0323 to 310eb70ad9b93932f34316fd52628af3568d8362
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?

comment:35 followup: ↓ 42 Changed 6 years ago by
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)
.
comment:36 Changed 6 years ago by
 Commit changed from 310eb70ad9b93932f34316fd52628af3568d8362 to e570958c71ae97e4b50d078c361880fd2c48302b
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)

comment:37 followup: ↓ 38 Changed 6 years ago by
How come AlternatingSignMatrices?._element_constructor_ checks if asm.parent() is self? Is that also redundant?
comment:38 in reply to: ↑ 37 ; followup: ↓ 39 Changed 6 years ago by
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).
comment:39 in reply to: ↑ 38 Changed 6 years ago by
Does it matter which line we write "Element = FullyPackedLoop?"? Anywhere under "class FullyPackedLoops?(Parent, UniqueRepresentation?):"?
comment:40 Changed 6 years ago by
No, for the same reason the order of the methods doesn't matter.
comment:41 Changed 6 years ago by
 Commit changed from e570958c71ae97e4b50d078c361880fd2c48302b to 94ced9c7a9ec791a18df05e138eb6a39d291f5f1
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).

comment:42 in reply to: ↑ 35 ; followup: ↓ 43 Changed 6 years ago by
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?
comment:43 in reply to: ↑ 42 Changed 6 years ago by
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 sixvertex 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]])
comment:44 Changed 6 years ago by
 Commit changed from 94ced9c7a9ec791a18df05e138eb6a39d291f5f1 to c5386d92539b7036f9dc4ee3964af25052059483
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)

comment:45 Changed 6 years ago by
 Commit changed from c5386d92539b7036f9dc4ee3964af25052059483 to 38e19ec52d4b18ebc5725ed68cc75432ce1ac51f
comment:46 Changed 6 years ago by
 Cc tscrim added; VivianePons removed
 Milestone changed from sage6.6 to sage6.9
 Status changed from needs_work to needs_review
comment:47 Changed 6 years ago by
I'm not sure what is causing the PluginOnlyFailed?.
comment:48 Changed 6 years ago by
 Status changed from needs_review to needs_work
 Work issues create a parent class deleted
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 (forFullyPackedLoop
). The__init__
still needs to have a doctest, and a good one is to typically create an elementX
and then doTestSuite(X).run()
, but you already have this, so leave theTESTS::
block.  In
to_alternating_sign_matrix
, remove the blank line at the beginning of the docstring and start withReturn
.  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 inplot
is indented one to many times.  For notes, you might want to consider using the
.. NOTE::
block (inlink_pattern
).  Period missing in
six_vertex_model
oneline sentence.  I would make
_vertex_dictionary
a lazy attribute (grep for@lazy_attribute
). FYI  This means it's created ondemand and acts like a regular attribute, soself._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) attributeend_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 inFullyPackedLoop
(resp.FullyPackedLoops
) andto_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
orFullyPackedLoop
, 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.
comment:49 Changed 6 years ago by
 Commit changed from 38e19ec52d4b18ebc5725ed68cc75432ce1ac51f to 968f0a44112ee12916685c3cb21ae167ddf3a09b
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:

comment:50 Changed 6 years ago by
I don't understand your comment about :math:x = y
?
comment:51 Changed 6 years ago by
 Commit changed from 968f0a44112ee12916685c3cb21ae167ddf3a09b to 09c5de4f6836e5e5e63ccdc8929bda6836f36bfa
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.

comment:52 Changed 6 years ago by
 Commit changed from 09c5de4f6836e5e5e63ccdc8929bda6836f36bfa to 98f691d084967ade47e74660d457052f324a153c
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

comment:53 Changed 6 years ago by
 Cc nadialafreniere added
New commits:
98f691d  18003: Fix the link to [Striker2015]. Add SEEALSO:: AMSs to FullyPackedLoop and FullyPackedLoops

comment:54 Changed 6 years ago by
 Cc mlapointe added
comment:55 Changed 6 years ago by
 Commit changed from 98f691d084967ade47e74660d457052f324a153c to 96b3a1b365e1098ddcf78909adfa9269d2efe933
Branch pushed to git repo; I updated commit sha1. New commits:
96b3a1b  18003: Improve doc for _end_point_dictionary and _endpoints_

comment:56 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:57 Changed 6 years ago by
 Description modified (diff)
comment:58 Changed 6 years ago by
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.
comment:59 Changed 6 years ago by
 Commit changed from 96b3a1b365e1098ddcf78909adfa9269d2efe933 to 1416b489b340236f50fa14b05b21029d4aae6b00
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.

comment:60 Changed 6 years ago by
 Status changed from needs_review to positive_review
Looks good to me now. Thanks!
comment:61 Changed 6 years ago by
That's really exciting  great work everyone!
comment:62 Changed 6 years ago by
 Branch changed from public/ticket/18003 to 1416b489b340236f50fa14b05b21029d4aae6b00
 Resolution set to fixed
 Status changed from positive_review to closed
comment:63 Changed 6 years ago by
 Commit 1416b489b340236f50fa14b05b21029d4aae6b00 deleted
Nice job guys! :)
comment:64 followup: ↓ 65 Changed 3 years ago by
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!
comment:65 in reply to: ↑ 64 Changed 3 years ago by
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.
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) <ipythoninput62beb825ee7c96> in <module>()
/Users/eg/sageMar2015/sage/local/lib/python2.7/sitepackages/sage/combinat/fully_packed_loop.pyc in link_pattern(self)
> 639 while not vertices_d[position]:
KeyError?: (0, 2)