# How to generate a random tree?

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]
]


-
Re: your edit, you can try using LayeredGraphPlot –  The Toad Oct 17 '12 at 21:10

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


-
The doc page for TreeGraph[] also gives some code for generating a random tree. –  Guess who it is. Oct 6 '12 at 9:42

You can make trees from horses and mazes ;-)

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]


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,
GraphStyle -> "ThickEdge", DirectedEdges -> False]


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. Connecting Towns Using Kruskal's Algorithm - Neat, random points in plane construction

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

3. Image processing - see above

4. Random expressions - see above

5. 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[#]} &)]


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]


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] & /@


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",
VertexShapeFunction -> ({PointSize[0], Point[#]} &)]


-

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"]]]


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

-

Similar to the one in the documentation. I just made it into a function so that you can specify the number of vertices.

randomTree[n_, opts___] :=
Graph[Range@n, # + 1 <-> RandomInteger[{1, #}] & /@ Range[n - 1], opts]

-