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?
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
For some related history see my question: Algorithm improvement for enumerating binary trees