Random tree with specific branching factor in Mathematica

Question

Do you know if it's possible to somehow generate a random tree graph with a specific branching factor? I don't want it to be a k-ary tree.

It would be also great if I could define both the branching factor and the maximum depth. I want to randomly generate a bunch of trees that would differ in branching factor and depth.

TreePlot with random integer input returns something that's almost what I want:

TreePlot[RandomInteger[#] -> # + 1 & /@ Range[0, 100]]

but I can't figure out a way to get a tree with a specific branching factor.

Thanks!

Answer 1

I guess I'm a bit late, but I like the question. Instead of creating a tree in the form

{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}

I will use the following form of nested calls, where every argument is a child, which represents another node

0[1[2, 3, 4], 5]

Both forms are equivalent and can be transformed into each other.

Row[{
  TreeForm[0[1[2, 3, 4], 5]],
  TreePlot[{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}]
  }]

Here is how the algorithm works: As arguments we need a function f which gives a random number of children and is called when we create a node. Additionally, we have a depth d which defines the maximum depth a (sub-)tree can have.

1. [Choose branching] Define a branching function f which can be called like f[] and returns a random number of children. If you want a tree with either 2 or 4 children, you could use e.g. f[] := RandomChoice[{2, 4}]. This function will be called for each created node in the tree.

2. [Choose tree-depth] Choose a maximum depth d of the tree. At this point, I'm not sure what you want the randomness to be incorporated into the generation of the tree. What I do here is that when a new node is created, the depth of the tree below it is randomly chosen between the depth of its parent minus one and zero.

3. [Create ID Counter] Create a unique counter variable count and set it to zero. This will give us increasing node ID's. When creating a new node, it is increased by 1.

4. [Create a node] Increase count and use it as node-ID. If the current depth d is zero, give back a leaf with ID count, otherwise call f to decide how many children the node should get. For every new child chose randomly the depth of its sub-tree which can be 0,...,d-1 and call 4. for each new child. When all recursive calls have returned, the tree is built.

Fortunately, in Mathematica-code this procedure is not so verbose and consists only of a few lines. I hope you can find in the code what I have described above

With[{counter = Unique[]},
 generateTree[f_, d_] := (counter = 0; builder[f, d]);
 builder[f_, d_] := Block[
   {nodeID = counter++, childs = builder[f, #] & /@ RandomInteger[d - 1, f[]]},
   nodeID @@ childs
 ];
 builder[f_, 0] := (counter++);
]

Now you can create a random tree like follows

branching[] := RandomChoice[{2, 4}];
t = generateTree[branching, 6];
TreeForm[t]

Or if you like you can use the next function to convert the tree into what is accepted by TreePlot

transformTree[tree_] := Module[{transform},
  transform[(n_Integer)[childs__]] := (Sow[
     n -> # & /@ ({childs} /. h_Integer[__] :> h)]; 
    transform /@ {childs});
  Flatten@Last@Reap[transform[tree]
]

and use it to create many random trees

trees = Table[generateTree[branching, depth], {depth, 3, 7}, {5}];
GraphicsGrid[Map[TreePlot[transformTree[#]] &, trees, {2}]]