20
$\begingroup$

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]

Mathematica graphics

AcyclicGraphQ@graph

(* ==> True *)
$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – Szabolcs Jan 24 '12 at 14:21
  • $\begingroup$ @Szabolcs, yes. $\endgroup$ – István Zachar Jan 24 '12 at 14:24
  • $\begingroup$ 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. $\endgroup$ – Heike Jan 24 '12 at 14:32
  • $\begingroup$ @Heike I just realized I did this before, and that's where this came from --> codereview.stackexchange.com/questions/5307/… $\endgroup$ – Szabolcs Jan 24 '12 at 14:34
  • $\begingroup$ @Heike: I do that at the moment since I use small graphs, but I wanted to make the code general for future extensions. $\endgroup$ – István Zachar Jan 24 '12 at 14:44
23
$\begingroup$

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!)

Mathematica graphics

graph = AdjacencyGraph[adjacencyMatrix]

AcyclicGraphQ[graph]

(* ==> True *)

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

Mathematica graphics


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.

$\endgroup$
  • $\begingroup$ +1 much neater than my suggestion. And hooray for recycling old posts :-) $\endgroup$ – Heike Jan 24 '12 at 14:47
  • $\begingroup$ 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. $\endgroup$ – István Zachar Jan 24 '12 at 15:10
  • $\begingroup$ Nice solution, thanks a lot. $\endgroup$ – István Zachar Jan 24 '12 at 15:11
  • $\begingroup$ 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? $\endgroup$ – Mr.Wizard Jan 24 '12 at 16:06
  • 1
    $\begingroup$ @Mr.Wizard Thank you! I ought to pay more attention ... :S $\endgroup$ – Szabolcs Jan 24 '12 at 16:46
20
$\begingroup$

or you could do:

DirectedGraph[RandomGraph[{10, 10}], "Acyclic"]
$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Szabolcs Feb 24 '12 at 16:34
  • $\begingroup$ @Szabolcs I still prefer the algorithmically transparent way, so I keep my accept :) $\endgroup$ – István Zachar Oct 8 '13 at 10:18
1
$\begingroup$

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)
$\endgroup$
  • 1
    $\begingroup$ Some code would be nice. $\endgroup$ – István Zachar Feb 16 '13 at 16:56
  • 1
    $\begingroup$ Technically this is correct, but it generates exactly one isomorphism class of DAGs, which I doubt would satisfy anybody. $\endgroup$ – whuber Feb 16 '13 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.