Path_Tableaux

[Bruce]

This is a project to implement an abstraction of rectification, evacuation and promotion. These are conventionally defined on standard tableaux using jeu-de-taquin. The file catalan.py gives a toy implementation. I intend to provide other implementations.

[Bruce]

I have been unable to push my commits. I get Permission Denied. I will try again in the morning.

[embray]

It seems there was something about this branch causing the git merge plugin to break so I have deleted the branch for now and will investigate further later.

[embray]

It seems the branch was just the current develop with no new commits on it, so maybe something about that scenario broke the plugin.

[Bruce]

Replying to embray:

It seems the branch was just the current develop with no new commits on it, so maybe something about that scenario broke the plugin.

Thanks for sorting that out. I struggled to follow the instructions and no doubt got it messed up.

[gh-darijgr]

New commits:

​e09a7bb	This is the initial commit for the project on Path Tableaux
​934c015	Corrected path
​7157b1f	Edited a couple of doc tests
​3090a75	A few trivial changes.

[git]

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

​a89516e	Changed all.py
​8944c6e	Fixed imports so doc tests now run.

[git]

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

​7d6fef0

Imports into semistandard.py fixed

[embray]

Replying to Bruce:

Replying to embray:

It seems the branch was just the current develop with no new commits on it, so maybe something about that scenario broke the plugin.

Thanks for sorting that out. I struggled to follow the instructions and no doubt got it messed up.

No problem, not your fault at all.

[git]

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

​bfcfc84	Added doc tests
​391ffd0	More doc testing

[git]

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

​f9abd6b	Started doc testing semistandard.py
​0d1e91f	Added rectify and multiply
​16c04c4	Added rectify

[git]

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

​e5cb861

Rectify added

[Bruce]

I now have the basic functionality in the two implementations I have committed. I would appreciate some feedback before I commit other implementations. I have attempted to explain the purpose of this project but no doubt I could do better.

[tscrim]

