Opened 6 years ago

Closed 5 years ago

#17048 closed enhancement (fixed)

Faster Posets.RandomPoset

Reported by: jmantysalo Owned by:
Priority: minor Milestone: sage-7.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,...,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.

Change History (11)

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)
        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']).

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:

3e3f42cFaster 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:

6c927f4Typo fix.

comment:6 follow-up: 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:

728cba8Removed unused import.

comment:8 in reply to: ↑ 6 Changed 5 years ago by 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.

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

comment:10 Changed 5 years ago by jmantysalo

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.