37
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Re: your edit, you can try using LayeredGraphPlot $\endgroup$ – rm -rf Oct 17 '12 at 21:10
24
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The doc page for TreeGraph[] also gives some code for generating a random tree. $\endgroup$ – J. M. will be back soon Oct 6 '12 at 9:42
  • $\begingroup$ @J.M. and R.M. The problem with these methods is that they do not sample uniformly. To be precise, they do generate all possible outcome with the same probability. However, they are not capable of generating all labelled trees. (And if we consider unlabelled ones, then they do not sample uniformly at all—but I guess doing that would be a rather hard problem.) $\endgroup$ – Szabolcs Apr 5 '18 at 15:01
39
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In version 10 or later,we shoul add a option GraphLayout-> "LayeredEmbedding".Suggestion you add in your answer to help read. $\endgroup$ – yode Apr 4 '16 at 20:39
  • $\begingroup$ @Vitaliy my trees are different, I have a Mathematica 10.4 , How to do this like your trees? $\endgroup$ – vito Jun 22 '16 at 22:46
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, this one does sample uniformly. But I really wonder if there's a more direct way, without having to use Prüfer codes. $\endgroup$ – Szabolcs Apr 5 '18 at 15:03
  • $\begingroup$ @Szabolcs, would you happen to know of a direct method? It has been a while since I looked at the lit, but all I've seen used Prüfer codes as an intermediate step... $\endgroup$ – J. M. will be back soon Apr 7 '18 at 21:43
  • $\begingroup$ I found something called loop-erased random walks, which can uniformly sample spanning trees. If we do it on a complete graph, we can generate uniformly distributed random trees. $\endgroup$ – Szabolcs Apr 8 '18 at 11:34
  • 1
    $\begingroup$ I posted another answer. $\endgroup$ – Szabolcs Apr 8 '18 at 12:44
7
$\begingroup$

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

Mathematica graphics

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

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

enter image description here

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.

$\endgroup$
6
$\begingroup$

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

enter image description here

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.

$\endgroup$
2
$\begingroup$

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]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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