Opened 4 years ago

Closed 4 years ago

#23319 closed enhancement (fixed)

Various improvements to the implementation of Fomin's growth diagrams

Reported by: mantepse Owned by:
Priority: major Milestone: sage-8.1
Component: combinatorics Keywords:
Cc: sage-combinat, tscrim, aschilling, nthiery, darij Merged in:
Authors: Martin Rubey, Travis Scrimshaw Reviewers: Martin Rubey, Travis Scrimshaw, Darij Grinberg
Report Upstream: N/A Work issues:
Branch: 43b6324 (Commits, GitHub, GitLab) Commit: 43b63242419ea06b5b5e0e3202984b84817d0dda
Dependencies: Stopgaps:

Status badges

Description (last modified by mantepse)

Implement the backward rule for Sylvester insertion on binary trees, and make the dual graded graphs accessible.

Also allow for multiple edges in the dual graded graphs, implement shifted insertion and affine insertion as examples.

Change History (119)

comment:1 Changed 4 years ago by mantepse

  • Branch set to u/mantepse/growth_diagram_improvements

comment:2 Changed 4 years ago by mantepse

  • Authors set to Martin Rubey
  • Commit set to bf1d772feb03ca80ac20a346ab4d30e7bc6214ad
  • Component changed from PLEASE CHANGE to combinatorics
  • Description modified (diff)
  • Type changed from PLEASE CHANGE to enhancement

New commits:

bf1d772add backward rule for Sylvester, add access to the graded graphs

comment:3 Changed 4 years ago by tscrim

  • Cc sage-combinat tscrim added

comment:4 Changed 4 years ago by git

  • Commit changed from bf1d772feb03ca80ac20a346ab4d30e7bc6214ad to 74260a3c644b41978f7b776a1ed66ae7e502e51c

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

6c34a9cmicro improvement to the backward rule in GrowthDiagramBinWord
74260a3add support for multiple edges, add class for shifted shapes

comment:5 Changed 4 years ago by git

  • Commit changed from 74260a3c644b41978f7b776a1ed66ae7e502e51c to 2785f3f9c21579f3b3f2368730c2ea6bda520d07

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

2785f3ffix P_chain and Q_chain for graphs with multiple edges, record disagreement in ShiftedShapes

comment:6 Changed 4 years ago by git

  • Commit changed from 2785f3f9c21579f3b3f2368730c2ea6bda520d07 to 53d37c7c8e2da60a31ae5a3892ad7f6bac1673f8

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

53d37c7lazy import shifted shapes, fix forward rule, fix tests

comment:7 Changed 4 years ago by mantepse

  • Status changed from new to needs_review

There are still some missing doctests to make the patchbot happy, which I'll provide in time, but it should be functional.

comment:8 Changed 4 years ago by git

  • Commit changed from 53d37c7c8e2da60a31ae5a3892ad7f6bac1673f8 to e96e3e153e06e0dbc7b91dfa0cf151573300fae0

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

e96e3e1fix missing DiGraph import

comment:9 Changed 4 years ago by git

  • Commit changed from e96e3e153e06e0dbc7b91dfa0cf151573300fae0 to f1ba93219afd82cbfd2328b25f127aa8fb1a3f82

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

f1ba932add backwards rules for shifted shapes

comment:10 Changed 4 years ago by mantepse

  • Description modified (diff)

comment:11 Changed 4 years ago by git

  • Commit changed from f1ba93219afd82cbfd2328b25f127aa8fb1a3f82 to 5a66779da3fd68d25ef72d15b4e551342e15eafe

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

5a66779initial version of a class for LLMS insertion

comment:12 Changed 4 years ago by git

  • Commit changed from 5a66779da3fd68d25ef72d15b4e551342e15eafe to cc4110ca181146454a2dc515f1f0788cd1aaa777

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

cc4110calmost done with LLMS insertion

comment:13 Changed 4 years ago by git

  • Commit changed from cc4110ca181146454a2dc515f1f0788cd1aaa777 to 8853225fbc39b7e42587a2aa497737c92b83b598

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

8853225fix a bug and add more (failing) tests

comment:14 Changed 4 years ago by git

  • Commit changed from 8853225fbc39b7e42587a2aa497737c92b83b598 to 995d6d63b641bbd2dba30b392c944a40f406e997

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

995d6d6fix final fehler, produce P_symbol as StrongTableau

comment:15 Changed 4 years ago by mantepse

  • Cc aschilling added

Anne, could you have a look at affine insertion? Usage:

sage: G = GrowthDiagramLLMS(3)([4,1,5,3,2])
sage: G.P_symbol().pp()
 -1 -2  3
 -3 -5
 -4  5
  5
  5
sage: G.Q_symbol().pp()
  1  3  5
  2  4
  3  5
  4
  5

comment:16 Changed 4 years ago by git

  • Commit changed from 995d6d63b641bbd2dba30b392c944a40f406e997 to 1ddf8827bab487a0cd03e1d03c0a82c621bf1d94

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

1ddf882add rank function

comment:17 Changed 4 years ago by git

  • Commit changed from 1ddf8827bab487a0cd03e1d03c0a82c621bf1d94 to 500e234c1dd8a736966b2f74fa1bf55951231789

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

500e234docfixes

comment:18 Changed 4 years ago by git

  • Commit changed from 500e234c1dd8a736966b2f74fa1bf55951231789 to 70276380b3e1692532eb7427737bcc84d4d65390

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

7027638doc fixes (in particular use the global reference file) and simplify defaults

comment:19 Changed 4 years ago by mantepse

  • Description modified (diff)

comment:20 Changed 4 years ago by git

  • Commit changed from 70276380b3e1692532eb7427737bcc84d4d65390 to a1db01517ca7fa25e448ea1f10109b455cec1098

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

a1db015make r a class attribute and implement test for Domino as an example

comment:21 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

needs documentation:

+Decreased doctests in combinat/growth.py: from 34 / 39 = 87% to 41 / 80 = 51%

comment:22 Changed 4 years ago by git

  • Commit changed from a1db01517ca7fa25e448ea1f10109b455cec1098 to 6b2a647ddef2c37478268c8fad88875799c060bc

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

1ca9e7aMerge branch 'develop' into t/23319/growth_diagram_improvements
6b2a647add documentation and doctests

comment:23 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_review

comment:24 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

+Decreased doctests in combinat/growth.py: from 34 / 39 = 87% to 68 / 80 = 85% You must reach 100%.

comment:25 Changed 4 years ago by git

  • Commit changed from 6b2a647ddef2c37478268c8fad88875799c060bc to b433c01607ddc5835a763f7852cc15b9b1a6cccb

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

b433c01provide mode doctests

comment:26 follow-up: Changed 4 years ago by mantepse

The remaining __init__ methods are all tested in the corresponding class. I don't want to provide docstrings there, because I set them using __init__.__doc__ = GrowthDiagram.__init__.__doc__.

comment:27 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_review

comment:28 in reply to: ↑ 26 Changed 4 years ago by tscrim

Replying to mantepse:

The remaining __init__ methods are all tested in the corresponding class. I don't want to provide docstrings there, because I set them using __init__.__doc__ = GrowthDiagram.__init__.__doc__.

Strong -1 on this. IMO, the __init__ should generally be a short docstring to begin with (the main doc with inputs, etc. should (generally) be at the class-level). It is basically hidden from the user and the public API. Also, the __init__ is a good place to put a TestSuite test. I wasn't paying attention with the first implementation and should have mentioned it then.

I am willing to let this in with that because it was done previously, but I dislike it.

comment:29 Changed 4 years ago by mantepse

I actually asked back then, and was told to do it this way. I'm happy to do it differently, because the current setup does not work.

Please keep in mind that I took great care that new variants of growth diagrams are as easy to implement as possible. For example, the following is enough for many purposes - ideally, hitting GrowthMinimal? should even display most of the generic documentation!

sage: from sage.combinat.growth import GrowthDiagram
sage: class GrowthMinimal(GrowthDiagram):
....:     _zero = 0
....:     _rank_function = lambda self,x: x
....:     _backward_rule = lambda self,y,z,x: (min(x,y), 0 if y==z or x==z else 1)
sage: GrowthMinimal(labels=[0,1,2,1,2,1,0]) # indirect doctest
1  0  0
0  0  1
0  1

