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.

Is it possible to generate a random tree without explicitly constructing a random adjacency matrix that satisfies tree properties? How about a random directed tree?


Edit: incredible answer by Vitaliy! What I wanted was somewhat simpler and rm -rf's answer largely pointed me in the right direction. One thing to note is that the TreeGraph functions (new in version 8), while easy to use, seem to be lacking some functionality compared to the older TreePlot family of functions. In particular, I wanted to make sure that the root of my tree is displayed at the top, and I could not find a way to do it with TreeGraph -- please correct me if I missed something! Here is the illustration (notice how TreeGraph puts node 1 at the top):

Block[{edges, p1, p2},
 edges = Table[DirectedEdge[RandomInteger[{0, i - 1}], i], {i, 1, 8}];
 p1 = TreeGraph[edges, GraphStyle -> "DiagramBlack"] ;
 p2 = TreePlot[edges /. {DirectedEdge -> Rule}, Top, 0, 
   DirectedEdges -> True, 
   VertexRenderingFunction -> ({White, EdgeForm[Black], Disk[#, .1], 
       Black, Text[#2, #1]} &)];
 GraphicsGrid[{{p1, p2}}, ImageSize -> 800]
 ]

tree visualization

share|improve this question
    
Re: your edit, you can try using LayeredGraphPlot –  rm -rf Oct 17 '12 at 21:10
add comment

3 Answers 3

up vote 14 down vote accepted

Here is one way of doing it based on an example in TreePlot. We create a function to generate a random set of edges and form a graph as:

vtx[] := Table[i <-> RandomInteger[{0, i - 1}], {i, 1, 50}];
Graph@vtx[]

Generate several:

Table[Graph@vtx[], {12}] ~Partition~ 4 // Grid

share|improve this answer
    
The doc page for TreeGraph[] also gives some code for generating a random tree. –  J. M. Oct 6 '12 at 9:42
add comment

You can make trees from horses and mazes ;-)

maze to tree

horse to tree

Images for these can be found in documentation for SkeletonTransform and MorphologicalGraph.

Actually, trees are everywhere. Arbitrary expressions have the structure of arbitrary trees. Imagine taking an integral:

Integrate[Sin[(1 - x)/(1 + x)], x]

integral of Sin[(1 - x)/(1 + x)]

This will give you a pretty random tree if you apply algorithm from this answer - I am giving only the final line with styles here:

Graph[edges, VertexLabels -> First@labels, 
 ImagePadding -> {{1, 35}, {0, 10}}, GraphLayout -> "RadialDrawing", 
 GraphStyle -> "ThickEdge", DirectedEdges -> False]

tree from expression

Now on a more serious note: There are probably quite a few different ways to do this. In addition to @rm -rf's answer, I mention 6 other possibilities.

  1. Random Tree Aggregation

  2. Connecting Towns Using Kruskal's Algorithm - Neat, random points in plane construction

  3. Tree Form of Recursive Function Evaluation Steps - can give a key to another approach

  4. Image processing - see above

  5. Random expressions - see above

  6. Randomly cut a perfect tree.

You can generate a complete tree of specified number of levels and branches. Here is a tree of 7 levels and 3 branches:

g = CompleteKaryTree[7, 3, GraphStyle -> "LargeNetwork", 
  GraphLayout -> "RadialDrawing", VertexShapeFunction -> ({PointSize[0], Point[#]} &)]

k-ary tree with 7 levels and 3 branches

Then drop a controlled number of edges, and select the largest connected component. Here are a few random samples like that:

rg = Subgraph[g, Sort[ConnectedComponents[
       Graph[RandomSample[#, Round[Length[#] .6]] &@EdgeList[g]]], 
      Length@#1 > Length@#2 &][[1]], GraphStyle -> "LargeNetwork", 
    GraphLayout -> "RadialDrawing"] & /@ Range[12]

random subgraphs of k-ary tree

Note that I use "RadialDrawing" layout everywhere, which is good for large trees. Of course you can use the standard one:

AdjacencyGraph[#, GraphStyle -> "LargeNetwork", AspectRatio -> .5] & /@ 
(AdjacencyMatrix /@ rg)

adjacency graph

Still, the radial one is excellent for large trees:

g = CompleteKaryTree[10, 4, GraphStyle -> "LargeNetwork", 
   GraphLayout -> "RadialDrawing", VertexShapeFunction -> ({PointSize[0], Point[#]} &)];

Subgraph[g, Sort[ConnectedComponents[
    Graph[RandomSample[#, Round[Length[#] .45]] &@EdgeList[g]]], 
   Length@#1 > Length@#2 &][[1]], GraphStyle -> "LargeNetwork", 
 GraphLayout -> "RadialDrawing", 
 VertexShapeFunction -> ({PointSize[0], Point[#]} &)]

subgraph of k-ary tree

share|improve this answer
add comment

The Combinatorica package has a function CodeToLabeledTree[] for generating trees from their corresponding Prüfer codes. Since the old function was adapted for Combinatorica Graph[] objects, as opposed to the built-in Graph[] objects introduced in version 8, some modification of the code in the package is needed:

CodeToLabeledTree[l_List, opts___] := Module[{m = Range[Length[l] + 2], x, i}, 
   TreeGraph[Append[
             Table[x = Min[Complement[m, Drop[l, i - 1]]]; m = Complement[m, {x}]; 
                   UndirectedEdge @@ Sort[{x, l[[i]]}], {i, Length[l]}], 
             UndirectedEdge @@ Sort[m]], opts]] /; Complement[l, Range[Length[l] + 2]] == {}

From this, you can generate a random tree like so:

With[{n = 50}, (* number of vertices *)
 BlockRandom[SeedRandom[42, Method -> "MersenneTwister"]; (* for reproducibility *)
  CodeToLabeledTree[RandomInteger[{1, n}, n - 2], GraphLayout -> "SpringEmbedding"]]]

random graph from Prüfer code

(The Combinatorica function RandomTree[] is implemented in this way.)

share|improve this answer
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.