Generating strongly-connected, uniformly-distributed, random di-graphs

Question

So I've been building a program that uses Monte Carlo simulations to find properties of evolutionary graph theory. One of the key functions of this is to be able to generate uniformly-distributed random graphs, so that we can determine the generalised properties of graphs. For the case of connected undirected graphs I have implemented the solution outlined in this answer.

However for directed graphs, generating the one-directional uniform spanning tree you get from Wilson's algorithm doesn't ensure that the graph is strongly-connected, and it seems that adding extra edges to make the spanning tree bi-directional would introduce a bias into the graphs that you generate.

I feel like I might be missing something obvious/misunderstanding something, but essentially my request is, can someone recommend to me a high-level scheme that allows me to generate strongly-connected, uniformly-distributed, random di-graphs?

Answer 1

The most straightforward solution I can think of is to randomly generate uniformly-distributed digraphs and reject any that are not strongly connected. That will preserve uniform distribution and guarantee the property that you want. It's probably not terribly efficient but you'll know for sure if you run some tests.

Answer 2

Can someone recommend to me a high-level scheme that allows me to generate strongly-connected, uniformly-distributed, random di-graphs?

I had a similar problem generating expression trees for test data. I found that if you find out how to count unique trees then the problem becomes easy. What I mean by that is that I found for full binary trees with N internal nodes the number of unique trees based on N is the Catalan Numbers. Then for binary trees that have unary branches with N total nodes the number of unique trees based on N is the Motzkin Numbers.

Then I found The On-Line Encyclopedia of Integer Sequences®. So if you know a value, N, that can uniquely identify a graph and you know the corresponding count of unique graphs for that N and put those counts into a the OEIS search you should get back a page that will help you in your search. e.g. Catalan Numbers for full binary trees or Motzkin Numbers for regular binary tress. Along the way I found that one of the keys to generating them was a recurrence relation.

Or you can use keywords in the search but this may not get an exact hit. I only found Motzkin numbers using the number sequence and not via keywords.

Here is an OEIS query for strongly connected digraph

Now if you know the count for a given N and you either generate all graphs for a given N or can have a one to one correspondence between a value and the graph then you just generate random integers and get/generate the corresponding graph. If I understand your problem correctly this should solve it.

My best guess to the OEIS sequence for this question is:

Number of acyclic digraphs with n unlabeled nodes. A003087

Which has a reference to Uniform random generation of large acyclic digraphs

TL;DR

For some related history see my question: Algorithm improvement for enumerating binary trees