Here is what I want to achieve:

  • I want identical text describing input and output for all classes inheriting from GrowthDiagram. That's important, because the whole point of the thing is a common interface. I only want to provide this text once: somewhere in the class GrowthDiagram.
  • additionally, I want some text that describes the inheriting class. In particular, this is also the natural place to describe the objects involved and references for the insertion algorithm - not necessarily the growth diagram version.
  • additionally, I want to display the docstring of some other methods, like _forward_rule and _backward_rule (these are the natural places to put the reference for the forward and backward rule).

Thus, when I write GrowthDiagramBinWord?, I want to see all of the above.

Currently, the generic docstring is not displayed at all!

comment:30 Changed 4 years ago by mantepse

On the lighter side, the following makes me smile:

+Decreased doctests in combinat/growth.py: from 34 / 39 = 87% to 73 / 80 = 91%
+Coverage went from 43573 / 45276 = 96.239% to 43612 / 45317 = 96.238%

comment:31 Changed 4 years ago by mantepse

I think I found a good pattern. Is the following acceptable to you? With this I get the complete doc for Instance1? whereas Instance2? shows the generic doc and the hints. What I couldn't find out is how to include the doc from, say, _forward_rule automatically yet. Instance3? shows the hints twice, but that's OK...

class Generic(SageObject):
    """
    Initialise a generalized Schensted growth diagram ...

    INPUT:
    - ``filling``
    ...
    """
    def __init__(self):
        """
        Hints for implementing your own class
        """
        pass

class Instance1(Generic):
    __doc__ = Generic.__doc__
    def __init__(self):
        """
        This is the greatest growth diagram ever
        """
        pass
    def _forward_rule(self, a,b,c):
        """
        Euler invented it
        """
        pass

class Instance2(Generic):
    __doc__ = Generic.__doc__

class Instance3(Generic):
    pass

comment:32 Changed 4 years ago by tscrim

I think what you want is impossible with the current capabilities of Sphinx. I think you should rewrite the inputs for each function type as they are essentially different. If they really should be the same interface and delegate, you should have one entry point and all of the requisite documentation there. I feel more like you want to have something that references the base class more than that entire documentation and almost certainly the generic documentation is too generic (maybe even better as a thematic tutorial or a de facto tutorial by being at the module-level documentation).

As for including the documentation of the other methods, you could just do __doc__ += method.__doc__. That is good with me as you are adding additional information. You could also do a decorator, but that feels like overkill. Actually, for some of what you want, the main documentation about things like _forward_rule should be in the class-level doc and _forward_rule doc should be

def _forward_rule(self):
    """
    Apply the forward rule.

    See :class:`GrowthDiagram` for a precise description.
    """

I suggest this because the method is private and never viewable from a user perspective.

comment:33 follow-up: Changed 4 years ago by tscrim

I am even more against comment:31 because then you lose the locality of the documentation.

comment:34 in reply to: ↑ 33 ; follow-up: Changed 4 years ago by mantepse

Replying to tscrim:

I am even more against comment:31 because then you lose the locality of the documentation.

I am quite sure that you misread my proposal - I actually tried it and it works beautifully!

In particular, I do achieve locality of documentation - after all, that's why I am trying so hard.

In particular, I certainly do not want to put the reference for the forward rule into the main documentation - but of course I want it visible! In several classes we have:

  • insertion algorithm, discovered by S in 1961
  • local rule, described by F in 1995

When implementing or debugging the local rule, you want to look how it is defined mathematically, so the reference and description should be in the docstring of _forward_rule! It would be terrible to have it in the class docstring, then you would have to scroll back and forth all the time.

So the natural thing is to append the doc of _forward_rule automatically to the main documentation. I thought that .. automethod: would do this, but it doesn't.

comment:35 in reply to: ↑ 34 ; follow-up: Changed 4 years ago by tscrim

Replying to mantepse:

Replying to tscrim:

I am even more against comment:31 because then you lose the locality of the documentation.

I am quite sure that you misread my proposal - I actually tried it and it works beautifully!

No, I read it correctly. I am very strongly opposed to it.

In particular, I do achieve locality of documentation - after all, that's why I am trying so hard.

No, you do not. Everything is defined/described in the generic class, which is not what you want. You want things connected with each class. Otherwise, if you feel the doc needs to be consolidated, then that is a very strong code smell that the design is wrong.

In particular, I certainly do not want to put the reference for the forward rule into the main documentation - but of course I want it visible!

You are basically telling me you want two mutually exclusive things: You want it documented but you don't.

In several classes we have:

  • insertion algorithm, discovered by S in 1961
  • local rule, described by F in 1995

When implementing or debugging the local rule, you want to look how it is defined mathematically, so the reference and description should be in the docstring of _forward_rule! It would be terrible to have it in the class docstring, then you would have to scroll back and forth all the time.

Have multiple windows open of the file. Have one be the html and the other be the text editor. Copy in the rule right where you need it. These are all easy ways to get around that if that is ever a problem that you couldn't remember the rule while working on it.

So the natural thing is to append the doc of _forward_rule automatically to the main documentation. I thought that .. automethod: would do this, but it doesn't.

I disagree if you feel that it should be described at the class-level. Either copy the rule description or just have it at the class-level. The other way is to make _forward_rule public (i.e., forward_rule).

comment:36 in reply to: ↑ 35 ; follow-up: Changed 4 years ago by mantepse

Let me first repeat that my framework serves two purposes:

  1. easy to use
  2. easy to extend, even interactively.

Since the definitions involve quite a few conventions, I want that the user sees them when writing his new class. And no, opening a second window is not an option for this.

No, I read it correctly. I am very strongly opposed to it.

In particular, I do achieve locality of documentation - after all, that's why I am trying so hard.

No, you do not. Everything is defined/described in the generic class, which is not what you want.

I am actually not saying that. Only those things which must not be changed in inherited classes without destroying the framework. In particular, input and output.

In particular, I certainly do not want to put the reference for the forward rule into the main documentation - but of course I want it visible!

You are basically telling me you want two mutually exclusive things: You want it documented but you don't.

Apparently, I miscommunicated. I want it documented at that place where the documentation is needed.

I disagree if you feel that it should be described at the class-level. Either copy the rule description or just have it at the class-level. The other way is to make _forward_rule public (i.e., forward_rule).

Yes, I'll do that.

comment:37 in reply to: ↑ 36 ; follow-up: Changed 4 years ago by tscrim

Replying to mantepse:

Let me first repeat that my framework serves two purposes:

  1. easy to use
  2. easy to extend, even interactively.

Since the definitions involve quite a few conventions, I want that the user sees them when writing his new class.

Define what you mean by "extending interactively". Subclasses, passing local rules as input, or something else?

And no, opening a second window is not an option for this.

Why not? In fact, your proposal makes things harder without a second window for someone doing development because there is no documentation there with other classes or the class you are writing.

I feel like you are either being too precious or you have a code smell.

No, I read it correctly. I am very strongly opposed to it.

In particular, I do achieve locality of documentation - after all, that's why I am trying so hard.

No, you do not. Everything is defined/described in the generic class, which is not what you want.

I am actually not saying that. Only those things which must not be changed in inherited classes without destroying the framework. In particular, input and output.

That is what your proposal in comment:31 is doing and what I am saying that is not what you want to do. The __init__ is never visible (unless you are looking at the code). Because they are different classes, they can have different inputs. Hence, you need to copy the input as a way to state they have the same input. There is no output for creating a class. Also, there is no restriction (nor should there be) that all subclasses take the same inputs.

In particular, I certainly do not want to put the reference for the forward rule into the main documentation - but of course I want it visible!

You are basically telling me you want two mutually exclusive things: You want it documented but you don't.

Apparently, I miscommunicated. I want it documented at that place where the documentation is needed.

Which is where?

I disagree if you feel that it should be described at the class-level. Either copy the rule description or just have it at the class-level. The other way is to make _forward_rule public (i.e., forward_rule).

Yes, I'll do that.

Do you want the user to be able to call forward_rule?

comment:38 in reply to: ↑ 37 ; follow-up: Changed 4 years ago by mantepse

I feel like you are either being too precious or you have a code smell.

Don't know what either of this means (probably because English is my second language).

Define what you mean by "extending interactively". Subclasses, passing local rules as input, or something else?

