Creating a random tree?

Question

What is a good way of creating a random tree (or an adjacency matrix that satisfies tree properties)? I currently have the following data structure that I am returning but I would like to generate this randomly. Any suggestions?

    return [{
        Source: "A1",
        Target: "A2",
    }, {
        Source: "A2",
        Target: "A3",
    }, {
        Source: "A1",
        Target: "A4",
    }, {
        Source: "A4",
        Target: "A6",
    }, {
        Source: "A4",
        Target: "A7",
    }, {
        Source: "A3",
        Target: "A8",
    }, {
        Source: "A3",
        Target: "A5",
    }];

Answer 1

A tree with n nodes can be uniquely expressed by a sequence of n-2 integer numbers (in the range of [0, n-1]). This is called the Prüfer sequence.

Creating a random sequence should be no problem. Then you just have to transform the sequence to your tree structure and you're done.

Answer 2

Developing on the above idea, here is how we can generate a 20-node labeled random tree (in python):

1. start from a randomly generated length-18 sequence with each element chosen from the set {1,2,...,20}.
2. use the generated string as Prufer sequence for the spanning tree for the complete graph K20 on 20 vertices and generate the corresponding labeled tree (since there is a 1-1 correspondence always) using the following algorithm (from here).

The next code snippet implements the above algorithm to generate a labeled tree (by computing the edges) given the prufer sequence:

def get_tree(S):
    n = len(S)
    L = set(range(1, n+2+1))
    tree_edges = []
    for i in range(n):
        u, v = S[0], min(L - set(S))
        S.pop(0)
        L.remove(v)
        tree_edges.append((u,v))
    tree_edges.append((L.pop(), L.pop()))
    return tree_edges

Now, we can always generate a prufer sequence (of length n-2) randomly and subsequently generate the corresponding spanning tree (on n vertices), which can serve as our random tree (can be thought of to be randomly sampled from the set of n^(n-2) spanning trees of Kn).

n = 20 # Kn with n vertices
N = 25 # generate 25 random trees with 20 vertices (as spanning trees of K20)
for i in range(N):
    S = np.random.choice(range(1,n+1), n-2, replace=True).tolist()
    T_E = get_tree(S) # the spanning tree corresponding to S
    # plot the tree generated (with `networkx`, e.g.,)

The next animation shows a few such randomly generated labeled trees with 20 nodes.