Various improvements to the implementation of Fomin's growth diagrams

[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.

CC: @sagetrac-sage-combinat @tscrim @anneschilling @nthiery @darijgr

Component: combinatorics

Author: Martin Rubey, Travis Scrimshaw

Branch/Commit: 43b6324

Reviewer: Martin Rubey, Travis Scrimshaw, Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/23319

[mantepse]

Branch: u/mantepse/growth_diagram_improvements

[mantepse]

Author: Martin Rubey

[mantepse]

Commit: bf1d772

[mantepse]

New commits:

bf1d772

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

[mantepse]

Description changed:

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6c34a9c	micro improvement to the backward rule in GrowthDiagramBinWord
74260a3	add support for multiple edges, add class for shifted shapes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bf1d772 to 74260a3

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 74260a3 to 2785f3f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2785f3f

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2785f3f to 53d37c7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

53d37c7

lazy import shifted shapes, fix forward rule, fix tests

[mantepse]

comment:7

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e96e3e1

fix missing DiGraph import

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 53d37c7 to e96e3e1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e96e3e1 to f1ba932

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f1ba932

add backwards rules for shifted shapes

[mantepse]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
 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 as example.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5a66779

initial version of a class for LLMS insertion

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f1ba932 to 5a66779

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cc4110c

almost done with LLMS insertion

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5a66779 to cc4110c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from cc4110c to 8853225

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8853225

fix a bug and add more (failing) tests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8853225 to 995d6d6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

995d6d6

fix final fehler, produce P_symbol as StrongTableau

[mantepse]

comment:15

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 995d6d6 to 1ddf882

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ddf882

add rank function

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

500e234

docfixes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1ddf882 to 500e234

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 500e234 to 7027638

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7027638

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

[mantepse]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 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 as example.
+Also allow for multiple edges in the dual graded graphs, implement shifted insertion and affine insertion as examples.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a1db015

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7027638 to a1db015

[fchapoton]

comment:21

needs documentation:

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a1db015 to 6b2a647

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ca9e7a	Merge branch 'develop' into t/23319/growth_diagram_improvements
6b2a647	add documentation and doctests

[fchapoton]

comment:24

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6b2a647 to b433c01

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b433c01

provide mode doctests

[mantepse]

comment:26

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__.

[tscrim]

comment:28

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.

[mantepse]

comment:29

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!

[mantepse]

comment:30

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%

[mantepse]

comment:31

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

[tscrim]

comment:32

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.

[tscrim]

comment:33

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

[mantepse]

comment:34

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.

[tscrim]

comment:35

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).