How to generate random directed acyclic graphs?

Note that @halmir's solution does the same thing as described below, but much more concisely. I recommend using that approach.

---

The idea is that the graph is acyclic if and only if if there exists a vertex ordering which makes the adjacency matrix lower triangular¹. It's easy to see that if the adjacency matrix is lower triangular, then vertex $i$ can only be pointing to vertex $j$ if $i<j$.

So let's generate a matrix which has zeros and ones uniformly distributed under the diagonal:

vertexCount = 10;
edgeCount = 30;

elems = RandomSample@
  PadRight[ConstantArray[1, edgeCount], 
   vertexCount (vertexCount - 1)/2]

adjacencyMatrix = 
  Take[
    FoldList[RotateLeft, elems, Range[0, vertexCount - 2]],
    All,
    vertexCount
  ] ~LowerTriangularize~ -1

(Thanks to @Mr.Wizard for the code that fills the triangular matrix!)

graph = AdjacencyGraph[adjacencyMatrix]

AcyclicGraphQ[graph]

(* ==> True *)

LayeredGraphPlot will show you the acyclic structure in a "convincing" way:

---

You did not say it explicitly, but I assume you need a connected graph. Unfortunately I have no algorithm that gives you a connected one, but you can keep generating them until you find a connected one by accident (brute force). If the connectance is very low, and you get very few connected ones, you can try generating graphs with a slightly higher vertex count than the required one until the largest connected component has the required vertex count.

---

Packed into a function for convenience:

randomDAG[vertexCount_, edgeCount_] /; 
  edgeCount < vertexCount (vertexCount - 1)/2 :=
 Module[
   {elems, adjacencyMatrix},
   elems = RandomSample@
     PadRight[ConstantArray[1, edgeCount], vertexCount (vertexCount - 1)/2];
   adjacencyMatrix = 
     Take[
       FoldList[RotateLeft, elems, Range[0, vertexCount - 2]],
       All,
       vertexCount
     ] ~LowerTriangularize~ -1;
   AdjacencyGraph[adjacencyMatrix]
 ]

---

¹ You can find the ordering that makes the adjacency matrix triangular using a topological sort.

or you could do:

DirectedGraph[RandomGraph[{10, 10}], "Acyclic"]

What about this?

• Shuffle and rank all nodes using any random criteria. O(N)
• Connect all higher nodes with all lower nodes. O(N^2)