Opened 6 years ago

Closed 5 years ago

#18567 closed enhancement (fixed)

LatticePoset: add maximal_sublattices()

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.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) Commit: d85c87373d6d2ec200e07efa2943e40bddf819ad
Dependencies: Stopgaps:

Description (last modified by jmantysalo)

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 jmantysalo

  • Branch set to u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__

comment:2 Changed 6 years ago by jmantysalo

  • Commit set to 4b47df9119878d94e5bee124765ff09bf2eb015a

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 of maximal_sublattices() (that internally generates some non-maximal sublattices and then discards them).

I tried googling some time, but find no algorithm for this. This is somewhat ad hoc solution.


New commits:

4b47df9Added a function.

comment:3 Changed 6 years ago by git

  • Commit changed from 4b47df9119878d94e5bee124765ff09bf2eb015a to 5ede78b761ed6f373727b1a72083f159725c0bbc

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

5ede78bSome optimization.

comment:4 Changed 6 years ago by git

  • Commit changed from 5ede78b761ed6f373727b1a72083f159725c0bbc to ef073c191be5c7e28967b11dd72c1072a2336336

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ef073c1New function for maximal_sublattices.

comment:5 Changed 6 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-6.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 jmantysalo

Ping... Anybody wants to look at the code? This is necessary part in the road to frattini_sublattice().

comment:7 Changed 5 years ago by kdilks

  • Cc kdilks added

comment:8 Changed 5 years ago by tscrim

Two minor things:

  • I think you could change the test sorted([sorted(list(x)) for x in ms]) to sorted(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 5 years ago by git

  • Commit changed from ef073c191be5c7e28967b11dd72c1072a2336336 to 8dbb1d8e2b57bc044fcfa51e2ee435f2b51143f2

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

8dbb1d8Two minor changes.

comment:10 Changed 5 years ago by jmantysalo

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 5 years ago by jmantysalo

  • Milestone changed from sage-6.8 to sage-6.9

comment:12 follow-up: Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

needs rebase, does not apply

comment:13 Changed 5 years ago by git

  • Commit changed from 8dbb1d8e2b57bc044fcfa51e2ee435f2b51143f2 to 24b10dd3197a804a8c7e7d477d0e01f9026bb734

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

24b10ddAdd maximal_sublattices().

comment:14 in reply to: ↑ 12 Changed 5 years ago by jmantysalo

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 5 years ago by jmantysalo

  • Status changed from needs_work to needs_review

comment:16 follow-up: Changed 5 years ago by tscrim

  • Branch changed from u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__ to u/tscrim/maximal_sublattices_iterator-18567
  • 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 5 years ago by jmantysalo

?? Branch-field is red, so I guess you made a typo.

comment:18 follow-up: Changed 5 years ago by tscrim

I think it's because beta3 was just released and my branch is based off beta2.

comment:19 in reply to: ↑ 18 Changed 5 years ago by jmantysalo

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 5 years ago by git

  • Commit set to d85c87373d6d2ec200e07efa2943e40bddf819ad

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

24b10ddAdd maximal_sublattices().
ffe4fb8Merge branch 'u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__' of git://trac.sagemath.org/sage into u/jmantysalo/latticeposet__add_maximal_sublattices_iterator__
d85c873Some reviewer tweaks.

comment:21 Changed 5 years ago by tscrim

It seems like it didn't push it for some reason. Fixed.

comment:22 in reply to: ↑ 16 Changed 5 years ago by jmantysalo

  • Authors changed from Jori Mäntysalo to Jori Mäntysalo, Travis Scrimshaw
  • 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 5 years ago by vbraun

  • Branch changed from u/tscrim/maximal_sublattices_iterator-18567 to d85c87373d6d2ec200e07efa2943e40bddf819ad
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.