Opened 5 years ago

Closed 5 years ago

#20495 closed enhancement (fixed)

Add a function to generate random lattice (poset)

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.4
Component: combinatorics Keywords: latticeposet
Cc: tscrim, chapoton Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 5fc39b0 (Commits, GitHub, GitLab) Commit: 5fc39b08f9ad24d57296b2e35c7a0552f126f715
Dependencies: Stopgaps:

Status badges

Description (last modified by jmantysalo)

This patch will add a function to generate a random lattice with given number of elements.

Currently only "dismantlable" and "planar" are implemented as a property. Is this a good desing from user perspective? I hope to later add for example "modular", but of course most combinations will always just raise NotImplemented?, as there are at least dozens of meaningful combinations that should be coded one by one.

I am not satisfied of this code, but at least it works and is quite fast.

Change History (17)

comment:1 Changed 5 years ago by jmantysalo

  • Branch set to u/jmantysalo/random-lattice

comment:2 Changed 5 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc tscrim chapoton added
  • Commit set to 60eff31087c3784f997ae2f49bd5150e676fad85
  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-7.4
  • Status changed from new to needs_review

New commits:

60eff31Add random lattice generation.

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

If you pass in a tuple for the properties, e.g., ('dismantlable'), it will result in an error. If you're going to compare it to a list, you should cast properties into a list. You should also future-proof your code by checking properties[0] == 'dismantlable'.

Also, I feel that p = 0 should be acceptable and return a chain, as it is the unique lattice with the minimal number of cover relations.

Is this model of random lattices known (i.e., is there a literature reference for it)?

comment:4 in reply to: ↑ 3 ; follow-up: Changed 5 years ago by jmantysalo

Replying to tscrim:

If you pass in a tuple for the properties, e.g., ('dismantlable'), it will result in an error. If you're going to compare it to a list, you should cast properties into a list. You should also future-proof your code by checking properties[0] == 'dismantlable'.

The code must be something like

props = ['dismantlable', 'modular', 'planar' . . .]
for p in properties:
    if p not in props:
        Raise ValueError(...)

But the most important question is the "interface", that is hard to change later. What kind of parameters would be possible to have for different kind of lattices? What if type x lattices can have five different numerical parameters to choise from, and type y has two?

Or maybe I am planning too much for a code not yet written.

Also, I feel that p = 0 should be acceptable and return a chain, as it is the unique lattice with the minimal number of cover relations.

Actually it kind of works now, but generates a random semilattice with minimal number of covers, i.e. a tree, and then adds the top element. Would be strange if p=0 would always give the chain and p=0.001 would give a tree (+top).

Is this model of random lattices known (i.e., is there a literature reference for it)?

I found only https://www.emis.de/journals/MB/125.2/mb125_2_1.pdf and the code in that paper is... Well, take a look at yourself.

I don't know if there is even a theoretical results about "random lattice", like "What is the average width of all non-isomorphic lattices on 100 elements?" So is there anything to compare to be able to say how good or bad an algorithm is?

comment:5 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

If you pass in a tuple for the properties, e.g., ('dismantlable'), it will result in an error. If you're going to compare it to a list, you should cast properties into a list. You should also future-proof your code by checking properties[0] == 'dismantlable'.

The code must be something like

props = ['dismantlable', 'modular', 'planar' . . .]
for p in properties:
    if p not in props:
        Raise ValueError(...)

You can also do something like this:

if not set('dismantlable', 'modular', 'planar', ...).is_superset(properties):
    raise ValueError("invalid property")

But the most important question is the "interface", that is hard to change later. What kind of parameters would be possible to have for different kind of lattices? What if type x lattices can have five different numerical parameters to choise from, and type y has two?

We can easily add parameters and moderately easily change to an *args attribute if necessary.

Or maybe I am planning too much for a code not yet written.

Also, I feel that p = 0 should be acceptable and return a chain, as it is the unique lattice with the minimal number of cover relations.

Actually it kind of works now, but generates a random semilattice with minimal number of covers, i.e. a tree, and then adds the top element. Would be strange if p=0 would always give the chain and p=0.001 would give a tree (+top).

The minimal number of covers has to be a chain, because a tree + top will have E+k covers, where k is the number leaves that is not the root and E is the number of edges of the tree. 2 leaves with one being the root minimizes k, which implies the tree must be a path/chain. So it is not strange to me because boundary points (at least for Gnp random graphs) can behave different.

Is this model of random lattices known (i.e., is there a literature reference for it)?

I found only https://www.emis.de/journals/MB/125.2/mb125_2_1.pdf and the code in that paper is... Well, take a look at yourself.

Hmmm...I see your point. At least we could drop that C code in and link it easily in Sage to compare. Although it looks like it will generate a different distribution from a cursory look.

I don't know if there is even a theoretical results about "random lattice", like "What is the average width of all non-isomorphic lattices on 100 elements?" So is there anything to compare to be able to say how good or bad an algorithm is?

Well, if its not known, it might result in a paper if you can determine some theoretical results. I was asking more if there was a reference that could be added.

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

