Categories for posets

[nthiery]

This patch creates categories for posets and lattices, refactors the
poset code, and adds new features. See the header of the patch for a
complete description.

Apply: attachment: trac_10998-categories-posets-nt.patch

Apply on sagenb repo: attachment: trac_10998-categories-posets-sagenb-nt.patch

Depends on #8288
Depends on #10651
Depends on #11289
Depends on #10938
Depends on #9065

CC: @sagetrac-sage-combinat @nilesjohnson @novoselt @vbraun

Component: combinatorics

Keywords: days30, sd31, Cernay2012

Author: Frédéric Chapoton, Christian Stump, Nicolas M. Thiéry

Reviewer: Franco Saliola, Christian Stump, Nicolas M. Thiéry, Florent Hivert

Merged: sage-5.0.beta4

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

[nthiery]

comment:6

Fixed trivial non commutation with trac_10193-graded_enumerated_sets-nt.patch in the Sage-Combinat queue. In principle the patch should now apply on vanilla sage + listed dependencies.

[stumpc5]

comment:7

Salut Nicolas,

I must say: there is a lot of code where I don't really understand what you do, and why you do it. E.g., which code is generic enough to put in categories and which is not, how are examples organized, how do you properly test the code, ...

In my (not yet final) review patch, I place some questions on implementations, some suggestions for additional methods, and I fixed several typos.

Best, Christian

[nthiery]

comment:8

Replying to @stumpc5:

I must say: there is a lot of code where I don't really understand
what you do, and why you do it.

Hmm, more specific questions (like the one below) would be useful to
get a constructive discussion :-)

E.g., which code is generic enough to put in categories and which is
not,

The rule of thumb is: does the code use the data structure or not?
For example, a method like has_top uses the internal hasse diagram,
and therefore remains in Poset. On the other hand a method like
join_irreducibles just requires that there is a method "lower_covers",
and so can be implemented generically in the category.

But that's just a rule thumb; I left in Poset all the code that was on
the edge, so as to avoid moving too much code around.

how are examples organized, how do you properly test the code, ...

Are those questions about the category framework in general, or about
this specific patch?

In my (not yet final) review patch, I place some questions on
implementations, some suggestions for additional methods, and I
fixed several typos.

Ok, thanks!

Cheers,
Nicolas

[nthiery]

Reviewer: Franco Saliola, Christian Stump, Nicolas M. Thiéry

[stumpc5]

comment:10

Apply only trac_10998-categories-posets-nt.patch

[hivert]

comment:11

There where a few bad sphinx markup. I just pushed a review patch on sage-combinat queue. I let you decide if you want to fold it or upload it.

Cheers,

Florent

[nthiery]

comment:12

Folded; thanks!

[nthiery]

comment:13

Fixed failing test.

[nthiery]

comment:14

Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!

[hivert]

comment:15

Replying to @nthiery:

Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!

I also just spotted a few more wrong sphinx markup ! I'm fixing those.

[hivert]

Changed reviewer from Franco Saliola, Christian Stump, Nicolas M. Thiéry to Franco Saliola, Christian Stump, Nicolas M. Thiéry, Florent Hivert

[hivert]

comment:16

Replying to @hivert:

Replying to @nthiery:

Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!

I also just spotted a few more wrong sphinx markup ! I'm fixing those.

Please see my new review patch on sage-combinat queue trac_10998-categories-posets-docfix-fh.patch

[saliola]

comment:17

I started with a fresh install of sage-4.7.rc1 and applied the patches at #9065 and #10938, followed by the patch for this ticket on the sage-combinat queue. I get a the following doctest failures.

The following tests failed:
 
        sage -t  devel/sage-trac/sage/geometry/fan_morphism.py # 25 doctests failed                                    
        sage -t  devel/sage-trac/sage/geometry/fan.py # 4 doctests failed
        sage -t  devel/sage-trac/sage/schemes/generic/toric_variety.py # 1 doctests failed
        sage -t  devel/sage-trac/sage/schemes/generic/toric_divisor.py # 3 doctests failed
        sage -t  devel/sage-trac/sage/schemes/generic/toric_chow_group.py # 10 doctests failed
        sage -t  devel/sage-trac/sage/structure/sage_object.pyx # 1 doctests failed

I verified that they are not caused by the other patches. (I also get these errors on 4.6.2 with the sage-combinat patches applied.)

I don't understand the problem. If you copy and paste the offending doctests into the sage command-line, I don't get the errors reported by the doctest system. Any ideas?

[nthiery]

comment:18

Oh right, I had forgotten about those. I tried a bit to find the problem, but to not avail yet.

Andrey, would you have any clue?

[novoselt]

comment:19

Hi Nicolas, thanks for ccing me!

Given that the problem is not reproducible in the command line, I am not exactly sure how to attack it, but we probably need to focus on the failing doctest in fan.py.

The problem as shown by the doctest framework is that cones which are supposed to know that they sit inside a fan appear to be "standalone" and breaking this relation messes up everything that builds up on top of it.

I'll try to trace it down further, but it may take me a few days due to traveling and conferencing...

[novoselt]

comment:48

Hello, I wonder - what are the current plans for this ticket? (I am interested in #11559 which depends on it.)

[nthiery]

comment:49

Replying to @novoselt:

Hello, I wonder - what are the current plans for this ticket? (I am interested in #11559 which depends on it.)

I really want to get rid of it. I should have more time working on Sage shortly, so hopefully that will be soon!
Nicolas

[simon-king-jena]

comment:50

I get numerous mismatches when applying the patch on top of sage-5.0.prealpha0. I think it is due to #11900. Since #11900 is merged, I suggest to rebase the patch from here.

[simon-king-jena]

Work Issues: rebase relative sage-5.0.beta0

[nthiery]

comment:51

Replying to @stumpc5:

I don't know what the current status here is; I just saw that the optional arguments label_elements and element_labels for show/plot do not work anymore (I fixed that a while ago somewhere is this big cluster patch). Can someone confirm that and/or see where my changes got lost?

As an example, I tried

sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] })
sage: D.plot(label_elements=False)

sage: D.show()
sage: elm_labs = {0:'a', 1:'b', 2:'c', 3:'d', 4:'e'}
sage: D.show(element_labels=elm_labs)

In both cases, I see the numbers as labels.

Fixed and tested in the updated patch!

[nthiery]

comment:52

Replying to @vbraun:

The poset elements have two attributes, .element and .vertex. Is there a one-to-one correspondence between elements and vertices? I do think so, but maybe there is something I'm overlooking.

If it is true, can we get rid of the superfluous element comparison in PosetElement.__eq__? This causes a serious slowdown in the toric code - its much cheaper to compare vertices than cones.

Thanks for the suggestion. I implemented this in the latest version of my patch!

[nthiery]

Changed keywords from days30, sd31 to days30, sd31, Cernay2012

[nthiery]

comment:53

The latest version of the patch is here and in the Sage-Combinat queue. Florent will make the final review tomorrow morning.

[nthiery]

Patch to be applied on the sagenb repo

[nthiery]

comment:54

Attachment: trac_10998-categories-posets-sagenb-nt.patch.gz

[nthiery]

comment:55

Attachment: trac_10998-categories-posets-nt.patch.gz

Final patch uploaded, after polishing of the doc and a final failing doctest. Crossreviewed with Florent. All tests pass. Positive review!

Thanks everyone!

[jdemeyer]

comment:56

Wow, you win the award for longest commit message.

[jdemeyer]

Changed work issues from rebase relative sage-5.0.beta0 to none

[jdemeyer]

Merged: sage-5.0.beta4