Opened 6 years ago
Closed 5 years ago
#17048 closed enhancement (fixed)
Faster Posets.RandomPoset
Reported by:  jmantysalo  Owned by:  

Priority:  minor  Milestone:  sage7.2 
Component:  combinatorics  Keywords:  
Cc:  chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  728cba8 (Commits)  Commit:  728cba835d97b721ca08c71bd93bff0ef3864215 
Dependencies:  Stopgaps: 
Description
Nathann Cohen wrote on another ticket:
"This code could be seriously rewritten, though. In two different ways:
1) Assume from the start that 0,...,n1 is a linear extension, and only add edges i,j with i<j. With this you don't have to call is_directed_acyclic
every second (and this is the bottleneck of the implementation). At the end, relabel everything randomly so that the linear extension is random, too
2) Work directly on the Hasse Diagram. Build the random Poset on n elements from a poset on n1 elements:
Consider all minimal elements m_1,...m_c
of the previous digraph and add the edges m_i,n
with probability p
. If some edge m_i
was not added, consider the immediate predecessors of m_i
and do the same with them.
This second way to build them benefits from the transitivity of posets.
The last algorithm was mentionned by Florent and Nicolas to which I asked the question. They seemed to think that this generation of random posets was not standard, and that we could change it a bit if we like, i.e. without caring if by changing the algorithm we change the distribution of posets. It seems that it is only there to provide random posets for computer tests, with no specific property in mind."
I add this on wishlistmilestone, so that I don't forget it totally. I'm not going to code this at least for release 6.4.
Change History (11)
comment:1 Changed 6 years ago by
comment:2 Changed 5 years ago by
 Branch set to u/jmantysalo/faster_posets_randomposet
comment:3 Changed 5 years ago by
 Cc chapoton added; ncohen removed
 Commit set to 3e3f42c5a9a003f27d354a5dc9e16216210b6836
 Milestone changed from sagewishlist to sage7.2
 Status changed from new to needs_review
This could be made still faster: just generate a random number of edges to add, instead of looping. However, this patch at least makes this five times faster.
New commits:
3e3f42c  Faster RandomPoset().

comment:4 Changed 5 years ago by
typo in propability
comment:5 Changed 5 years ago by
 Commit changed from 3e3f42c5a9a003f27d354a5dc9e16216210b6836 to 6c927f4df114410e44419fbaa50a19d8d6eed8a4
Branch pushed to git repo; I updated commit sha1. New commits:
6c927f4  Typo fix.

comment:6 followup: ↓ 8 Changed 5 years ago by
+ from random import shuffle
+
unused
comment:7 Changed 5 years ago by
 Commit changed from 6c927f4df114410e44419fbaa50a19d8d6eed8a4 to 728cba835d97b721ca08c71bd93bff0ef3864215
Branch pushed to git repo; I updated commit sha1. New commits:
728cba8  Removed unused import.

comment:8 in reply to: ↑ 6 Changed 5 years ago by
Replying to chapoton:
+ from random import shuffle
unused
True. I removed it.
...and now realized that shuffle
is as a Sage function, so it takes use of set_random_seed()
and could be used (So, what I was thinking??). But maybe it makes no real difference anyways, as it is much faster than creating the poset.
comment:9 Changed 5 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, good to go
comment:10 Changed 5 years ago by
Thanks again!
comment:11 Changed 5 years ago by
 Branch changed from u/jmantysalo/faster_posets_randomposet to 728cba835d97b721ca08c71bd93bff0ef3864215
 Resolution set to fixed
 Status changed from positive_review to closed
Maybe we could also generate random posets with given restrictions? For example
Calling this kind of functions could be something like
Posets.RandomPoset(20, 0.2, properties=['graded', 'connected', 'third_property'])
.