I strongly believe that PathTableaux should not be a category. You should just have an abstract base class (ABC) for the *Tableau objects (the ElementMethods is currently playing this role, but you're using a sledgehammer in place of a ball-peen). It is something that is easy to change back if there becomes a practical use/need for the category, but I think it puts more distance between the concrete class and the ABC code, which makes it harder to maintain.

At this point, I am thinking it might be best to make a new folder in the combinat folder called tableau with your new code (one file for the ABC and your other two files). Then it will become the eventual home for all tableau files (but moving those should be done on separate tickets).

Some other misc comments:

• What is this doing here: #!/usr/bin/env python2?
• I would call the method plot instead of draw.
• Your drawL and drawC might be best as separate standalone functions in the ABC file. Otherwise if you feel that they should be methods, then make them hidden by calling them _drawL and _drawC.
• I don't see the point of having draw_partition in drawL as an internal helper function (in drawC, it makes sense because of the two for loops and avoiding code duplication).
• There are a bunch of malformatted docstrings (EXAMPLES: -> EXAMPLES:: (or missing altogether) when followed by code, which should be indented by 1), and some that should be at the class level or at the top of the module.
• The copyright should be comments, not part of the docstring.

[git]

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

​0ae66fe

Corrected formatting of doctests

[Bruce]

Hi Travis, Thank you for the feedback.

"At this point, I am thinking it might be best to make a new folder in the combinat folder called tableau with your new code (one file for the ABC and your other two files). Then it will become the eventual home for all tableau files (but moving those should be done on separate tickets)."

Could you please expand on this? I understand your suggestion to use an ABC instead of a category. I am not clear on how this should be done within the trac system. I understand that I could open a new ticket, copy the files by hand, and at some point delete the existing ticket. However I suspect you may mean a different approach.

Is the first step to create a new ticket with the new folder called tableau containing just one file with the ABC?

[gh-darijgr]

You can keep making commits and pushing to the same branch (and set the ticket back to needs_review once you're done fixing the issues you're aware of).

[git]

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

​cdef4c8

Corrections to doctests with ellipsis

[git]

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

​d562246

Files moved to new directory

[git]

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

​8d0191a	Edited and added files all.py
​18aaf93	File __init__.py added
​5aa14e1	Moved directory from tableau to pathtableau

[git]

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

​f20a5d1

Parent classes added

[git]

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

​4adad87

All tests passed!

[git]

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

​9c0cd75

PathTableau_partitions added and more doctests

[Bruce]

I have made the changes suggested by Travis, including removing the Category and using an ABC instead. I am working on missing doctests. I would appreciate further feedback.

[git]

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

​f4d341f	multiply doctest added
​7cb9d1f	More doctests
​8b21628	rule changed to avoid use of vector
​c751cc0	Moved tests. Use _test_ and other minor changes on tests.
​bb2caa0	Moved PathTableaux class back
​8715ae9	All doctests pass

[git]

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

​800560c

Modified all.py

[git]

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

​6229e0d

Semistandard removed

[git]

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

​efdd91d

Documentation updates

[git]

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

​a3a6472

Doctests added

[kdilks]

Is from sage.combinat.pathtableau.all import * right? I don't think the .all is supposed to be there. Tried to run patchbot and immediately crashed because of that.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​f4b5642

updated all.py

[git]

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

​3d2f309

git added all.py and __init__.py

[kdilks]

For python 3 compatability, the two print commands in commutor() should be changed from 'print stuff' to 'print(stuff)' .

[Bruce]

The method _rule_ should have @staticmethod (before @abstractmethod)

[Bruce]

There should be references.

[tscrim]

I also think we should rename _rule_ -> _rule as methods with a leading and trailing underscores (_) are generally considered as special Sage functions.

In addition to the Python3 compatibility mentioned in commment:43, the test for dual_equivalence_graph seems quite brittle. It would be better to explicitly construct the graph and compare it by isomorphism.

I don't see why you have a PathTableaux class. It look like it is a very malformed parent.

[embray]

I would also like to test this ticket on top of my python 3 branch, but that is up to me to do. Not that python 3 is technically supported yet, so if there are any significant issues in other parts of Sage that affect this code on python 3 then I won't worry about it. But it would be nice to keep significant new code forward-compatible where possible.

[git]

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

​baae1df	Reference added
​a716ba8	Reference changed
​e36c89b	Fixed reference
​52b8488	Ref
​f03e476	Ref
​295aeeb	Ref
​269ded8	Ref
​340117e	Ref

[Bruce]

Replying to tscrim:

the test for dual_equivalence_graph seems quite brittle. It would be better to explicitly construct the graph and compare it by isomorphism.

I understand this to mean my code could construct the wrong graph but this test would not notice if it happened to have the same adjacency matrix. Really? or did you mean something else?

I don't see why you have a PathTableaux class. It look like it is a very malformed parent.

Could you please expand on this? I take malformed to be pejorative. I will want these to be (finite) enumerated sets but I haven't thought this through yet.

[Bruce]

Replying to Bruce: This takes care of comments 44, 45 and the first sentence in 47.

[Bruce]

Replying to git:

This takes care of comment 46.

[Bruce]

It seems I could use RecursivelyEnumeratedSet() to give a generic enumeration. Just because I can do something doesn't mean I should.

Does anyone think this would be reasonable? or unreasonable?

[mantepse]

You could have a look at #25173, where I have done this for staircase tableaux. Also, I am a bit surprised that you do not reference our joint paper, I must say.

[Bruce]

Replying to mantepse:

You could have a look at #25173, where I have done this for staircase tableaux. Also, I am a bit surprised that you do not reference our joint paper, I must say.

Is there any code for #25173 (apart from sl3webs.sage? or is it a "wish list"?

I will refer to our joint paper in the relevant implementations. At the moment I am concentrating on getting a positive review for the ABC and the toy implementation.

[mantepse]

sl3webs.sage contains (possibly) relevant code. Just look for "RecursivelyEnumeratedSet?"!

[git]

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

​c3cde2e	Used clone
​5dcc336	Another clone

[git]

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

​d346b00	Element added
​88862d6	Element imported
​124c505	Sets

[git]

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

​954048e	Element removed
​57c76e2	Directory and filename changed
​8df41ac	Edit to all.py
​212d2ad	Corrected names

[Bruce]

I am working on implementing RecursiveEnumeratedSets? and introducing Parents whose category is EnumeratedSets?. I am struggling as I don't have an example to follow; DyckWords? is the nearest I have found but this uses a deprecated backtracker.

[git]

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

​e2c3b14	Added __getattr__ and several Parents
​830636d	Added __getatrr__ and other minor changes
​d60ce49	More work
​236ae8b	Added construction from skew tableau

[git]

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

​11c5eb6	File names changed in __init__.py
​0818203	Made _rule a helper function.
​ee430d5	Made _rule a helper function

[git]

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

​bcd1acd

Tidy up

[gh-BruceWestbury]

I have now made all modifications following conversations at ICERM and subsequent comments. The only one I am not sure about is whether I have correctly dealt with Travis' comment on "malformed parents".

I would be grateful for a review.

[tscrim]

Now you have a proper parent and element. So that part is a good improvement over trying to do things with categories.

A naming convention, you should call the folder path_tableaux. For filenames, etc. that are all lowercase, words are separated by underscores _.

I believe you are better using ClonableArray instead of ClonableList because your object should be a fixed length because it is effectively immutable.

All methods need a doctest, including __classcall_private__ and the abstract _local_rule.

Instead of display, the somewhat standard argument name is verbose.

I think your __getattr__ hack is dangerous and violates the principle of least surprise. It is dangerous because suppose you have two PathTableau that convert to each other but neither implements a given method. My understanding is that would lead to an infinite loop. It is also slow because it has to do and then check for each such conversion. Nor does not dispatch to base classes, which might interfere with some of the hacks of the category framework (I would have to check this one specifically, but this might not be an issue because this is not a Cython class).

This is also extremely brittle as it depends heavily on implementations in other unrelated classes (violating code locality) and the result depends strongly on the order of _conversions. Which brings me to the violation the principle of least surprise. Suddenly you get a DyckPath instead of a PathTableau when asking for a method that might be natural or nonsense:

sage: t = CatalanTableau([0,1,2,3,2,1,0])
sage: t.to_DyckWord()
[1, 1, 1, 0, 0, 0]
sage: _.reverse()
[1, 1, 1, 0, 0, 0]
sage: t.reverse()
[1, 1, 1, 0, 0, 0]

These are PathTableau, so either you implement methods directly there or you explicitly convert.

The rest of it mostly looks good other than perhaps a few small formatting tweaks. I can address those once the above is taken care of.

[git]

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

​e25e2aa	Merge branch 'develop' into t/25434/pathtableaux
​6518f21	Dealt with Travis' objection to my __getattr__ hack and most of his other comments.
​ec63927	Made minor changes to catalan.py

[git]

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

​12b27c4	Changed directory name
​653f8a5	Changed import to new file names

[Bruce]

I believe I have taken care of Travis' comments.

[git]

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

​03152b8

Moved ClonableArray from ABC class to implementation

[kdilks]

Realized that I should probably focus on this one before (or at least concurrently with) oscillating tableau. Travis has hopefully covered all the bases in terms of the programming technicalities (and should probably confirm before this gets a final positive review), I'll focus more on doc/usability.

Some of my previous comments from oscillating tableau actually apply to this ticket (I didn't realize this ticket was being pulled into oscillating tableau ticket as a dependency).

• Adding the underscores to the folder/file names requires a few other lines to be changed. In src/doc/en/reference/combinat/module_list.rst, the line sage/combinat/pathtableau/catalan needs to be updated to sage/combinat/path_tableau/catalan. Also, sage/combinat/pathtableau/pathtableaux needs to be updated to sage/combinat/path_tableau/path_tableaux. Finally, in CatalanTableaux?, the link :class:`sage.combinat.pathtableau.pathtableaux` needs to be updated to :class:`sage.combinat.path_tableau.path_tableaux`.

• As with OscillatingTableaux?, the docstrings for CatalanTableaux? need to be moved from _classcall_private_ up to the class itself.

• descents method needs some sort of definition, because in particular, whatever definition is used here doesn't agree with my first idea of what it should be (i appearing in a row below i+1 in the associated two row tableau.

• to_perfect_matching should first check to see if the tableau is skew, and give an appropriate error message (rather than having the call to DyckWord? fail). Furthermore, if you input something that doesn't end at 0 (corresponding to a two-row tableau with uneven rows), the code still returns a perfect matching, and I'm not sure this is desired behavior.

• I would modify to_tableau some, because it should be possible to have this return a StandardTableau? in the case where you start with 0 and aren't actually skew. I would have the default behavior check is_skew, and then use the appropriate constructor. I suppose there could be situations where you always want your output to use the SkewTableau? constructor, so there could be some optional parameter like skew=False that you could set to be True if you always wanted to use the SkewTableau? constructor.

• PathTableaux? needs some kind of general definition of what path tableaux actually are. It should appear both with the current description of what it's trying to abstract (which should appear at the top of the documentation page for the module), and also for the PathTableau? class itself (so it will show up when viewing PathTableau?? ).

• Right now, there's just a method to apply the action of a single cactus group generator. It may be useful to have a method that would take a list/sequence of generators and apply them successively.

• The method commutor should give some kind of general definition of what the commutor actually is.

[git]

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

​415e704

I can't spell in French

[git]

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

​9156fb4	Merge branch 'u/kdilks/pathtableaux' of git://trac.sagemath.org/sage into pathtab25434
​4f51907	Moved doc from classcall, added check in to_perfect_matching for skewness
​cd325b4	modified to_tableau method

[git]

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

​1b7e134

Edited doc strings.

[tscrim]

EXAMPLE:: -> EXAMPLES:: which should also have a blankline after it.

Many methods do not have doctests.

Remove the CylndricalDiagram.__str__ and change the __repr__ -> _repr_. You should also implement an _ascii_art_ (and possibly a _unicode_art_) and have pp call that.

For the _test_involution, I would move the all out and do an explicit for loop that tests each pair (better control of what fails). Also this way you can also use tester._max_runs in case size() is really big.

PathTableau should inherit from ClonableArray. IMO your divider comments in that class should be indented to make it easier to read too.

I don't see the point of the _rule function in _local_rule. Just put that in the for loop.

What follows after an INPUT: block should *not* be indented.

The docstring for catalan.py should be first, not the copyright

[git]

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

​716b7ce	Added __init__ in CatalanTableau
​544eb66	Made corrections requested by Travis.

[tscrim]

Is this suppose to be back to needs review?

[chapoton]

• never use EXAMPLES:: twice in the doc for one method or function

• There is a missing empty line after one EXAMPLES::

• please do not add empty methods

[embray]

Ticket retargeted after milestone closed

[mkoeppe]

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[git]

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

​03ce5dd	No idea
​ce528c3	Merge branch 'develop' into t/25434/pathtableaux
​2473d5b	Minor edits
​f3dc239	Worked on doc tests
​3d82797	All tests passed!
​009466d	Added doc tests
​7884fc5	More tests

[Bruce]

I have improved the coverage of documentation and testing in response to comments by Scrimshaw and Chapoton. There were some places where I was not confident I was getting it right.

[chapoton]

Looking at the patchbot report, one sees:

In the first lines of method docs, replace "Returns" by "Return":

++        Returns a string representation of ``self``
++        Returns a `\LaTeX` representation of ``self``
++        Returns an ascii art representation of ``self``
++        Returns a unicode art representation of ``self``

There is one function missing documentation:

+combinat/path_tableaux/path_tableau.py: 95.8% (23 of 24)

Moreover, by a quick look at the ticket:

Also, always have an empty line after the first line of the doc of any function or method.

[git]

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

​c0c9e5c

Tidied documentation

[Bruce]

I have fixed the above.

The method without a doctest is _element_constructor_ on line 422

I am not sure when this gets called. I assume it has been called several times implicitly in the existing doctests and I don't know what an explicit doctest would do.

[git]

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

​f5887d6

Removed trailing spaces

[chapoton]

For the element_constructor doctest, you can add one or several creations of elements, tagged with # indirect doctest

[chapoton]

From comment:78

What follows after an INPUT: block should *not* be indented.

has not been taken care of yet.

[chapoton]

Each raise statement must be triggered in one doctest. For example

raise ValueError("the perfect matching must be non crossing")

[chapoton]

Still some empty lines missing, for instance

+        TESTS::
+            sage: CatalanTableau([0,1,0,-1,0])

[git]

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

​ddf1a4b

Completed doctests

[git]

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

​51d3b73	Added tests of ValueError
​7866ab4	More tests

[chapoton]

Travis, any opinion ? I am not sure that we want these things in the global namespace.

[tscrim]

I am inclined to agree with you. It probably would be best as a catalog of the form path_tableaux.Name and have that be in the global namespace.

There are also a few places (e.g., in to_word()) that need the docstring to being r""" (although I would argue you should essentially always do this to be safe).

There are also a few other places where the docstrings are not formatted for Sage (cactus has $'s, PathTableaux really has a one-line docstring (instead of having the """ on their own lines), one-line docstrings should end in a period/full-stop, etc.) However these are very minor things.

