Opened 6 years ago

Closed 5 years ago

# Faster Posets.RandomPoset

Reported by: Owned by: jmantysalo minor sage-7.2 combinatorics chapoton Jori Mäntysalo Frédéric Chapoton N/A 728cba8 (Commits) 728cba835d97b721ca08c71bd93bff0ef3864215

### 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,...,n-1 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 n-1 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 wishlist-milestone, so that I don't forget it totally. I'm not going to code this at least for release 6.4.

### comment:1 Changed 6 years ago by jmantysalo

Maybe we could also generate random posets with given restrictions? For example

```# Graded poset

# set_random_seed(0)
from sage.misc.prandom import random
from sage.misc.randstate import current_randstate
dice=current_randstate()

n=20
prob=0.2
# Too many 1-element levels... make better.
levels=Partitions(n).random_element()
p=Permutations(len(levels)).random_element()
levels=[levels[x-1] for x in p]

# Poset P will have 0..levels[0] as minimal element,
# levels[0]..levels[1]-1 covering them and so on.
G=DiGraph({x:[] for x in range(0,n)})
prev_start=0
prev_end=levels[0]

for i in levels[1:]:
# Connect every element of previous level to some element on this level
for prev in range(prev_start, prev_end):
r=randint(prev_end, prev_end+i-1)
# Connect every element of this level to some element on previous level
for e in range(prev_end, prev_end+i):
if G.in_degree(e) == 0:
r=randint(prev_start, prev_end-1)
# And now the random part
for e1 in range(prev_start, prev_end):
for e2 in range(prev_end, prev_end+i):
if dice.c_rand_double() < prob:
prev_start=prev_end
prev_end=prev_end+i
P=Poset(G);
```

Calling this kind of functions could be something like `Posets.RandomPoset(20, 0.2, properties=['graded', 'connected', 'third_property'])`.

### comment:2 Changed 5 years ago by jmantysalo

• Branch set to u/jmantysalo/faster_posets_randomposet

### comment:3 Changed 5 years ago by jmantysalo

• Authors set to Jori Mäntysalo
• Cc chapoton added; ncohen removed
• Commit set to 3e3f42c5a9a003f27d354a5dc9e16216210b6836
• Milestone changed from sage-wishlist to sage-7.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 chapoton

typo in `propability`

### comment:5 Changed 5 years ago by git

• Commit changed from 3e3f42c5a9a003f27d354a5dc9e16216210b6836 to 6c927f4df114410e44419fbaa50a19d8d6eed8a4

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

 ​6c927f4 `Typo fix.`

### comment:6 follow-up: ↓ 8 Changed 5 years ago by chapoton

```+        from random import shuffle
+
```

unused

### comment:7 Changed 5 years ago by git

• 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 jmantysalo

```+        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 chapoton

• Reviewers set to Frédéric Chapoton
• Status changed from needs_review to positive_review

ok, good to go

Thanks again!

### comment:11 Changed 5 years ago by vbraun

• Branch changed from u/jmantysalo/faster_posets_randomposet to 728cba835d97b721ca08c71bd93bff0ef3864215
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.