title: Creating all strongly connected graphs with given in-degree with equal probability
body: <p>I am looking for a way to sample <strong>uniformly</strong> from the space of all <strong>strongly connected directed</strong> graphs (without self-loops) of <code>n</code> nodes and in-degree <code>k=(k_1,...,k_n), 1 &lt;= k_i &lt;= n-1</code>.</p>
  
  <p><strong>Input</strong></p>
  
  <ul>
  <li><code>n</code>, the number of nodes</li>
  <li><code>k = (k_1,...,k_n)</code>, where <code>k_i =</code> number of directed edges that enter node <code>i</code> (in-degree)</li>
  </ul>
  
  <p><strong>Output</strong></p>
  
  <ul>
  <li>a strongly connected directed graph of <code>n</code> nodes (without self-loops) with the given in-degrees <code>k_1,...,k_n</code> where each possible such graph is returned with the <strong>same</strong> probability.</li>
  </ul>
  
  <p>I am particularly interested in cases where <code>n</code> is large and <code>k_i</code> is small so that simply creating a graph and checking for strong connectedness is unfeasible because the probability is essentially <strong>zero</strong>.</p>
  
  <p>I looked through all sorts of papers and methods but couldn't find anything that deals with this problem.</p>