# 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?) – Szabolcs Jan 24 '12 at 14:21 @Szabolcs, yes. – István Zachar Jan 24 '12 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. – Heike Jan 24 '12 at 14:32 @Heike I just realized I did this before, and that's where this came from --> codereview.stackexchange.com/questions/5307/… – Szabolcs Jan 24 '12 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. – István Zachar Jan 24 '12 at 14:44

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@
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 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 = 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 :-) – Heike Jan 24 '12 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. – István Zachar Jan 24 '12 at 15:10
Nice solution, thanks a lot. – István Zachar Jan 24 '12 at 15:11
+1 for nice coding – Mr.Wizard Jan 24 '12 at 15:34
@Mr.Wizard Thank you! I ought to pay more attention ... :S – Szabolcs Jan 24 '12 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 – Szabolcs Feb 24 '12 at 16:34