#28237 closed enhancement (fixed)
Implement Atkinson's algorithm for counting linear extensions of (tree) posets
Reported by: | jmatherne | Owned by: | jmatherne |
---|---|---|---|
Priority: | major | Milestone: | sage-9.2 |
Component: | combinatorics | Keywords: | IMA Coding Sprints, days99, linear extensions, posets, trees, spectrum, gsoc2020 |
Cc: | Merged in: | ||
Authors: | Galen Dorpalen-Barry, 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 i-th entry contains the number of linear extensions ofP
witha
in the i-th 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), 23-25.
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 alpha-spectrum 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 first-line-description, use "Return" and not "Returns"
- EXAMPLES: should be followed by 2 colons, usually
comment:13 Changed 3 years ago by
- Milestone changed from sage-8.9 to sage-9.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
Sure, added the tests. Let me know if you see any other issues.
comment:22 follow-up: ↓ 24 Changed 2 years ago by
Thanks.
found 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 sage-9.1 to sage-9.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_posets-28237
- 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_posets-28237
|
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 follow-up: ↓ 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 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.
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 (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?
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 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.
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_posets-28237 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.