Opened 6 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:  sage7.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: 
Description (last modified by )
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
 Branch set to u/jmantysalo/randomlattice
comment:2 Changed 5 years ago by
 Cc tscrim chapoton added
 Commit set to 60eff31087c3784f997ae2f49bd5150e676fad85
 Description modified (diff)
 Milestone changed from sagewishlist to sage7.4
 Status changed from new to needs_review
comment:3 followup: ↓ 4 Changed 5 years ago by
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 futureproof 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 ; followup: ↓ 5 Changed 5 years ago by
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 castproperties
into a list. You should also futureproof your code by checkingproperties[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 nonisomorphic 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 ; followup: ↓ 6 Changed 5 years ago by
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 castproperties
into a list. You should also futureproof your code by checkingproperties[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 typey
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 andp=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 nonisomorphic 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
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 andp=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 meetsemilattice, inversed as a joinsemilattice 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 nonisomorphic 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
 Commit changed from 60eff31087c3784f997ae2f49bd5150e676fad85 to cd7104619519cee19b5c741888870d96d53f6ed2
Branch pushed to git repo; I updated commit sha1. New commits:
cd71046  Add random planar lattices.

comment:8 Changed 5 years ago by
 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 followup: ↓ 12 Changed 5 years ago by
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
 Commit changed from cd7104619519cee19b5c741888870d96d53f6ed2 to 07ea77dcc7c146c652732ee269f72f6448d9d1ff
Branch pushed to git repo; I updated commit sha1. New commits:
07ea77d  Some random :=) changes.

comment:11 Changed 5 years ago by
 Commit changed from 07ea77dcc7c146c652732ee269f72f6448d9d1ff to 5fc39b08f9ad24d57296b2e35c7a0552f126f715
Branch pushed to git repo; I updated commit sha1. New commits:
5fc39b0  Minor correction.

comment:12 in reply to: ↑ 9 Changed 5 years ago by
 Status changed from needs_work to needs_review
Replying to tscrim:
I think you should make
known_properties
into aset
for faster checking. (Actually, to still have your desired error message, you could doif 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 saysp=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 coatomic.
comment:13 Changed 5 years ago by
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
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
 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
Thanks! Hopefully this will be used to test and optimize other parts of lattices.py
.
comment:17 Changed 5 years ago by
 Branch changed from u/jmantysalo/randomlattice to 5fc39b08f9ad24d57296b2e35c7a0552f126f715
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Add random lattice generation.