Opened 6 years ago
Last modified 5 years ago
#20495 closed enhancement
Add a function to generate random lattice (poset) — at Version 8
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  combinatorics  Keywords:  latticeposet 
Cc:  tscrim, chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/jmantysalo/randomlattice (Commits, GitHub, GitLab)  Commit:  cd7104619519cee19b5c741888870d96d53f6ed2 
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 (8)
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.
New commits:
Add random lattice generation.