#28237 closed enhancement (fixed)
Implement Atkinson's algorithm for counting linear extensions of (tree) posets
Reported by:  jmatherne  Owned by:  jmatherne 

Priority:  major  Milestone:  sage9.2 
Component:  combinatorics  Keywords:  IMA Coding Sprints, days99, linear extensions, posets, trees, spectrum, gsoc2020 
Cc:  Merged in:  
Authors:  Galen DorpalenBarry, Bryan Gillespie, Jacob P. Matherne, Thomas McConville, Franco Saliola, Stefan Grosser  Reviewers:  Kevin Dilks, Bryan Gillespie, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  bdf4b35 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
We add two methods to posets.py:
 "spectrum"  This method has input a poset
P
and an elementa
ofP
. It outputs thea
spectrum ofP
, which is a list of integers whose ith entry contains the number of linear extensions ofP
witha
in the ith position. In particular, the sum of the entries of thea
spectrum is the number of linear extensions ofP
.
 "atkinson"  This method has input a poset
P
, whose underlying undirected graph is a forest, and an elementa
ofP
. It uses Atkinson's algorithm (see reference below) to compute thea
spectrum ofP
(see definition ofa
spectrum above).
 D. Atkinson, On computing the number of linear extensions of a tree, Order 7 (1990), 2325.
Change History (40)
comment:1 Changed 3 years ago by
 Keywords sd99 linear extensions posets trees spectrum added
 Owner changed from (none) to jmatherne
 Priority changed from major to minor
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 3 years ago by
 Component changed from PLEASE CHANGE to combinatorics
 Priority changed from minor to major
comment:3 Changed 3 years ago by
 Branch set to u/jmatherne/atkinson_s_algorithm_for_counting_linear_extensions_of__tree__posets
comment:4 Changed 3 years ago by
 Commit set to 6f9d50418a680f8faee723696090fe3b73f097fb
 Keywords IMA Coding Sprints days99 added; sd99 removed
New commits:
6f9d504  Added alphaspectrum method to posets class

comment:5 Changed 3 years ago by
comment:6 Changed 3 years ago by
 Summary changed from Atkinson's algorithm for counting linear extensions of (tree) posets to Implement Atkinson's algorithm for counting linear extensions of (tree) posets
comment:7 Changed 3 years ago by
 Commit changed from 6f9d50418a680f8faee723696090fe3b73f097fb to 1005509be5429618f5af4dcc9653f233e4c8cf60
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

comment:8 Changed 3 years ago by
 Commit changed from 1005509be5429618f5af4dcc9653f233e4c8cf60 to fd63ff1f5e32c68a8cedca4a6fdcd81b02f353ce
Branch pushed to git repo; I updated commit sha1. New commits:
fd63ff1  Fixed documentation. Code is ready to review.

comment:9 Changed 3 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:10 Changed 3 years ago by
 Reviewers set to Kevin Dilks
comment:11 Changed 3 years ago by
 Commit changed from fd63ff1f5e32c68a8cedca4a6fdcd81b02f353ce to 7df574c18db780a316b61c5196e18055d414a58b
Branch pushed to git repo; I updated commit sha1. New commits:
7df574c  Updated to adhere to the Python/Sage style guide

comment:12 Changed 3 years ago by
 Status changed from needs_review to needs_work
 syntax should by python3 compatible, and it is not
 in the firstlinedescription, use "Return" and not "Returns"
 EXAMPLES: should be followed by 2 colons, usually
comment:13 Changed 3 years ago by
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:14 Changed 2 years ago by
 Branch changed from u/jmatherne/atkinson_s_algorithm_for_counting_linear_extensions_of__tree__posets to u/bgillespie/rebase_atkinsons_alg_linear_extensions
comment:15 Changed 2 years ago by
 Commit changed from 7df574c18db780a316b61c5196e18055d414a58b to 002ae1523d5144769aba55a1a158ea04e999dc6a
Branch pushed to git repo; I updated commit sha1. New commits:
002ae15  Implement small revisions for rebase to 9.1.beta9

comment:16 Changed 2 years ago by
 Commit changed from 002ae1523d5144769aba55a1a158ea04e999dc6a to d30bd348b4031f51735e27c3b630b470b31e17fa
Branch pushed to git repo; I updated commit sha1. New commits:
d30bd34  Small style changes to code

comment:17 Changed 2 years ago by
 Status changed from needs_work to needs_review
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.
comment:18 Changed 2 years ago by
 Reviewers changed from Kevin Dilks to Kevin Dilks, Bryan Gillespie
comment:19 Changed 2 years ago by
 Status changed from needs_review to needs_work
