23
$\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$
5
  • $\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, 2012 at 14:21
  • $\begingroup$ @Szabolcs, yes. $\endgroup$ Jan 24, 2012 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, 2012 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, 2012 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$ Jan 24, 2012 at 14:44

3 Answers 3

28
$\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 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 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, 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$
6
  • $\begingroup$ +1 much neater than my suggestion. And hooray for recycling old posts :-) $\endgroup$
    – Heike
    Jan 24, 2012 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$ Jan 24, 2012 at 15:10
  • $\begingroup$ Nice solution, thanks a lot. $\endgroup$ Jan 24, 2012 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, 2012 at 16:06
  • 1
    $\begingroup$ @Mr.Wizard Thank you! I ought to pay more attention ... :S $\endgroup$
    – Szabolcs
    Jan 24, 2012 at 16:46
26
$\begingroup$

or you could do:

DirectedGraph[RandomGraph[{10, 10}], "Acyclic"]
$\endgroup$
2
  • 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, 2012 at 16:34
  • $\begingroup$ @Szabolcs I still prefer the algorithmically transparent way, so I keep my accept :) $\endgroup$ Oct 8, 2013 at 10:18
2
$\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$
2
  • 1
    $\begingroup$ Some code would be nice. $\endgroup$ Feb 16, 2013 at 16:56
  • 2
    $\begingroup$ Technically this is correct, but it generates exactly one isomorphism class of DAGs, which I doubt would satisfy anybody. $\endgroup$
    – whuber
    Feb 16, 2013 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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