Opened 5 years ago

Last modified 5 years ago

#20516 needs_info enhancement

Generating non-isomorphic lattices

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-wishlist
Component: combinatorics Keywords: latticeposet
Cc: tscrim, chapoton Merged in:
Authors: Jori Mäntysalo Reviewers:
Report Upstream: N/A Work issues:
Branch: u/jmantysalo/generate_lattices (Commits, GitHub, GitLab) Commit: 55d1ef911cdfb3c04d35fbf1cfc2b7c90aa47e16
Dependencies: Stopgaps:

Status badges

Description

Peter Jipsen gave a permission to incorporate his lattice generation code to Sage. We should think where to put it and what should be the interface.

There are codes for generating all lattices, modular lattices and vertically indecomposable lattices, and at least some paper is about distributive lattices. Also for example lattice with given maximal height of width should be easy to make. But basically lattice is special type of poset, and so class lattice of maximal height n is a poset with two restrictions.

Change History (8)

comment:1 Changed 5 years ago by jmantysalo

  • Branch set to u/jmantysalo/generate_lattices

comment:2 Changed 5 years ago by jmantysalo

  • Cc tscrim chapoton added
  • Commit set to 55d1ef911cdfb3c04d35fbf1cfc2b7c90aa47e16
  • Keywords latticeposet added
  • Status changed from new to needs_info

I just mechanically copied the code and checked that it seems to work inside Sage.

I am interested in generation of special classess of posets and lattices, and have already made a modification to generate only atomic lattices. But before those we should think about interface, and for that I ask help.

Please note that this lattice code starts with empty lattice and add elements; poset generation starts with antichain and adds covering relations. So for lattices it has no extra cost to generate lattices up to give size instead of given size.

comment:3 Changed 5 years ago by jmantysalo

Just pinging this up to ask "anybody interested at least a little?".

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

From a quick look, it seems more like the generation code should be an iterator class: it also would avoid the globals (which would become instance variables) and could be an iterator proper (which is lighter weight for loops).

Some other small comments, you should use Python3 compatible print statements and be more PEP8 compliant (in particular, things like this should be 2 lines except: print i, orb, p, L, le).

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

Replying to tscrim:

From a quick look, it seems more like the generation code should be an iterator class: it also would avoid the globals (which would become instance variables) and could be an iterator proper (which is lighter weight for loops).

OK. Now, if we do it as a real class, what about in? Try

print DiGraph({0: [1]}) in digraphs(2)
print DiGraph({1: [0]}) in digraphs(2)
print Poset({0: [1]}) in Posets(2)
print Poset({1: [0]}) in Posets(2)

Do we want "filter-usable class", something like L = LatticePosets(10, properties=['selfdual', 'modular']); . . .; if x in L: . . .? It would be easier to just make a generator function.

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

With all of the extra functions and cross usage of variables, it's a (IMO big) "technical debt" and could be a maintenance headache down the road. If you don't want to do the extra work, at least have a separate class to do the iteration and then return a list over that iterator.

comment:7 in reply to: ↑ 6 Changed 5 years ago by jmantysalo

Replying to tscrim:

With all of the extra functions and cross usage of variables, it's a (IMO big) "technical debt" and could be a maintenance headache down the road. If you don't want to do the extra work, at least have a separate class to do the iteration and then return a list over that iterator.

OK, can be done. But still I don't see the point of making a class instead of just a top-level function with internal subfunctions.

comment:8 Changed 5 years ago by tscrim

It's because there are so many subfunctions and lines like

global m, Bk, Sk, As, M # avoid passing a lot of parameter into achains

By doing it this way, it makes it so that there was no way to confuse variables and scope. You also get a very minor speed bump for not passing so many parameters and it becomes much easier to Cythonize.

Also, while you are moving stuff, it is faster to use not b instead of b == [] and while base: instead of while len(base)!=0:.

Note: See TracTickets for help on using tickets.