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

<p>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 <a href="https://en.wikipedia.org/wiki/Catalan_number" rel="nofollow noreferrer">Catalan Numbers</a>. Then for binary trees that have unary branches with N total nodes the number of unique trees based on N is the <a href="https://en.wikipedia.org/wiki/Motzkin_number" rel="nofollow noreferrer">Motzkin Numbers</a>. </p>

<p>Then I found <a href="http://oeis.org/" rel="nofollow noreferrer">The On-Line Encyclopedia of Integer Sequences®</a>. 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. <a href="http://oeis.org/A000108" rel="nofollow noreferrer">Catalan Numbers</a> for full binary trees or <a href="http://oeis.org/A001006" rel="nofollow noreferrer">Motzkin Numbers</a> for regular binary tress. Along the way I found that one of the keys to generating them was a <a href="https://en.wikipedia.org/wiki/Recurrence_relation" rel="nofollow noreferrer">recurrence relation</a>. </p>

<p>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.</p>

<p>Here is an OEIS query for <a href="http://oeis.org/search?q=+strongly+connected+digraph+&amp;sort=&amp;language=&amp;go=Search" rel="nofollow noreferrer">strongly connected digraph</a></p>

<p>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. </p>

<p>My best guess to the OEIS sequence for this question is:</p>

<p>Number of acyclic digraphs with n unlabeled nodes. <a href="https://oeis.org/A003087" rel="nofollow noreferrer">A003087</a></p>

<p>Which has a reference to <a href="https://arxiv.org/pdf/1202.6590.pdf" rel="nofollow noreferrer">Uniform random generation of large acyclic digraphs</a></p>

<h2>TL;DR</h2>

<p>For some related history see my question: <a href="https://stackoverflow.com/q/42627198/1243762">Algorithm improvement for enumerating binary trees</a></p>
Generating strongly-connected, uniformly-distributed, random di-graphs
<p>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 <a href="https://stackoverflow.com/a/14618505">this</a> answer. </p>

<p>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. </p>

<p>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?</p>