# How to generate random directed acyclic graphs?

How to programmatically build random directed acyclic graphs (DAG)? I know about the AcyclicGraphQ predicate and the TopologicalSorting function, though Mathematica does not offer any algorithm to create such networks. Anyone has some experience in this topic?

The following random method does not guarantee that the result will be acyclic:

graph = RandomGraph[{10, 10}, DirectedEdges -> True]


AcyclicGraphQ@graph

(* ==> True *)

• Do you mean how to generate random DAGs? What do you need them for, how "random" do they need to be (do you need a uniform distribution, i.e. each allowed graph is equally probable)? What are your input parameters? (Connectance and vertex count?) Jan 24, 2012 at 14:21
• @Szabolcs, yes. Jan 24, 2012 at 14:24
• A brute force way would be to keep generating graphs until an acyclic one turns up although it's probably not the most efficient way. Jan 24, 2012 at 14:32
• @Heike I just realized I did this before, and that's where this came from --> codereview.stackexchange.com/questions/5307/… Jan 24, 2012 at 14:34
• @Heike: I do that at the moment since I use small graphs, but I wanted to make the code general for future extensions. Jan 24, 2012 at 14:44

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

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

vertexCount = 10;
edgeCount = 30;

elems = RandomSample@
vertexCount (vertexCount - 1)/2]

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


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 connectivity 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 = RandomSample@
PadRight[ConstantArray[1, edgeCount], vertexCount (vertexCount - 1)/2];
Take[
FoldList[RotateLeft, elems, Range[0, vertexCount - 2]],
All,
vertexCount
] ~LowerTriangularize~ -1;
]


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

• +1 much neater than my suggestion. And hooray for recycling old posts :-) Jan 24, 2012 at 14:47
• No, connectedness is not a requirement here! Though, in the long run, it would be nice to include it as an option to the function (something like: UnconnectedVertices -> False), but at the moment, I do need such unconnected nodes. Jan 24, 2012 at 15:10
• Nice solution, thanks a lot. Jan 24, 2012 at 15:11
• I was thinking about how I would improve this code, and I found that it seemed very familiar. I then realized that I had done this before for your question on Code Review. I see you did not use the FoldList form I answered with; do you dislike it? Jan 24, 2012 at 16:06
• @Mr.Wizard Thank you! I ought to pay more attention ... :S Jan 24, 2012 at 16:46

or you could do:

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

• What this does corresponds to zeroing out the adjacency matrix below the diagonal, so it is equivalent to my approach and will generate graphs with the same distribution. But it is much more concise, +1 Feb 24, 2012 at 16:34
• @Szabolcs I still prefer the algorithmically transparent way, so I keep my accept :) Oct 8, 2013 at 10:18