Subclassing the generic class (as in the example above, I am currently writing a better example into the documentation)

No, you do not. Everything is defined/described in the generic class, which is not what you want.

I am actually not saying that. Only those things which must not be changed in inherited classes without destroying the framework. In particular, input and output.

That is what your proposal in comment:31 is doing and what I am saying that is not what you want to do. The __init__ is never visible (unless you are looking at the code).

On my computer, the docstring of __init__ becomes visible when I do Instance2?.

Because they are different classes, they can have different inputs.

NO NO NO! The point of the framework is that the input is always the same! It allows for extension, but not deviation!

Apparently, I miscommunicated. I want it documented at that place where the documentation is needed.

Which is where?

in the docstring of _forward_rule: for all of the dozen classes I wrote, I needed the docstring, because in every article the conventions differ.

I disagree if you feel that it should be described at the class-level. Either copy the rule description or just have it at the class-level. The other way is to make _forward_rule public (i.e., forward_rule).

Yes, I'll do that.

Do you want the user to be able to call forward_rule?

It might be useful in very rare cases (debugging or trying to find out why the algorithm works, for example).

And no, opening a second window is not an option for this.

Why not?

I was imprecise: searching for the code in another window is not an option, that's what we have ? for. When I have provided a partial implementation of a new growth diagram, I already want that the doc for input and output is already there, and I want to have the implementation hints for the stuff I haven't provided yet.

Last edited 4 years ago by mantepse (previous) (diff)

comment:39 Changed 4 years ago by git

  • Commit changed from b433c01607ddc5835a763f7852cc15b9b1a6cccb to 16ffc0c93b9c7604c66472f2f292df5426afe4a7

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

16ffc0cimprove module documentation

comment:40 Changed 4 years ago by mantepse

That is what your proposal in comment:31 is doing and what I am saying that is not what you want to do. The __init__ is never visible (unless you are looking at the code).

On my computer, the docstring of __init__ becomes visible when I do Instance2?.

I just found out that this does not happen if the class is lazily imported. How come?

comment:41 Changed 4 years ago by git

  • Commit changed from 16ffc0c93b9c7604c66472f2f292df5426afe4a7 to 81a5156997d01d87c7f98d66f54be325fc3f3bdc

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

81a5156make many methods public, fix literal block bug

comment:42 Changed 4 years ago by git

  • Commit changed from 81a5156997d01d87c7f98d66f54be325fc3f3bdc to c4e696f990561c6dad8d8837b89bc3e26d219f64

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

c4e696ffix documentation explaining which methods to provide

comment:43 in reply to: ↑ 38 ; follow-up: Changed 4 years ago by tscrim

  • Status changed from needs_review to needs_work

Replying to mantepse:

I feel like you are either being too precious or you have a code smell.

Don't know what either of this means (probably because English is my second language).

precious = you are too concerned with making it elegant or a certain way code smell = indication of a deeper problem (https://en.wikipedia.org/wiki/Code_smell)

Actually, I am now convinced that it is a code smell coming from a bad design choice.

No, you do not. Everything is defined/described in the generic class, which is not what you want.

I am actually not saying that. Only those things which must not be changed in inherited classes without destroying the framework. In particular, input and output.

That is what your proposal in comment:31 is doing and what I am saying that is not what you want to do. The __init__ is never visible (unless you are looking at the code).

On my computer, the docstring of __init__ becomes visible when I do Instance2?.

It does not appear in the online documentation. However, you are right and it does appear at the bottom (which I am slightly inclined to say it should not, but that is a different issue), which I never noticed. Yet, I say that documentation should not be considered as part of the public API as it does not appear in the built documentation and all other special Python methods are not visible.

Because they are different classes, they can have different inputs.

NO NO NO! The point of the framework is that the input is always the same! It allows for extension, but not deviation!

Let me be clear, you can not and should not enforce this on any subclass. The input for any subclass can be whatever that subclass wants because it might know better or want to force values for the base class. The moment you want to enforce subclasses to have the same input, you need a different design than subclasses.

Actually, everything you have been telling me what you want a class that takes an "rule" class/function that it uses. (This is called a strategy design pattern.) This (or some close variant) is what we should actually implement.

Apparently, I miscommunicated. I want it documented at that place where the documentation is needed.

Which is where?

in the docstring of _forward_rule: for all of the dozen classes I wrote, I needed the docstring, because in every article the conventions differ.

This is the only real difference, not the classes. This is where the code smell is coming from.

I disagree if you feel that it should be described at the class-level. Either copy the rule description or just have it at the class-level. The other way is to make _forward_rule public (i.e., forward_rule).

Yes, I'll do that.

Do you want the user to be able to call forward_rule?

It might be useful in very rare cases (debugging or trying to find out why the algorithm works, for example).

If someone is doing either of those things, then they are looking at the code and know they can call hidden methods. It sounds like it should not be public as it is an implementation detail.

And no, opening a second window is not an option for this.

Why not?

I was imprecise: searching for the code in another window is not an option, that's what we have ? for. When I have provided a partial implementation of a new growth diagram, I already want that the doc for input and output is already there, and I want to have the implementation hints for the stuff I haven't provided yet.

It should be clear that you are doing something wrong. It is a new class, and so it should have new documentation. However, what you are trying to do is say it is not a new class, but a new rule, which should not be a class.

I will sit down and rework this later today because it needs to be done. The current approach does not scale.

comment:44 Changed 4 years ago by git

  • Commit changed from c4e696f990561c6dad8d8837b89bc3e26d219f64 to 82080d6effdfba93ea1de01dfc2065ad0d24bbbf

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

82080d6make more of the doc for Domino insertion public

comment:45 in reply to: ↑ 43 Changed 4 years ago by mantepse

Travis, please be careful! I worked a lot with this class (both for fun and for research), and I tried several approaches. In particular, at first I had a class whose init method would take the various rules as named arguments. This was terrible to work with, it encouraged a really bad style of writing. Of course, easy growth diagrams work well, but for something like GrowthDiagramLLMS it just didn't feel right.

I have now implemented 10 classes, at various stages. The last few indicated that the current pattern works - at least for me.

I am open for an improvement, but I am anxious that it looks great at first and then doesn't do so well. So, if you change the pattern completely, maybe you could do it on a separate ticket? I promise to consider it with an open mind!

Other comments:

  • I decided to make forward_rule a public method - it turns out that I simply didn't notice how often I used it for checking things in papers or my work. (Possibly I miscommunicated: with "trying to find out how the algorithm works" I did not refer to my implementation but to the mathematics.)
  • Concerning

    It should be clear that you are doing something wrong. It is a new class, and so it should have new documentation. However, what you are trying to do is say it is not a new class, but a new rule, which should not be a class.

I hope it's clear that not only the rules should carry documentation - there also is need for documentation of the class. I admit I have not provided as much documentation as might be desirable, but the doc of GrowthDiagramDomino might give a good impression.


New commits:

82080d6make more of the doc for Domino insertion public

comment:46 Changed 4 years ago by mantepse

In case you want an example to work with, you could implement the forward rule on from section 3 of https://arxiv.org/pdf/1103.0319.pdf (Bloom and Saracino) It is a straightforward modification of the classical rule for Schensted insertion.

Note that this rule is not invertible, so some things cannot work. But that should certainly not be an obstacle to play with it!

comment:47 Changed 4 years ago by git

  • Commit changed from 82080d6effdfba93ea1de01dfc2065ad0d24bbbf to f8dd0ca5bbf7d552ebb3bcf1f8960fbafce4db58

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

f8dd0caMerge branch 'develop' into t/23319/growth_diagram_improvements

comment:48 Changed 4 years ago by git

  • Commit changed from f8dd0ca5bbf7d552ebb3bcf1f8960fbafce4db58 to 36b2889e5f55c9d14abd0c538995a54eca9faae8

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

36b2889improve documentation, better design for default is_P_edge, is_Q_edge

comment:49 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_review

Travis, I took some care that the documentation works now, both in the html version and interactively.

Since the current version is a huge improvement over what's in sage currently, could you have another look whether it's at least "OK"? Again, I promise to test your idea, too.

comment:50 follow-up: Changed 4 years ago by tscrim

  • Branch changed from u/mantepse/growth_diagram_improvements to public/combinat/improve_growth_diagrams-23319
  • Commit changed from 36b2889e5f55c9d14abd0c538995a54eca9faae8 to a6e1c0ae1a170c79829b89a6ff8dfd1dbb1ce5d7
  • Status changed from needs_review to needs_work

It is not the way forward and makes clear that there are major flaws in the code. It also does not conform the code standards for Sage such as the documentation coverage. So I do not believe this should be given a positive review.

However, I did finish a mostly proof-of-concept of the way I feel things should be done. It has several advantages and I believe satisfies all of your requirements:

  • There is only one class for growth diagrams, which differ only based upon the rule given. They are all the same data structure, so it makes more sense to have the same class.
  • Documentation and code for each of the rules is local to each rule.
  • Documentation and methods that pertains to the growth diagram can be separate from that for the rules. So there is a clear separation of concerns.
  • There is clear information about the possible rules and accessing their documentation interactively is easy.
  • It is easy to extend.

There is one clear downside: You do have to type a little bit more because you have to keep the rule objects around. However, we can have an inject_rules() function or something like that to make life a little easier if you feel it is necessary.

There are still a few things that need to be done because I didn't know what the best place to put them was (and I'm tired now). In particular, should P/Q_symbol be associated to the rule or the growth diagram or both, as well as for _check_duality. Let me know what you think.


