Opened 6 years ago
Closed 6 years ago
#18567 closed enhancement (fixed)
LatticePoset: add maximal_sublattices()
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  
Cc:  ncohen, kdilks  Merged in:  
Authors:  Jori Mäntysalo, Travis Scrimshaw  Reviewers:  Travis Scrimshaw, Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  d85c873 (Commits, GitHub, GitLab)  Commit:  d85c87373d6d2ec200e07efa2943e40bddf819ad 
Dependencies:  Stopgaps: 
Description (last modified by )
This adds a new function that computes maximal (proper) sublattices of the lattice.
It could be faster to reverse thinking: instead of computing sublattice try to get a minimal "remainder" of sublattice. For example the remainder must be a connected poset and it's every minimal element may not have more than one lower cover. However, this slow implementation at least works, and can be used as a checkpoint when making faster implementations.
Change History (23)
comment:1 Changed 6 years ago by
 Branch set to u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__
comment:2 Changed 6 years ago by
 Commit set to 4b47df9119878d94e5bee124765ff09bf2eb015a
comment:3 Changed 6 years ago by
 Commit changed from 4b47df9119878d94e5bee124765ff09bf2eb015a to 5ede78b761ed6f373727b1a72083f159725c0bbc
Branch pushed to git repo; I updated commit sha1. New commits:
5ede78b  Some optimization.

comment:4 Changed 6 years ago by
 Commit changed from 5ede78b761ed6f373727b1a72083f159725c0bbc to ef073c191be5c7e28967b11dd72c1072a2336336
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ef073c1  New function for maximal_sublattices.

comment:5 Changed 6 years ago by
 Description modified (diff)
 Milestone changed from sagewishlist to sage6.8
 Status changed from new to needs_review
 Summary changed from LatticePoset: add maximal_sublattices_iterator() to LatticePoset: add maximal_sublattices()
comment:6 Changed 6 years ago by
Ping... Anybody wants to look at the code? This is necessary part in the road to frattini_sublattice()
.
comment:7 Changed 6 years ago by
 Cc kdilks added
comment:8 Changed 6 years ago by
Two minor things:
 I think you could change the test
sorted([sorted(list(x)) for x in ms])
tosorted(ms, key=sorted)
(note that I didn't actually try this).
 Could you add a space around the
<
comparisons to help improve readability?
Kevin, if you want to do the full review, please go ahead. I'm not sure I will have enough time to throughly test this.
comment:9 Changed 6 years ago by
 Commit changed from ef073c191be5c7e28967b11dd72c1072a2336336 to 8dbb1d8e2b57bc044fcfa51e2ee435f2b51143f2
Branch pushed to git repo; I updated commit sha1. New commits:
8dbb1d8  Two minor changes.

comment:10 Changed 6 years ago by
Here is one test lattice:
z={'d': [1,2,3], 1:['l', 4], 2:[4,'c'], 3:['r',4], 4:[5], 5:[6,13], 6:[7,11], 7:[8,14], 8:[9,12], 9:[10,15], 10:['u'], 'l':[11], 11:[12], 12:['u'], 'r':[13], 13:[14], 14:[15], 15:['u'], 'c':[10]} M3min=LatticePoset(z)
(from http://www.math.hawaii.edu/~ralph/Preprints/combined.pdf you can find more). Do you want some test code? You can make a random lattice (for example random poset + completion_by_cuts()
), and test by adding one random element to maximal sublattice  it should generate whole lattice. Or make a test like #18562 and see if a random maximal sublattice is found in the list of sublattices.
comment:11 Changed 6 years ago by
 Milestone changed from sage6.8 to sage6.9
comment:12 followup: ↓ 14 Changed 6 years ago by
 Status changed from needs_review to needs_work
needs rebase, does not apply
comment:13 Changed 6 years ago by
 Commit changed from 8dbb1d8e2b57bc044fcfa51e2ee435f2b51143f2 to 24b10dd3197a804a8c7e7d477d0e01f9026bb734
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
24b10dd  Add maximal_sublattices().

comment:14 in reply to: ↑ 12 Changed 6 years ago by
Replying to chapoton:
needs rebase, does not apply
Done that, should work now. I will change this to needs_review after checking myself that this compiles and works.
comment:15 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:16 followup: ↓ 22 Changed 6 years ago by
 Branch changed from u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__ to u/tscrim/maximal_sublattices_iterator18567
 Commit 24b10dd3197a804a8c7e7d477d0e01f9026bb734 deleted
 Reviewers set to Travis Scrimshaw
I made some minor reviewer changes. If you're happy with them, then go ahead and set a positive review.
comment:17 Changed 6 years ago by
?? Branchfield is red, so I guess you made a typo.
comment:18 followup: ↓ 19 Changed 6 years ago by
I think it's because beta3 was just released and my branch is based off beta2.
comment:19 in reply to: ↑ 18 Changed 6 years ago by
Replying to tscrim:
I think it's because beta3 was just released and my branch is based off beta2.
But I don't see the "commits"link, like there is when the code needs rebasing.
comment:20 Changed 6 years ago by
 Commit set to d85c87373d6d2ec200e07efa2943e40bddf819ad
Branch pushed to git repo; I updated commit sha1. New commits:
24b10dd  Add maximal_sublattices().

ffe4fb8  Merge branch 'u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__' of git://trac.sagemath.org/sage into u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__

d85c873  Some reviewer tweaks.

comment:21 Changed 6 years ago by
It seems like it didn't push it for some reason. Fixed.
comment:22 in reply to: ↑ 16 Changed 6 years ago by
 Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Jori Mäntysalo
 Status changed from needs_review to positive_review
Replying to tscrim:
I made some minor reviewer changes. If you're happy with them, then go ahead and set a positive review.
Thank you! Compiles & works.
(Now we just put this to production, and wait for someone to come up with better algorithm...)
comment:23 Changed 6 years ago by
 Branch changed from u/tscrim/maximal_sublattices_iterator18567 to d85c87373d6d2ec200e07efa2943e40bddf819ad
 Resolution set to fixed
 Status changed from positive_review to closed
There is now some code that at least seems to work. This is quite interesting optimization problem. Can this be made to real
maximal_sublattices_iterator()
instead ofmaximal_sublattices()
(that internally generates some nonmaximal sublattices and then discards them).I tried googling some time, but find no algorithm for this. This is somewhat ad hoc solution.
New commits:
Added a function.