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",
    }];

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",
    }];

• javascript
• python-3.x
• algorithm
• graph
• graph-theory

• When you say random.. Do you mean balanced tree? – smk Commented Feb 14, 2013 at 15:33
• @SajitKunnumkal: Actually, anything is fine. Preferably something which has more leaf nodes but other than that I don't really have any preference. – Legend Commented Feb 14, 2013 at 15:36

2 Answers 2

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.

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 plete 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 puting 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.