New commits:

9d8d5b9Merge branch 'develop' into public/combinat/improve_growth_diagrams-23319
01723a1Some PEP8 and other trivial cleanup.
867ef32Merge branch 'u/mantepse/growth_diagram_improvements' of git://trac.sagemath.org/sage into public/combinat/improve_growth_diagrams-23319
a6e1c0aInplement growth diagrams by using Rule (sub)classes.

comment:51 Changed 4 years ago by mantepse

I like most of this. I didn't think of the possibility to pass the things specific to a growth as a class. So, the one thing I absolutely dislike is

        sage: Domino = GrowthDiagram.rules.Domino()
        sage: G = GrowthDiagram(Domino, [[0,0,0,-1],[0,0,1,0],[-1,0,0,0],[0,1,0,0]]); G

Since one usually works only with one specific rule, the invocation should be GrowDomino([[0,0,0,-1],[0,0,1,0],[-1,0,0,0],[0,1,0,0]]).

I'll have to play a little.

comment:52 in reply to: ↑ 50 ; follow-up: Changed 4 years ago by mantepse

I think your proposal is good - the one issue mentioned above is certainly no obstruction. BUT:

Replying to tscrim:

It is not the way forward and makes clear that there are major flaws in the code.

I must say that it is not nice to read this.

It also does not conform the code standards for Sage such as the documentation coverage.

That's also a bit strange, because it suggests that my package is badly documented, which is certainly not the case.

Back to technical stuff:

There are still a few things that need to be done because I didn't know what the best place to put them was (and I'm tired now). In particular, should P/Q_symbol be associated to the rule or the growth diagram or both, as well as for _check_duality. Let me know what you think.

P_symbol should be accessible just as P_chain. The reason it does not exist for all rules is that often there is no special object for it, so the implementation must always be in the rule.

_check_duality is only interesting when implementing the rule. In fact, there may be several interesting local rules for the same pair of dual graded graphs, it only depends on is_P_edge and is_Q_edge.

normalize_labels should certainly have a default implementation.

Does this answer your questions?

Minor thing, in Rule:

All subclasses must provide the following methods:

should be

All subclasses should provide the following methods:

because it is important that the thing also works (as much as possible) with a partial implementation, and, more importantly, it is important to cover situations which do not quite fit the framework (eg., RSK).

comment:53 in reply to: ↑ 52 Changed 4 years ago by tscrim

Replying to mantepse:

I think your proposal is good - the one issue mentioned above is certainly no obstruction. BUT:

Replying to tscrim:

It is not the way forward and makes clear that there are major flaws in the code.

I must say that it is not nice to read this.

I should first apologize as my wording is misleading. I should have said in the code design. It is not my intention to offend you, and I am sorry if I have. I have written poorly designed code (which I had thought was good or necessary), and I will also write more in the future. I appreciate the code that you have added as it does improve Sage's capabilities and works quite well, and you are.

It also does not conform the code standards for Sage such as the documentation coverage.

That's also a bit strange, because it suggests that my package is badly documented, which is certainly not the case.

I do not mean to imply that it was badly documented, but it was lacking good documentation and tests in places.

Back to technical stuff:

There are still a few things that need to be done because I didn't know what the best place to put them was (and I'm tired now). In particular, should P/Q_symbol be associated to the rule or the growth diagram or both, as well as for _check_duality. Let me know what you think.

P_symbol should be accessible just as P_chain. The reason it does not exist for all rules is that often there is no special object for it, so the implementation must always be in the rule.

I will have the GrowthDiagram.P_symbol call rule.P_symbol.

_check_duality is only interesting when implementing the rule. In fact, there may be several interesting local rules for the same pair of dual graded graphs, it only depends on is_P_edge and is_Q_edge.

Okay, this is something that should be done at the Rule level.

normalize_labels should certainly have a default implementation.

Just to return the original labels? Every one of your implementations needed to normalize the labels.

Does this answer your questions?

Yes, thank you.

Minor thing, in Rule:

All subclasses must provide the following methods:

should be

All subclasses should provide the following methods:

because it is important that the thing also works (as much as possible) with a partial implementation, and, more importantly, it is important to cover situations which do not quite fit the framework (eg., RSK).

Are the optional or mandatory? Your documentation suggests more that they are all mandatory. What methods are needed (for what functionality) and which are recommended?

As for comment:51, you only need to create the rule once (which you can give a single letter variable). Because of the nature of doctests, we create a lot more of the rule instance than would be necessary in a session.

comment:54 Changed 4 years ago by git

  • Commit changed from a6e1c0ae1a170c79829b89a6ff8dfd1dbb1ce5d7 to 853474d31a46dfb5106353d3268e7e20225bad1b

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

853474dadapt to new system

comment:55 Changed 4 years ago by git

  • Commit changed from 853474d31a46dfb5106353d3268e7e20225bad1b to 112c8ba0977e4b86f3d27bfa50b65b99a77fdde8

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

112c8bamake Rule callable

comment:56 Changed 4 years ago by mantepse

I simply made Rule callable, now we are back to what we had. To avoid the deprecation, we can simply define GrowthDiagramRSK etc. Is this OK?

sage: RuleRSK = GrowthDiagram.rules.RSK()
sage: RuleRSK([1,3,2])

  1  0  0
  0  0  1
  0  1  0

sage: RuleRSK(labels = [[], [1], [2], [2, 1], [2], [1], []])

  1  0  0
  0  0  1
  0  1  0

comment:57 Changed 4 years ago by tscrim