Hello,
every new "raise" line that you introduce should be doctested.
comment:20 Changed 2 years ago by
 Commit changed from d30bd348b4031f51735e27c3b630b470b31e17fa to a62bbbfef419ff421fbf20ffbcb2367650f09122
Branch pushed to git repo; I updated commit sha1. New commits:
a62bbbf  Add tests for error conditions

comment:21 Changed 2 years ago by
 Status changed from needs_work to needs_review
Replying to chapoton:
Hello,
every new "raise" line that you introduce should be doctested.
Sure, added the tests. Let me know if you see any other issues.
comment:22 followup: ↓ 24 Changed 2 years ago by
Thanks.
foudn a typo:
Hasse daigram
comment:23 Changed 2 years ago by
 Commit changed from a62bbbfef419ff421fbf20ffbcb2367650f09122 to 4e14bfc30ad2ed87330483a2c3bf0514759e444c
Branch pushed to git repo; I updated commit sha1. New commits:
4e14bfc  Fix typo in docstring of FinitePoset._split

comment:24 in reply to: ↑ 22 Changed 2 years ago by
comment:25 Changed 2 years ago by
 Milestone changed from sage9.1 to sage9.2
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.
comment:26 Changed 2 years ago by
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.
comment:27 Changed 2 years ago by
 Branch changed from u/bgillespie/rebase_atkinsons_alg_linear_extensions to public/combinat/linear_extensions_tree_posets28237
 Commit changed from 4e14bfc30ad2ed87330483a2c3bf0514759e444c to b8bf1caff7de6c0812d172ff9e980b70e0ec6777
 Reviewers changed from Kevin Dilks, Bryan Gillespie to Kevin Dilks, Bryan Gillespie, Travis Scrimshaw
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_posets28237

b8bf1ca  Some documentation and minor tweaks.

comment:28 Changed 2 years ago by
 Commit changed from b8bf1caff7de6c0812d172ff9e980b70e0ec6777 to 5ea3aef2923a5a9c0030244bddaac0fc3abacd73
Branch pushed to git repo; I updated commit sha1. New commits:
5ea3aef  Adding new public methods to the list of poset methods.

comment:29 followup: ↓ 30 Changed 2 years ago by
Convention for the list of methods is to refer to it as "the poset", not "a poset", or "this poset".
atkinson
method docstring is missing the grave character for the last use of ith.
Not going to make those changes right away until I'm finished getting reacquainted with this code and checking things over again.
comment:30 in reply to: ↑ 29 Changed 2 years ago by
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 (ghsgrosser) 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?
comment:31 Changed 2 years ago by
I'll wait until that gets done, then. Only other thing I noticed was that spectrum
could maybe use a better nontrivial example than BooleanLattice?, since it's not immediately obvious what element '5' should correspond to.
Still working on the nonacademic job search.
comment:32 Changed 2 years ago by
 Commit changed from 5ea3aef2923a5a9c0030244bddaac0fc3abacd73 to 333f55884845e63591a332a038f459313b5cb50b
Branch pushed to git repo; I updated commit sha1. New commits:
333f558  moved helper functions for atkinson over to HasseDiagram

comment:33 Changed 2 years ago by
 Commit changed from 333f55884845e63591a332a038f459313b5cb50b to 10d75ca7d8898a081192cd427e6bd7b7e730e85b
Branch pushed to git repo; I updated commit sha1. New commits:
10d75ca  Fixed failing examples and tests.

comment:35 Changed 2 years ago by
 Status changed from positive_review to needs_work
Forgot about addressing comment:31 for a different example.
comment:36 Changed 2 years ago by
 Commit changed from 10d75ca7d8898a081192cd427e6bd7b7e730e85b to 48a04ef9463b14674f3ece12bd3a2c1e8fddbf9b
comment:37 Changed 2 years ago by
 Commit changed from 48a04ef9463b14674f3ece12bd3a2c1e8fddbf9b to bdf4b35a8e1acc544eb1c746c23a232603105afd
Branch pushed to git repo; I updated commit sha1. New commits:
bdf4b35  added back BooleanLattice example

comment:38 Changed 2 years ago by
 Status changed from needs_work to positive_review
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.
comment:39 Changed 2 years ago by
 Branch changed from public/combinat/linear_extensions_tree_posets28237 to bdf4b35a8e1acc544eb1c746c23a232603105afd
 Resolution set to fixed
 Status changed from positive_review to closed
comment:40 Changed 2 years ago by
 Commit bdf4b35a8e1acc544eb1c746c23a232603105afd deleted
 Keywords gsoc2020 added
We are working on this at Sage Days 99 this week.