Implement Atkinson's algorithm for counting linear extensions of (tree) posets

[jmatherne]

We add two methods to posets.py:

• "spectrum" - This method has input a poset P and an element a of P. It outputs the a-spectrum of P, which is a list of integers whose i-th entry contains the number of linear extensions of P with a in the i-th position. In particular, the sum of the entries of the a-spectrum is the number of linear extensions of P.

• "atkinson" - This method has input a poset P, whose underlying undirected graph is a forest, and an element a of P. It uses Atkinson's algorithm (see reference below) to compute the a-spectrum of P (see definition of a-spectrum above).

13. D. Atkinson, On computing the number of linear extensions of a tree, Order 7 (1990), 23-25.

[jmatherne]

We are working on this at Sage Days 99 this week.

[jmatherne]

New commits:

​6f9d504

Added alpha-spectrum method to posets class

[git]

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

​1005509

Added atkinson method to posets.py to use Atkinson's algorithm for computing linear extensions of posets whose underlying undirected graph is a forest

[git]

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

​fd63ff1

Fixed documentation. Code is ready to review.

[git]

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

​7df574c

Updated to adhere to the Python/Sage style guide

[chapoton]

• syntax should by python3 compatible, and it is not

• in the first-line-description, use "Return" and not "Returns"

• EXAMPLES: should be followed by 2 colons, usually

[embray]

Ticket retargeted after milestone closed

[git]

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

​002ae15

Implement small revisions for rebase to 9.1.beta9

[git]

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

​d30bd34

Small style changes to code

[bgillespie]

Rebased the ticket on release 9.1.beta9 and made a few revisions to docstrings and code to improve a few conventions. The functionality for this ticket seems to be working well, so I think the patch should be good to go.

Since I didn't directly write any of the code for the original patch, I'm going to call this a positive review with a reviewer patch. If one of the other authors can verify that the rebased code works for them as expected, we should be all set to change the ticket to positive review.

[chapoton]

Hello,

every new "raise" line that you introduce should be doctested.

[git]

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

​a62bbbf

Add tests for error conditions

[bgillespie]

Sure, added the tests. Let me know if you see any other issues.

[chapoton]

Thanks.

found a typo:

Hasse daigram

[git]

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

​4e14bfc

Fix typo in docstring of FinitePoset._split

[bgillespie]

Replying to chapoton:

found a typo:

Hasse daigram

Fixed.

[mkoeppe]

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

[gh-sgrosser]

Instead of using binomial(i,j) each time, it would be more efficient to use Pascal's identity and generate the full Pascal's triangle from levels 0 to n. Otherwise, you are recomputing many binomial coefficients repeatedly.

[tscrim]

I have just made a few documentation tweaks.

I think that computing and storing all of that information would take more time since it is done in Python than the binomial computation time (done at at most the C level if not a lower level). So I don't think it is worthwhile to do this right now unless we already have efficient code to generate Pascal's triangle.

However, if you do want a way to get more speed with minimal changes, I would suggest moving all of the helper functions to the Hasse diagram. That way you are working with integer labels and directly on the underlying digraph.

---

New commits:

​b449ceb	Merge branch 'u/bgillespie/rebase_atkinsons_alg_linear_extensions' of git://trac.sagemath.org/sage into public/combinat/linear_extensions_tree_posets-28237
​b8bf1ca	Some documentation and minor tweaks.

[git]

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

​5ea3aef

Adding new public methods to the list of poset methods.

[kdilks]

Convention for the list of methods is to refer to it as "the poset", not "a poset", or "this poset".

atkinson method doc-string is missing the grave character for the last use of i-th.

Not going to make those changes right away until I'm finished getting reacquainted with this code and checking things over again.

[tscrim]

Replying to kdilks:

Convention for the list of methods is to refer to it as "the poset", not "a poset", or "this poset".

There is no such convention, or at least once that is followed. unwrap uses "this poset" and the "a poset" makes grammatical sense here. However, I am +1 for having more uniformity.

Not going to make those changes right away until I'm finished getting reacquainted with this code and checking things over again.

Stefan (gh-sgrosser) should be soon moving stuff to the Hasse diagram backend, so give him a few days to do this.

How have you been doing Kevin?

[kdilks]

I'll wait until that gets done, then. Only other thing I noticed was that spectrum could maybe use a better non-trivial example than BooleanLattice?, since it's not immediately obvious what element '5' should correspond to.

Still working on the non-academic job search.

[git]

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

​333f558

moved helper functions for atkinson over to HasseDiagram

[git]

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

​10d75ca

Fixed failing examples and tests.

[tscrim]

Thanks. LGTM.

[tscrim]

Forgot about addressing comment:31 for a different example.

[git]

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

​9528cfe	Merge branch 'develop' into t/28237/public/combinat/linear_extensions_tree_posets-28237
​3de4f74	changed boolean lattice to young diagram
​48a04ef	Added full test with YoungDiagram

[git]

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

​bdf4b35

added back BooleanLattice example

[tscrim]

This now addresses comment:31. Kevin, if you disagree, feel free to revert the positive review.

@kdills Good luck with the job search. We should catch up sometime soon.