Having RuleFoo(bar) is a nice shorthand; good suggestion. I know you are not currently saying this, but I think we should not advertise it as the primary method to use the growth diagrams (that's not to say we should not put it in the doc).

I feel like we should deprecate GrowthDiagramRSK in order to not pollute the global namespace and promote more of a single entry point (GrowthDiagram). Although because everything starts with GrowthDiagram* (and because you have been nice and accommodated me), if you strongly feel like we should not deprecate it, then I will not object. Yet, the GrowthDiagram.rules.* basically is the new way to call it because of the above shorthand and you can always define these aliases in your init.sage if you prefer using them, so there is good reason to deprecate GrowthDiagram*.

comment:58 follow-up: Changed 4 years ago by mantepse

  • it's OK for me to deprecate the old entry points. In analogy to crystals, should we use lower case for the main entry point?
  • I actually would advertise the following usage, why not?
    sage: RuleRSK = GrowthDiagram.rules.RSK() # I'd prefer growthdiagrams.RSK() in fact
    sage: w = [2,3,6,1,4,5]; G = RuleRSK(w); G
    
      0  0  0  1  0  0
      1  0  0  0  0  0
      0  1  0  0  0  0
      0  0  0  0  1  0
      0  0  0  0  0  1
      0  0  1  0  0  0
    

comment:59 Changed 4 years ago by mantepse

Question: given

    sage: class RulePascal(Rule):
    ....:     zero = 0
    ....:     def rank_function(self, x): return x
    ....:     def backward_rule(self, y, z, x): return (min(x,y), 0 if y==z or x==z else 1)

What does RulePascal(labels=[0,1,2,1,2,1,0]) invoke? Currently, it raises a TypeError.

EDIT: it calls __init__, of course...

Last edited 4 years ago by mantepse (previous) (diff)

comment:60 Changed 4 years ago by git

  • Commit changed from 112c8ba0977e4b86f3d27bfa50b65b99a77fdde8 to f473f73457e6b535651b1c238d0313f7ce1119a2

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

f473f73fix documentation coverage and be consistent, replace normalize_labels with normalize_vertex

comment:61 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_review
Last edited 4 years ago by mantepse (previous) (diff)

comment:62 follow-up: Changed 4 years ago by mantepse

  • once comment:58 is adressed, I'd like to be consistent with this in the documentation - I won't insist, but I think BinWord(labels=[0,1,2,1,2,1,0]) is much better than GrowthDiagram(BinWord, labels=[0,1,2,1,2,1,0]).
  • I wouldn't know how to do the deprecation, so I'd ask the reviewer to do it.

comment:63 Changed 4 years ago by git

  • Commit changed from f473f73457e6b535651b1c238d0313f7ce1119a2 to 38244e34b7c6f4305b2c727a52f079544a362334

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

38244e3rename rank_function to rank

comment:64 in reply to: ↑ 62 ; follow-up: Changed 4 years ago by tscrim

Replying to mantepse:

  • once comment:58 is adressed, I'd like to be consistent with this in the documentation - I won't insist, but I think BinWord(labels=[0,1,2,1,2,1,0]) is much better than GrowthDiagram(BinWord, labels=[0,1,2,1,2,1,0]).

I disagree because I feel it violates the principle of least surprise.

  • I wouldn't know how to do the deprecation, so I'd ask the reviewer to do it.

There are many examples within Sage, but I do not mind doing it.

comment:65 in reply to: ↑ 58 Changed 4 years ago by tscrim

Replying to mantepse:

  • it's OK for me to deprecate the old entry points. In analogy to crystals, should we use lower case for the main entry point?

No, because the class GrowthDiagram is the main entry point, whereas crystals is a catalog module.

  • I actually would advertise the following usage, why not?
    sage: RuleRSK = GrowthDiagram.rules.RSK() # I'd prefer growthdiagrams.RSK() in fact
    sage: w = [2,3,6,1,4,5]; G = RuleRSK(w); G
    
      0  0  0  1  0  0
      1  0  0  0  0  0
      0  1  0  0  0  0
      0  0  0  0  1  0
      0  0  0  0  0  1
      0  0  1  0  0  0
    

+1 As I mentioned above, I completely agree that we should advertise it as a shorthand method to constructing growth diagrams. However, because of the proposed framework and to be more explicit about what objects are, I do not like growth_diagrams.RSK().

comment:66 in reply to: ↑ 64 ; follow-up: Changed 4 years ago by mantepse

(I don't mind much keeping GrowthDiagram.rules.RSK(), although I do not understand the reason you gave - it seems to me that the difference between crystals and GrowthDiagram is an implementation detail.)

Replying to tscrim:

Replying to mantepse:

  • once comment:58 is adressed, I'd like to be consistent with this in the documentation - I won't insist, but I think BinWord(labels=[0,1,2,1,2,1,0]) is much better than GrowthDiagram(BinWord, labels=[0,1,2,1,2,1,0]).

I disagree because I feel it violates the principle of least surprise.

I do not understand at all. What is surprising about

sage: RSKGrowth = GrowthDiagram.rules.RSK()
sage: RSKGrowth([2,3,1], shape=[3,2,2])
0  0  1
1  0
0  1

in contrast to the following?

sage: RSKGrowth = GrowthDiagram.rules.RSK()
sage: GrowthDiagram(RSKGrowth, labels=[[], [1], [2], [1], [], [1], []])
0  0  1
1  0
0  1

I find the former actually (slightly) less surprising. In fact, since I use

sage: posets.ChainPoset(4)
Finite lattice containing 4 elements
sage: crystals.Letters("A1")
The crystal of letters for type ['A', 1]
sage: groups.permutation.KleinFour()
The Klein 4 group of order 4, as a permutation group

I'd actually expect growthdiagrams.RSK() - we are providing a catalogue of growth diagrams, aren't we?

  • I wouldn't know how to do the deprecation, so I'd ask the reviewer to do it.

There are many examples within Sage, but I do not mind doing it.

So, what do we have to deprecate? Should I try to run all the old doctests and provide redirections?

comment:67 in reply to: ↑ 66 Changed 4 years ago by tscrim

Replying to mantepse:

(I don't mind much keeping GrowthDiagram.rules.RSK(), although I do not understand the reason you gave - it seems to me that the difference between crystals and GrowthDiagram is an implementation detail.)

It's not a detail, it is the whole thing. They are completely different implementations.

Replying to tscrim:

Replying to mantepse:

  • once comment:58 is adressed, I'd like to be consistent with this in the documentation - I won't insist, but I think BinWord(labels=[0,1,2,1,2,1,0]) is much better than GrowthDiagram(BinWord, labels=[0,1,2,1,2,1,0]).

I disagree because I feel it violates the principle of least surprise.

I do not understand at all. What is surprising about

sage: RSKGrowth = GrowthDiagram.rules.RSK()
sage: RSKGrowth([2,3,1], shape=[3,2,2])
0  0  1
1  0
0  1

in contrast to the following?

sage: RSKGrowth = GrowthDiagram.rules.RSK()
sage: GrowthDiagram(RSKGrowth, labels=[[], [1], [2], [1], [], [1], []])
0  0  1
1  0
0  1

I find the former actually (slightly) less surprising.

The former is a rule for a growth diagram, not a growth diagram. So why would it return a growth diagram? In addition, the entry point for growth diagrams is suppose to be the class GrowthDiagram.

In fact, since I use

sage: posets.ChainPoset(4)
Finite lattice containing 4 elements
sage: crystals.Letters("A1")
The crystal of letters for type ['A', 1]
sage: groups.permutation.KleinFour()
The Klein 4 group of order 4, as a permutation group

I'd actually expect growthdiagrams.RSK() - we are providing a catalogue of growth diagrams, aren't we?

We are not. We are providing a catalog of rules to pass to GrowthDiagram.

If you do a catalog of growth diagrams, then you run right back into most of the same problems that were there before with code/doc locality and separation of concerns. At least, in that argument, doesn't make sense why there should be a separate Rule and GrowthDiagram class and as I would have the old subclass design. While that could be an improvement over what we currently have in Sage (and was something Anne had suggested to me when we talked briefly about this ticket), it mixes two essentially separate things as growth diagrams are one data structure that uses rules, which gives the growing behavior.

  • I wouldn't know how to do the deprecation, so I'd ask the reviewer to do it.

There are many examples within Sage, but I do not mind doing it.

So, what do we have to deprecate? Should I try to run all the old doctests and provide redirections?

I guess this is a little more complicated. So what we should do is have a function like

def GrowthDiagramRSK(filling=None, shape=None, labels=None):
    from sage.misc.superseed import deprecation
    deprecation(23319, "GrowthDiagramRSK is deprecated; use GrowthDiagram with the RSK rule instead")
    return GrowthDiagram(RuleRSK(), filling, shape, labels)

comment:68 follow-up: Changed 4 years ago by mantepse

OK. Hopefully final question:

If I understand correctly, you want to remind the user that she is passing a rule to the GrowthDiagram class. Since I am mainly a user, I will go with your opinion even though I do not understand it.

However, I think it makes sense to use the shorthand X = GrowthDiagram.rules.RSK(); X([1,3,2]) in the tutorial at the beginning and in the individual rule classes.

On the other hand, I'd use the long form GrowthDiagram(X, [1,3,2]) in the doc of the GrowthDiagram class.

So, when advertising the shorthand, how should we call the reference to the rule:

sage: RSKGrowth = GrowthDiagram.rules.RSK(); RSKGrowth([1,3,2])
sage: RSKRule = GrowthDiagram.rules.RSK(); RSKRule([1,3,2])

(I think it's important to use good names for variables in a tutorial, to get the right mindset across ... although I admit that the difference here is perhaps marginal.)

PS: it's nice to hear that you talked with Anne about the package. I hope she likes it! Please let her know that I can't wait for #20041 and #22921 :-)

comment:69 in reply to: ↑ 68 ; follow-up: Changed 4 years ago by tscrim

Replying to mantepse:

If I understand correctly, you want to remind the user that she is passing a rule to the GrowthDiagram class. Since I am mainly a user, I will go with your opinion even though I do not understand it.

Thank you.

However, I think it makes sense to use the shorthand X = GrowthDiagram.rules.RSK(); X([1,3,2]) in the tutorial at the beginning and in the individual rule classes.

I would say it should come at the end of the tutorial only as it is a shorthand, but if you want to include it after the main way, then I probably will not object.

So, when advertising the shorthand, how should we call the reference to the rule:

sage: RSKGrowth = GrowthDiagram.rules.RSK(); RSKGrowth([1,3,2])
sage: RSKRule = GrowthDiagram.rules.RSK(); RSKRule([1,3,2])

(I think it's important to use good names for variables in a tutorial, to get the right mindset across ... although I admit that the difference here is perhaps marginal.)

Clearly the latter as the former is misleading at best. It is the rule for the growth diagram, the latter suggests that it is a growth diagram.

PS: it's nice to hear that you talked with Anne about the package. I hope she likes it! Please let her know that I can't wait for #20041 and #22921 :-)

From my conversion with her, it seems like we will have to get those tickets done in order to get them into Sage. I hope to find some time to do that, but I have a few higher priority things to do first. :/

comment:70 in reply to: ↑ 69 ; follow-up: Changed 4 years ago by aschilling

I did not read your entire discussion as it is pretty long and I am currently short on time. But here was my suggestion: use the category framework and have the generic code for GrowthDiagrams? in a category. Then for each implemented rule, you can have a class, where the specific rule is implemented. The syntax would be

    sage: grow_diagram.RSK(input)

The catalogue of rules and implementation would be at grow_diagram. See for example

    sage: crystals.Tableaux??

There is a category for crystals and each model has each own class.

Just an idea ....

comment:71 in reply to: ↑ 70 Changed 4 years ago by mantepse

Hi Anne!

    sage: grow_diagram.RSK(input)

I agree that I would find this more natural, but if I understand correctly, Travis doesn't. Since the ticket is mostly finished now, and usable, and I would like to move on, I'd rather go with what we have now...

comment:72 Changed 4 years ago by git

  • Commit changed from 38244e34b7c6f4305b2c727a52f079544a362334 to 9d7750f1b24bc59f39469d985032a8d0cccf1f4f

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

9d7750fdeprecate old access points, improve doc, be consistent with variable names, be consistent with calling convention

comment:73 Changed 4 years ago by mantepse

I am done. In particular:

  • I ran the doctests of the old version currently in sage. All of these tests pass (when switching off the DeprecationWarning), except for those where the method was underscored and is public now, and some very minor punctuation differences in exception tests.
  • I built and partially proofread the html documentation, checked some links, etc.

I ask for positive review :-)

Last edited 4 years ago by mantepse (previous) (diff)

comment:74 Changed 4 years ago by git

  • Commit changed from 9d7750f1b24bc59f39469d985032a8d0cccf1f4f to 51e5fabd49db60d341964deb5c3f974a35e40c93

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

51e5fabSome documentation changes and other small tweaks.

comment:75 follow-up: Changed 4 years ago by tscrim

I made a few additional documentation changes and additions, along with a few other small changes to avoid assert to validation user input (I've been told to reserve that for true bugs in the code).

Minor thing, in Rule:

    All subclasses must provide the following methods:

should be

    All subclasses should provide the following methods:

because it is important that the thing also works (as much as possible) with a partial implementation, and, more importantly, it is important to cover situations which do not quite fit the framework (eg., RSK).

Are the optional or mandatory? Your documentation suggests more that they are all mandatory. What methods are needed (for what functionality) and which are recommended?

This is the only outstanding issue. This is the thing that needs more documentation, and I do not feel I understand the code enough to do it to the precision you want.

comment:76 follow-up: Changed 4 years ago by mantepse

Travis, some of your documentation changes make me very unhappy. Some changes in the code make me unhappy.

  1. I took great care to strike a balance between the shorthand and GrowthDiagram(Rule, stuff). I feel ignored here. Although there are some cases where one may want to use different rules, most of the time there is only one rule around. This is also visible from Anne's comment. Please revert this.
  1. The point of the RulePascal example in the tutorial is now completely destroyed. Please revert this, too.
  1. The docstring template for the forward rule is there for a reason - it tells you the conventions at a glance. Please leave this in. Alternatively, provide an abstract method with this docstring, and doctest it with help(RulePascal.forward_rule) at this point.
  1. rather minor: I learned in school that, when writing English, sentences (and half-sentences) after a colon start in lowercase - has this changed?
  1. in the deprecation warnings, I took care to point the reader directly to the new entry point. While a minor issue, use GrowthDiagram with the YoungFibonacci rule instead is not really helpful.

comment:75 possibly explains the problem with the second point above. I hope I pointed out that RuleRSK is not a pair of local rules in the sense of Fomin. Still, the framework is useful. Even more explicitly, the first RulePascal example shows that the framework is useful even if the forward rule is not invertible! (I am not making this up, see https://arxiv.org/pdf/1103.0319.pdf by Bloom and Saracino)

comment:77 Changed 4 years ago by mantepse

  • Status changed from needs_review to needs_work

comment:78 follow-up: Changed 4 years ago by mantepse

I just see that I should take back item 2 in comment:76 - I didn't see from the commit that you incrementally add to the minimal implementation. Please excuse.

My original intention was to stress that one can implement a growth diagram with very little information, and very little typing.

Your changes introduced some mistakes though: in line 272 backward_rule makes no sense - unless we show that it won't work anymore as written. In line 295 it must be deleted, too, the good version appears 5 lines below.

I think that 1 and 3 are blockers, however. Advertising it like this seems completely wrong to me.

comment:79 in reply to: ↑ 75 Changed 4 years ago by mantepse

Minor thing, in Rule:

    All subclasses must provide the following methods:

should be

    All subclasses should provide the following methods:

because it is important that the thing also works (as much as possible) with a partial implementation, and, more importantly, it is important to cover situations which do not quite fit the framework (eg., RSK).

Are the optional or mandatory? Your documentation suggests more that they are all mandatory. What methods are needed (for what functionality) and which are recommended?

I would have thought that the RulePascal example in the tutorial and RuleRSK show that these methods are, in some sense, all "optional". Where does my documentation suggest that they would be mandatory?

I didn't want to explicitely list what is needed for which functionality. Let me try:

  • P_graph needs vertices, is_P_edge and has_multiple_edges
  • _check_duality needs P_graph and Q_graph
  • MyRule(filling) needs forward_rule, zero and has_multiple_edges
  • MyRule(labels=good_labels, shape=shape) needs backward_rule, zero and has_multiple_edges, if you provide the labels normalized, that is, as used by backward_rule
  • MyRule(labels=good_labels) additionally needs rank to guess the shape

One may be tempted to separate vertices, P_graph and _check_duality from the rest. However, combining them actually helps with implementing a "proof-of-concept". For example, if the dual graded graph is easy to implement, I can do assert is_P_edge(y, e, t) in forward_rule to catch silly mistakes. When the rank is easy, I can abort early in is_P_edge, etc.

An observation: for consistency, has_multiple_edges should be has_multiedges - as in graphs.

comment:80 in reply to: ↑ 76 ; follow-up: Changed 4 years ago by tscrim

Replying to mantepse:

  1. I took great care to strike a balance between the shorthand and GrowthDiagram(Rule, stuff). I feel ignored here. Although there are some cases where one may want to use different rules, most of the time there is only one rule around. This is also visible from Anne's comment. Please revert this.

I was not trying to ignore you; I did not know that was what you were trying to do as you didn't say that was your goal previously. However, I disagree with a number of them because the main entry point and object is GrowthDiagram. So I prefer to emphasize this over the shorthand. I do not want to put words in Anne's mouth, but I believe her comment was about the previous implementation as a way to address your documentation issues.

Also, to directly offer a counterpoint, each of the different crystals has a completely different data structure, whereas all growth diagrams have the same data structure. Perhaps a very good analogy is the tableaux crystal, which have specific rules for types ABCD. These are implemented in essentially the same way as the current implementation: the main entry point is crystals.Tableaux (i.e., CrystalOfTableaux) where the "rule" is the Cartan type that then is translated into a specific CrystalOfLetters subclass.

In this case, we can do some preparsing of the input to make things a little easier, but one could just as easily pass a CartanType object. For the growth diagram rules, I would have string inputs to specify the rule. Yet, the LLMS rule would need an additional argument, and I felt it was cleaner to do things this way.

  1. The docstring template for the forward rule is there for a reason - it tells you the conventions at a glance. Please leave this in. Alternatively, provide an abstract method with this docstring, and doctest it with help(RulePascal.forward_rule) at this point.

It has too much of a feeling of forcing people to have the same docstring. There are plenty of examples with the other rules already implemented, and IMO we do not need an @abstract_method(optional=True) method because we (will) explain what is needed in the documentation.

  1. rather minor: I learned in school that, when writing English, sentences (and half-sentences) after a colon start in lowercase - has this changed?

My understanding is that it depends on whether what comes after the colon and how much emphasis you want to put on what follows. Although you have most likely learned the formal rule.

  1. in the deprecation warnings, I took care to point the reader directly to the new entry point. While a minor issue, use GrowthDiagram with the YoungFibonacci rule instead is not really helpful.

The main entry point (and object) is and should be GrowthDiagram. I am expanding a bit more on that documentation because it is the main entry point (you do not get the module-level doc interactively).

I hope I pointed out that RuleRSK is not a pair of local rules in the sense of Fomin.

I think of it as all of the necessary information necessary to define a growth diagram.

Still, the framework is useful. Even more explicitly, the first RulePascal example shows that the framework is useful even if the forward rule is not invertible! (I am not making this up, see https://arxiv.org/pdf/1103.0319.pdf by Bloom and Saracino)

Indeed. I will add in the stuff from comment:79 into the Rule class documentation.

comment:81 in reply to: ↑ 78 Changed 4 years ago by tscrim

Replying to mantepse:

I just see that I should take back item 2 in comment:76 - I didn't see from the commit that you incrementally add to the minimal implementation. Please excuse.

No problem.

My original intention was to stress that one can implement a growth diagram with very little information, and very little typing.

I understood that from looking at the tutorial, but it was done in a way that suggested constructing things by monkey-patching, which is something that should be avoided.

Your changes introduced some mistakes though: in line 272 backward_rule makes no sense - unless we show that it won't work anymore as written. In line 295 it must be deleted, too, the good version appears 5 lines below.

That was the backward_rule that was being used at that point, but now it is just there explicitly. If it is wrong, which was no way clear to me, then more information is needed in the tutorial.

comment:82 in reply to: ↑ 80 ; follow-up: Changed 4 years ago by mantepse

Replying to tscrim:

because the main entry point and object is GrowthDiagram.

Well, for me it isn't. Possibly it is for developing new rules, and for first-timers, but certainly not for somebody using growth diagrams the second time.

It has too much of a feeling of forcing people to have the same docstring.

I like being reminded of the order of the arguments and the direction of the growth, since there is a dozen natural ways to do it. So, if I put it into the docstring right away, I don't have to remember it, and I don't even need to remember where to look it up.

For the growth diagram rules, I would have string inputs to specify the rule.

If you do that, then you've lost me completely. In fact, I'm close to quitting sage development entirely after this experience. I'm exhausted.

The main entry point (and object) is and should be GrowthDiagram?.

Can you please acknowledge that we disagree here, and that it is still possible to coexist.

I am expanding a bit more on that documentation because it is the main entry point (you do not get the module-level doc interactively).

Yes, I consider this a bug. I use the following as a workaround:

sage: import sage.combinat.growth
sage: sage.combinat.growth?

That was the backward_rule that was being used at that point, but now it is just there explicitly. If it is wrong, which was no way clear to me, then more information is needed in the tutorial.

You shouldn't have deleted the docstring. There it clearly shows that, in the case of multiedges, five arguments are needed.

comment:83 follow-up: Changed 4 years ago by mantepse

Let me summarise what I'd be OK with.

  1. Concerning long versus short form:
    • in the module level documentation, and all the individual rules, use the long version once and then the shorthand consistently.
    • in the documentation for GrowthDiagram, always use the long version.
  1. As the oversight with the backward rule in the introductory example shows, it is a good idea to have this docstring there.

comment:84 follow-up: Changed 4 years ago by mantepse

A question: usually, none of the methods appearing in the rules will actually depend on the instance (and that's the way it should be). Shouldn't we make them all staticmethods, or classmethods when necessary?

comment:85 Changed 4 years ago by git

  • Commit changed from 51e5fabd49db60d341964deb5c3f974a35e40c93 to e248e14342253cae343613e51eb38c5b78c920a5

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

e248e14provide P and Q-symbol for Sylvester

comment:86 in reply to: ↑ 82 Changed 4 years ago by tscrim

Replying to mantepse:

Replying to tscrim:

For the growth diagram rules, I would have string inputs to specify the rule.

If you do that, then you've lost me completely.

I am not saying we should do that. Let me also clarify, I would have something like GrowthDiagram("RSK", labels) be equivalent to GrowthDiagram(RuleRSK, labels).

In fact, I'm close to quitting sage development entirely after this experience. I'm exhausted.

I am also exhausted with this and ready to go to other code.

The main entry point (and object) is and should be GrowthDiagram?.

Can you please acknowledge that we disagree here, and that it is still possible to coexist.

Yes, I have.

I am expanding a bit more on that documentation because it is the main entry point (you do not get the module-level doc interactively).

Yes, I consider this a bug. I use the following as a workaround:

sage: import sage.combinat.growth
sage: sage.combinat.growth?

This is not a bug at all but a specification of Python.

That was the backward_rule that was being used at that point, but now it is just there explicitly. If it is wrong, which was no way clear to me, then more information is needed in the tutorial.

You shouldn't have deleted the docstring. There it clearly shows that, in the case of multiedges, five arguments are needed.

I feel that is unfair to me as it was your example and you are the expert in this area. IMO, it is a shortcoming/problem of the tutorial that needs to be addressed, and I do not have the expertise to correct it.

comment:87 in reply to: ↑ 83 Changed 4 years ago by tscrim

Replying to mantepse:

Let me summarise what I'd be OK with.

  1. Concerning long versus short form:
    • in the module level documentation, and all the individual rules, use the long version once and then the shorthand consistently.
    • in the documentation for GrowthDiagram, always use the long version.

I can relent on in each of the individual rules, but not in the module-level documentation.

  1. As the oversight with the backward rule in the introductory example shows, it is a good idea to have this docstring there.

I disagree. It is distracting from the tutorial, doesn't really explain why the method was wrong, and too much of an imposition on the developer.

We can also cc Nicolas and/or Darij to see what they think as well.

comment:88 Changed 4 years ago by git

  • Commit changed from e248e14342253cae343613e51eb38c5b78c920a5 to 984a76ad7ca0338ae06054bb7c30e02484a15d16

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

984a76aSome more documentation in GrowthDiagram for interactive use.

comment:89 in reply to: ↑ 84 Changed 4 years ago by tscrim

Replying to mantepse:

A question: usually, none of the methods appearing in the rules will actually depend on the instance (and that's the way it should be). Shouldn't we make them all staticmethods, or classmethods when necessary?

However, they can, so if one of the them can, all of them should be regular methods. There is also no penalty for static/class methods versus regular methods. Since we are also passing around instances, it makes more sense to me to have them be regular methods.

comment:90 Changed 4 years ago by mantepse

I am sorry for causing distress. I think it's an excellent idea to cc Darij and Nicolas, please go ahead!

Just to get on with it, for item 1 in comment:87, let's do it as follows:

  1. tutorial: consistently use long form, mention short form once
  2. GrowthDiagram?: consistently use long form
  3. individual rules: use long form once (in the class documentation), then consistently short form.

OK?

comment:91 Changed 4 years ago by mantepse

An observation: for consistency, has_multiple_edges should be has_multiedges - as in graphs.

It turns out that the graphs code is (slightly) inconsistent: for initialisation, the keyword is multiedges, in method names it's always multiple_edges. So it's better to stick to has_multiple_edges.

comment:92 Changed 4 years ago by git

  • Commit changed from 984a76ad7ca0338ae06054bb7c30e02484a15d16 to 2eca1b6ad13d45df424f3f1caac166bb505087fa

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

2eca1b6improve documentation, try to balance GrowthDiagram(MyRule,...) and MyRule(...)

comment:93 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_review

I don't know how to clarify the proper arguments of backward_rule. However, I expanded the doc of Rule, maybe that helps.

comment:94 Changed 4 years ago by mantepse

  • Cc nthiery darij added

comment:95 Changed 4 years ago by git

  • Commit changed from 2eca1b6ad13d45df424f3f1caac166bb505087fa to 780b636744d777871ddfa4ca08632e50b54975b9

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

780b636fix wrong comment

comment:96 Changed 4 years ago by mantepse

  • Authors changed from Martin Rubey to Martin Rubey, Travis Scrimshaw

ping?

comment:97 Changed 4 years ago by tscrim

Sorry, slightly busy with math and RL stuff. I will take a look at it this afternoon. I have some ideas about how to improve the backward_rule in the tutorial and should push it tonight.

Nicolas, Darij, we were wondering if you had any (quick) comments about the design or documentation of the growth diagrams and rules. I'm willing to defer more if you think I've had a stick up my a*$ about things.

comment:98 Changed 4 years ago by darij

Having a rigorous definition of a growth is a big step in the right direction. But I have a deadline on Sep 30, lecture notes to write and several batches of homework to grade; I am not sure whether any Sage work is realistic for me until then :(

comment:99 follow-up: Changed 4 years ago by darij

A couple quick remarks:

  • line 9: Travis, when did you become a class?
  • line 67: "the 36 cells of this matrix" seems to refer to the example on lines 49-54, not that on lines 62-64. Even so, are you sure it assigns partitions to the 36 cells of the matrix? IMHO it assigns integers to the 36 cells of the matrix, but assigns partitions to the 49 intersections of grid lines.
  • lines 113-128: This example should probably be explained better. What exactly does labels do? Does it determine the partitions along the western and northern borders? Is the growth really still working on a full 6x6 grid, rather than on some Young-ish portion of it? It's been a while since I've looked at skew RSK, so I guess I can now reasonably imitate a generic uninitiated reader...
  • lines 190-193: I think you mean
    * there is a positive integer `r` such that `DU = UD + rI` on the
      free `\ZZ`-module `\ZZ [V]`, where `D` is the down operator of
      `Q` (the `\ZZ`-linear map `\ZZ [V] \to \ZZ [V]` assigning to
      each vertex the formal sum of its predecessors in `Q`), where
      `U` is the up operator of `P` (the `\ZZ`-linear map
      `\ZZ [V] \to \ZZ [V]` assigning to each vertex the formal sum
      of its successors in `P`), and where `I` is the identity
      operator.
    

comment:100 Changed 4 years ago by mantepse

I have rewritten most of the introduction, but I'm not quite finished yet...

comment:101 in reply to: ↑ 99 Changed 4 years ago by tscrim

Replying to darij:

A couple quick remarks:

  • line 9: Travis, when did you become a class?

When I became Continuously Integrated. :P

@mantepse I will wait for your next push.

comment:102 Changed 4 years ago by mantepse

Hi Darij! Thank you for reading!

  • line 67: "the 36 cells of this matrix" seems to refer to the example on lines 49-54, not that on lines 62-64.

Moved the shorthand into a new section "Invocation".

Even so, are you sure it assigns partitions to the 36 cells of the matrix? IMHO it assigns integers to the 36 cells of the matrix, but assigns partitions to the 49 intersections of grid lines.

That's correct. The text is: "assigns partitions to the corners of each of the 36 cells of the matrix". No idea how to clarify further :-(

  • lines 113-128: This example should probably be explained better. What exactly does labels do? Does it determine the partitions along the western and northern borders? Is the growth really still working on a full 6x6 grid, rather than on some Young-ish portion of it?

I agree with "clarification needed". Please check.

  • lines 190-193: I think you mean
    * there is a positive integer `r` such that `DU = UD + rI` on the
      free `\ZZ`-module `\ZZ [V]`, where `D` is the down operator of
      `Q` (the `\ZZ`-linear map `\ZZ [V] \to \ZZ [V]` assigning to
      each vertex the formal sum of its predecessors in `Q`), where
      `U` is the up operator of `P` (the `\ZZ`-linear map
      `\ZZ [V] \to \ZZ [V]` assigning to each vertex the formal sum
      of its successors in `P`), and where `I` is the identity
      operator.
    

Yes, but I was afraid of writing this. I tried a compromise using a parenthetical remark, please check.

I also switched to using american english consistently (using a spellchecker), I adopted consistent parameter names for the forward and backward rules.

I hope it's OK now.

comment:103 Changed 4 years ago by git

  • Commit changed from 780b636744d777871ddfa4ca08632e50b54975b9 to 2aa3a8df2a1f87b5c58540468d879d0eef4aa306

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

2aa3a8dpolish

comment:104 Changed 4 years ago by git

  • Commit changed from 2aa3a8df2a1f87b5c58540468d879d0eef4aa306 to 3ed851be5196bcbe225cc5545bf77cecfcbcd9be

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

3ed851bA little bit more of doc polish.

comment:105 Changed 4 years ago by tscrim

  • Reviewers set to Martin Rubey, Travis Scrimshaw

I've done a few more changes and somewhat foregoing comment:87 and comment:90 to have a mix of both ways in the module-level documentation (which is primarily for new users) in the spirit of just completing this. If my changes are good, then go ahead and set this to a positive review.

comment:106 Changed 4 years ago by git

  • Commit changed from 3ed851be5196bcbe225cc5545bf77cecfcbcd9be to c2ed8d3887138ebd8b454ec6abe0d7e2dfbc8ff5

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

c2ed8d3fix a parenthesis, remark on duality, fix _check_duality, add test

comment:107 Changed 4 years ago by mantepse

I was implementing a pair of dual graphs, and had a bug. To make debugging easier, I made the message in _check_duality better. To do so, I also had to be consistent with "up in P and down in Q". To understand that, I added a remark on duality.

Apart from that, I removed a parenthesis.

If it's OK, please go ahead and set it to positive (finally :-)

If you dislike the more verbose error message, you can remove it, modify it, whatever you like!

comment:108 Changed 4 years ago by darij

Is the singular in "its predecessor" really intended? As in, there is only one?

comment:109 Changed 4 years ago by git

  • Commit changed from c2ed8d3887138ebd8b454ec6abe0d7e2dfbc8ff5 to 28ddfbe82caf21478043018c75c316d9c50370cc

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

28ddfbeno, it's not a tree

comment:110 Changed 4 years ago by mantepse

slightly embarrassed :-)

comment:111 Changed 4 years ago by tscrim

  • Milestone changed from sage-8.0 to sage-8.1
  • Reviewers changed from Martin Rubey, Travis Scrimshaw to Martin Rubey, Travis Scrimshaw, Darij Grinberg

One last little typo:

assigning to each vertex the formal sum of its predecessor,

should be predecessors. Once done, you can set a positive review on my behalf.

comment:112 Changed 4 years ago by mantepse

Wonderful!

I have yet another example ready - although without forward and backward rule because I don't know them: Dual graded graphs for (skew) quasisymmetric Schur functions. https://arxiv.org/pdf/1512.04614v1.pdf.

I have the graphs, and the conversion from a saturated chain in the P-graph to a CompositionTableaux.

Could you please confirm that it's better to put this in another ticket?

Or should I push?

comment:113 Changed 4 years ago by tscrim

I would say another ticket since this one is big enough already.

comment:114 Changed 4 years ago by git

  • Commit changed from 28ddfbe82caf21478043018c75c316d9c50370cc to 43b63242419ea06b5b5e0e3202984b84817d0dda

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

43b6324fix typos, add reference

comment:115 Changed 4 years ago by mantepse

  • Status changed from needs_review to positive_review

comment:116 Changed 4 years ago by mantepse

Yippee!

comment:117 Changed 4 years ago by tscrim

Thank you for all of your work on this.

comment:118 Changed 4 years ago by mantepse

Follow up on #23941 :-)

comment:119 Changed 4 years ago by vbraun

  • Branch changed from public/combinat/improve_growth_diagrams-23319 to 43b63242419ea06b5b5e0e3202984b84817d0dda
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.