Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to randomly generate trees, i.e. undirected acyclic graphs with a single root, making sure that all possible trees with a fixed number of nodes n are equally likely.

share|improve this question

2 Answers 2

Knuth says to look at it as generating all nested parentheses in lexicographic order.

Look here for the details

http://www-cs-faculty.stanford.edu/~uno/fasc4a.ps.

share|improve this answer
1  
I think that link should just be www-cs-faculty.stanford.edu/~uno/fasc4a.ps. Somehow you got the Google tracking page in there when you copied the link. –  Ben Alpert Jul 25 '10 at 15:55
    
Fixed, thanks Ben –  Jonathan Fischoff Jul 25 '10 at 19:28
    
And now there's no http://, which you need to make it a link. (I had it in my comment but it was stripped out.) –  Ben Alpert Jul 25 '10 at 19:38
    
Eric Lippert has been doing a series on something similar - blogs.msdn.com/b/ericlippert/archive/2010/04/22/…, which might be an interesting read. –  dsolimano Jul 26 '10 at 3:00
    
I only read the first few sentences but its interesting that binary tree's are Catalan numbers, I knew triangulations were, but either learned that and forgot or never knew. –  Jonathan Fischoff Jul 26 '10 at 4:36
up vote 0 down vote accepted

To generate a random tree you can use the following algorithm, where dst and src are two stacks:

dst := random permutation of all nodes;
src := empty stack
src.push(dst.pop()); % picks the root
while (!dst.empty()) {
  a := random element from src;
  b := dst.pop();
  add the edge (a, b)
  src.push(b);
}

Proof of correctness (all trees are possible and equally likely): Alexey S. Rodionov and Hyunseung Choo, On Generating Random Network Structures: Trees, ICCS 2003, LNCS 2658, pp. 879-887, 2003.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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