[git]

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

​387c0bd

Minor changes in doc strings

[git]

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

​4747bd6	Added catalog.py and changed name
​8567a47	Changed _local_rule to local_rule
​767405c	Tried to write catalog.py

[git]

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

​0942d3b	Edited combinat/all.py all.py etc. to import from catalog
​62e7e63	Minor edits

[tscrim]

I did some revisions to get everything up to Sage's standards and make the catalog be lazily imported (and the only entry point). In particular, I removed the PathTableau[x] from the catalog since they are ABCs.

---

New commits:

​214c067	Merge branch 'u/Bruce/pathtableaux' of git://trac.sagemath.org/sage into public/combinat/path_tableaux-25434
​bc8119f	Doing some cleanup to pass doctests, better test coverage, and lazy importing the catalog.

[Bruce]

Thanks Travis.

[git]

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

​ad8ca4d

Fixing the docbuild by having the correct files listed.

[tscrim]

Green patchbot.

[tscrim]

So are my changes good? Is this a positive review?

[tscrim]

One more thing that needs to be done: the DyckPaths needs an _an_element_ method. Then you can change this test, which is wrong:

-            sage: t = path_tableaux.DyckPath([0,1,2,1,0])
+            sage: t = path_tableaux.DyckPaths()
             sage: TestSuite(t).run()

[git]

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

​b248c6a	Changed to one line if
​79192f9	Merge branch 'public/combinat/path_tableaux-25434' of git://trac.sagemath.org/sage into t/25434/pathtableaux
​29732eb	Added _an_element_
​9d3a838	Merge branch 'public/combinat/path_tableaux-25434' of git://trac.sagemath.org/sage into t/25434/pathtableaux

[tscrim]

Thank you.