Opened 2 years ago
Closed 21 months ago
#29687 closed enhancement (fixed)
Efficiently Counting Linear Extensions of Specific Poset Families
Reported by: | gh-sgrosser | Owned by: | gh-sgrosser |
---|---|---|---|
Priority: | major | Milestone: | sage-9.3 |
Component: | combinatorics | Keywords: | gsoc2020 poset linear extension |
Cc: | nthiery, saliola, aschilling, tscrim | Merged in: | |
Authors: | Stefan Grosser | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This is a meta ticket for the following GSoC 2020 project by Stefan Grosser, mentored by Travis Scrimshaw. Project Proposal
The goal will be to add multiple classes to FinitePoset? such as d-complete, tree, and mobile, where all of these families have individual interest. Specifically, all of these classes permit efficient computation of the number of linear extensions.
Three main tickets were worked on: #28237 #29686 #30220
In 28237, I wrapped up the implementation of Atkinson's algorithm, used to compute the number of linear extensions of Tree posets. This tied in for the LinearExtensionsOfForest
class created.
In 29686, I worked on implenting the forest posets and d-complete posets, along with their linear extensions.
Finally in 30220, I worked on the implementation of mobile posets and the counting of their linear extensions. Additionally, I made several example posets (seen in #30273)
Change History (12)
comment:1 Changed 2 years ago by
- Description modified (diff)
- Owner changed from (none) to gh-sgrosser
comment:2 Changed 2 years ago by
- Keywords gsoc2020 added; gsoc removed
comment:3 Changed 2 years ago by
- Milestone changed from sage-9.1 to sage-9.2
comment:4 Changed 2 years ago by
comment:5 Changed 2 years ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:6 Changed 2 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:7 Changed 2 years ago by
- Status changed from needs_review to positive_review
comment:8 Changed 2 years ago by
full author, reviewer names
comment:9 Changed 2 years ago by
- Status changed from positive_review to needs_work
comment:10 Changed 2 years ago by
- Reviewers changed from tscrim to Travis Scrimshaw
comment:11 Changed 2 years ago by
- Status changed from needs_work to positive_review
comment:12 Changed 21 months ago by
- Resolution set to fixed
- Status changed from positive_review to closed
See also #28237.