Opened 3 years ago

Closed 2 years ago

Last modified 2 years ago

#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:

Status badges

Description (last modified by 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).
  1. 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 jmatherne

  • Authors set to Galen Dorpalen-Barry, Bryan Gillespie, Jacob P. Matherne, Thomas McConville
  • 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

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

comment:2 Changed 3 years ago by jmatherne

  • Component changed from PLEASE CHANGE to combinatorics
  • Priority changed from minor to major

comment:3 Changed 3 years ago by jmatherne

  • Branch set to u/jmatherne/atkinson_s_algorithm_for_counting_linear_extensions_of__tree__posets

comment:4 Changed 3 years ago by jmatherne

  • Commit set to 6f9d50418a680f8faee723696090fe3b73f097fb
  • Keywords IMA Coding Sprints days99 added; sd99 removed

New commits:

6f9d504Added alpha-spectrum method to posets class

comment:5 Changed 3 years ago by jmatherne

  • Authors changed from Galen Dorpalen-Barry, Bryan Gillespie, Jacob P. Matherne, Thomas McConville to Galen Dorpalen-Barry, Bryan Gillespie, Jacob P. Matherne, Thomas McConville, Franco Saliola

comment:6 Changed 3 years ago by jmatherne

  • 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 git

  • Commit changed from 6f9d50418a680f8faee723696090fe3b73f097fb to 1005509be5429618f5af4dcc9653f233e4c8cf60

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

1005509Added 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 git

  • Commit changed from 1005509be5429618f5af4dcc9653f233e4c8cf60 to fd63ff1f5e32c68a8cedca4a6fdcd81b02f353ce

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

fd63ff1Fixed documentation. Code is ready to review.

comment:9 Changed 3 years ago by jmatherne

  • Description modified (diff)
  • Status changed from new to needs_review

comment:10 Changed 3 years ago by kdilks

  • Reviewers set to Kevin Dilks

comment:11 Changed 3 years ago by git

  • Commit changed from fd63ff1f5e32c68a8cedca4a6fdcd81b02f353ce to 7df574c18db780a316b61c5196e18055d414a58b

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

7df574cUpdated to adhere to the Python/Sage style guide

comment:12 Changed 3 years ago by chapoton

  • 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
Last edited 3 years ago by chapoton (previous) (diff)

comment:13 Changed 3 years ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:14 Changed 2 years ago by bgillespie

  • 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 git

  • Commit changed from 7df574c18db780a316b61c5196e18055d414a58b to 002ae1523d5144769aba55a1a158ea04e999dc6a

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

002ae15Implement small revisions for rebase to 9.1.beta9

comment:16 Changed 2 years ago by git

  • Commit changed from 002ae1523d5144769aba55a1a158ea04e999dc6a to d30bd348b4031f51735e27c3b630b470b31e17fa

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

d30bd34Small style changes to code

comment:17 Changed 2 years ago by bgillespie

  • 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 bgillespie

  • Reviewers changed from Kevin Dilks to Kevin Dilks, Bryan Gillespie

comment:19 Changed 2 years ago by chapoton

  • 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 git

  • Commit changed from d30bd348b4031f51735e27c3b630b470b31e17fa to a62bbbfef419ff421fbf20ffbcb2367650f09122

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

a62bbbfAdd tests for error conditions

comment:21 Changed 2 years ago by bgillespie

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

Last edited 2 years ago by bgillespie (previous) (diff)

comment:22 follow-up: Changed 2 years ago by chapoton

Thanks.

foudn a typo:

Hasse daigram

Version 0, edited 2 years ago by chapoton (next)

comment:23 Changed 2 years ago by git

  • Commit changed from a62bbbfef419ff421fbf20ffbcb2367650f09122 to 4e14bfc30ad2ed87330483a2c3bf0514759e444c

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

4e14bfcFix typo in docstring of FinitePoset._split

comment:24 in reply to: ↑ 22 Changed 2 years ago by bgillespie

Replying to chapoton:

found a typo:

Hasse daigram

Fixed.

comment:25 Changed 2 years ago by mkoeppe

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

comment:27 Changed 2 years ago by tscrim

  • 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:

b449cebMerge branch 'u/bgillespie/rebase_atkinsons_alg_linear_extensions' of git://trac.sagemath.org/sage into public/combinat/linear_extensions_tree_posets-28237
b8bf1caSome documentation and minor tweaks.

comment:28 Changed 2 years ago by git

  • Commit changed from b8bf1caff7de6c0812d172ff9e980b70e0ec6777 to 5ea3aef2923a5a9c0030244bddaac0fc3abacd73

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

5ea3aefAdding new public methods to the list of poset methods.

comment:29 follow-up: Changed 2 years ago by 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.

comment:30 in reply to: ↑ 29 Changed 2 years ago by 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?

comment:31 Changed 2 years ago by 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.

comment:32 Changed 2 years ago by git

  • Commit changed from 5ea3aef2923a5a9c0030244bddaac0fc3abacd73 to 333f55884845e63591a332a038f459313b5cb50b

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

333f558moved helper functions for atkinson over to HasseDiagram

comment:33 Changed 2 years ago by git

  • Commit changed from 333f55884845e63591a332a038f459313b5cb50b to 10d75ca7d8898a081192cd427e6bd7b7e730e85b

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

10d75caFixed failing examples and tests.

comment:34 Changed 2 years ago by tscrim

  • Authors changed from Galen Dorpalen-Barry, Bryan Gillespie, Jacob P. Matherne, Thomas McConville, Franco Saliola to Galen Dorpalen-Barry, Bryan Gillespie, Jacob P. Matherne, Thomas McConville, Franco Saliola, Stefan Grosser
  • Status changed from needs_review to positive_review

Thanks. LGTM.

comment:35 Changed 2 years ago by tscrim

  • Status changed from positive_review to needs_work

Forgot about addressing comment:31 for a different example.

comment:36 Changed 2 years ago by git

  • Commit changed from 10d75ca7d8898a081192cd427e6bd7b7e730e85b to 48a04ef9463b14674f3ece12bd3a2c1e8fddbf9b

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

9528cfeMerge branch 'develop' into t/28237/public/combinat/linear_extensions_tree_posets-28237
3de4f74changed boolean lattice to young diagram
48a04efAdded full test with YoungDiagram

comment:37 Changed 2 years ago by git

  • Commit changed from 48a04ef9463b14674f3ece12bd3a2c1e8fddbf9b to bdf4b35a8e1acc544eb1c746c23a232603105afd

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

bdf4b35added back BooleanLattice example

comment:38 Changed 2 years ago by tscrim

  • 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 vbraun

  • 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 tscrim

  • Commit bdf4b35a8e1acc544eb1c746c23a232603105afd deleted
  • Keywords gsoc2020 added
Note: See TracTickets for help on using tickets.