Generating non-isomorphic lattices

[f29946bc-ee7b-48cd-9abc-3445948c551d]

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.

CC: @tscrim @fchapoton

Component: combinatorics

Keywords: latticeposet

Author: Jori Mäntysalo

Branch/Commit: u/jmantysalo/generate_lattices @ 55d1ef9

Issue created by migration from https://trac.sagemath.org/ticket/20516

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/generate_lattices

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:2

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.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Changed keywords from none to latticeposet

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Commit: 55d1ef9

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:3

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

[tscrim]

comment:4

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:5

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.

[tscrim]

comment:6

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.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:7

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.

[tscrim]

comment:8

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