Replying to tscrim:

You can also do something like this:

if not set('dismantlable', 'modular', 'planar', ...).is_superset(properties):
    raise ValueError("invalid property")

But then we can not raise exception saying what property was invalid.

We can easily add parameters and moderately easily change to an *args attribute if necessary.

True. We could add something like extra parameter if needed for some special type of lattices.

Also, I feel that p = 0 should be acceptable and return a chain, as it is the unique lattice with the minimal number of cover relations.

Actually it kind of works now, but generates a random semilattice with minimal number of covers, i.e. a tree, and then adds the top element. Would be strange if p=0 would always give the chain and p=0.001 would give a tree (+top).

The minimal number of covers has to be a chain

Yes for lattices. Not for semilattices.

But after all, I don't know if we really have to think about semilattices. I did the code such way that internal function generates a semilattice, which can be used directly as a meet-semilattice, inversed as a join-semilattice or after adding one element as a lattice.

Is this model of random lattices known (i.e., is there a literature reference for it)?

I found only https://www.emis.de/journals/MB/125.2/mb125_2_1.pdf and the code in that paper is... Well, take a look at yourself.

Hmmm...I see your point. At least we could drop that C code in and link it easily in Sage to compare. Although it looks like it will generate a different distribution from a cursory look.

Can you copypaste and compile it from PDF? I think I tried and failed.

I don't know if there is even a theoretical results about "random lattice", like "What is the average width of all non-isomorphic lattices on 100 elements?" So is there anything to compare to be able to say how good or bad an algorithm is?

Well, if its not known, it might result in a paper if you can determine some theoretical results. I was asking more if there was a reference that could be added.

True. The paper http://users.cecs.anu.edu.au/~bdm/papers/posets.pdf actually refers to a result about posets: "Our results do not show this behaviour, emphasizing again that the convergence of posets to their asymptotic behaviour is quite slow."

But at least the average number of atoms equals to number of coatoms. My ad hoc code does not achieve this. I used sqrt(random()) as a slight help to this direction.

I tested that my code generates all lattices of given (small) size eventually, and it should be theoretically clear too.

comment:7 Changed 5 years ago by git

  • Commit changed from 60eff31087c3784f997ae2f49bd5150e676fad85 to cd7104619519cee19b5c741888870d96d53f6ed2

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

cd71046Add random planar lattices.

comment:8 Changed 5 years ago by jmantysalo

  • Description modified (diff)
  • Status changed from needs_review to needs_work

How this looks? I think that this should still simplified, so that RandomLattice will contain only the parameters check and the logic to choise right function to do the job.

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

I think you should make known_properties into a set for faster checking. (Actually, to still have your desired error message, you could do if properties.difference(known_properties):, then pop an element off from that different for the error message.) There is a discrepancy between the doc and the code in that the doc says p=0 is valid input, but the code will error out. Otherwise it seems okay.

comment:10 Changed 5 years ago by git

  • Commit changed from cd7104619519cee19b5c741888870d96d53f6ed2 to 07ea77dcc7c146c652732ee269f72f6448d9d1ff

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

07ea77dSome random :=) changes.

comment:11 Changed 5 years ago by git

  • Commit changed from 07ea77dcc7c146c652732ee269f72f6448d9d1ff to 5fc39b08f9ad24d57296b2e35c7a0552f126f715

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

5fc39b0Minor correction.

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

  • Status changed from needs_work to needs_review

Replying to tscrim:

I think you should make known_properties into a set for faster checking. (Actually, to still have your desired error message, you could do if properties.difference(known_properties):, then pop an element off from that different for the error message.) There is a discrepancy between the doc and the code in that the doc says p=0 is valid input, but the code will error out. Otherwise it seems okay.

OK, done that, even if this should not be an issue: I suppose we wont have that many properties ever available.

Now if someone says Posets.RandomLattice(30, 0, properties='dismantlable') it will also work, and not raise an error about parameter value 'd'. (See set('hello').)

I also rethinked something, but the algorithms themself have not changed. I added tests and docstrings.

Maybe a time to close this and do other additions later. Will be a nice challenge, I guess, to make for example a random lattice that is both atomic and co-atomic.

comment:13 Changed 5 years ago by jmantysalo

I have already thinked about adding random atomic, distributive, modular and semimodular lattices. However I think it is easier to first integrate this patch to Sage and continue after that. Then patches are of manageable size.

comment:14 Changed 5 years ago by jmantysalo

Just pinging. I think I did nothing very special after your comment "Otherwise it seems okay."

This would be nice to have, as this can used for testing other functions.

comment:15 Changed 5 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Sorry, forgot about this. Yes, LGTM now. Thanks.

comment:16 Changed 5 years ago by jmantysalo

Thanks! Hopefully this will be used to test and optimize other parts of lattices.py.

comment:17 Changed 5 years ago by vbraun

  • Branch changed from u/jmantysalo/random-lattice to 5fc39b08f9ad24d57296b2e35c7a0552f126f715
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.