Faster Posets.RandomPoset

[jmantysalo]

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.

[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)
        G.add_edge(prev, r)
    # 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)
            G.add_edge(r, e)
    # 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:
                G.add_edge(e1, e2)
    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']).

[jmantysalo]

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().

[chapoton]

typo in propability

[git]

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

​6c927f4

Typo fix.

[chapoton]

+        from random import shuffle
+

unused

[git]

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

​728cba8

Removed unused import.

[jmantysalo]

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.

[chapoton]

ok, good to go

[jmantysalo]

Thanks again!