Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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 *)
share|improve this question
    
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
add comment

3 Answers

up vote 17 down vote accepted

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.

share|improve this answer
    
+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
1  
@Mr.Wizard Thank you! I ought to pay more attention ... :S –  Szabolcs Jan 24 '12 at 16:46
show 2 more comments

or you could do:

DirectedGraph[RandomGraph[{10, 10}], "Acyclic"]
share|improve this answer
1  
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
    
@Szabolcs I still prefer the algorithmically transparent way, so I keep my accept :) –  István Zachar Oct 8 '13 at 10:18
add comment

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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