How to generate a random tree?

Question

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

Answer 1

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

Answer 2

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, 
 ImagePadding -> {{1, 35}, {0, 10}}, GraphLayout -> "RadialDrawing", 
 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. 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[#]} &)]

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] & /@ 
(AdjacencyMatrix /@ rg)

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

Answer 3

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

Answer 4

Most of the existing answers do not sample uniformly from the set of labelled trees.

IGraph/M now has a function which guarantees uniform sampling, IGTreeGame. It implements two methods: conversion from a random Prüfer sequence (J.M.'s answer) and loop-erased random walk on a complete graph (a more efficient implementation of the method from my other answer).

It also supports directed trees (out-trees). Use these if you need a random rooted tree.

IGTreeGame[10, DirectedEdges -> True, 
 GraphLayout -> "LayeredDigraphEmbedding"]

Finally, there is also a function for the uniform sampling of the spanning trees of arbitrary graphs (IGRandomSpanningTree). I showed a demo in this answer.

Answer 5

The answer by @rm -rf is simple, but it does not sample uniformly on the set of all labelled trees (it can't generate some of them).

A good solution is the one mentioned by @J.M.: create a random Prüfer sequence, and convert it to a tree.

An alternative solution that is slower, but simpler to implement, and also samples uniformly, is to use a loop-erased random walk on a graph. This procedure can sample spanning trees uniformly. If we run it on the complete graph, it will sample all labelled trees uniformly.

Here's an implementation:

cRandomTree = Compile[{{n, _Integer}},
   Block[{
     visited = Table[0, {n}], (* for each node, 1=visited, 0=unvisited *)
     edges = Table[0, {n - 1}, {2}], (* preallocate *)
     i, j, k
     },

    (* select the starting node of the walk *)
    i = RandomInteger[{1, n}];
    visited[[i]] = 1;

    k = 1; (* number of already visited nodes *)
    While[k < n,
     j = RandomInteger[{1, n}];
     If[visited[[j]] == 0,
      visited[[j]] = 1;
      edges[[k++]] = {i, j};
      ];
     i = j;
     ];
    edges
    ]
   ];

Options[randomTree] = Options[Graph];
randomTree[n_?Internal`NonNegativeIntegerQ, opt : OptionsPattern[]] :=
  Graph[Range[n], cRandomTree[n], DirectedEdges -> False, opt]

Here's a test to show that it does indeed sample uniformly on the set of labelled trees:

Table[
    randomTree[4],
    {50000}
    ] // CountsBy[AdjacencyMatrix] // KeySort // BarChart

Furthermore, we can check that there are $16 = 4^{4-2}$ distinct trees generated, which is the total number of labelled trees on 4 nodes.

---

The algorithm in plain English:

• let the tree nodes be labelled by integers 1..n
• generate a sequence of random integers (i.e. nodes)
• whenever a node appears in this sequence for the first time, it is connected with an edge to the previous node in the sequence
• keep doing this until all nodes have been connected up

The algorithm could be made more efficient by choosing only yet-unconnected nodes when appropriate.

Answer 6

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]