Iterate through all trees of a given size

Question

I often encounter the problem of checking some property of trees (graphic) of a given size with brute force. Do you have any good tricks for this? Ideally, I would like to study each class of isomorphism only once (but speed does it all matter).

Bit-tricks-tricks are welcome since n is usually less than 32 :)

I ask for slightly better algorithms than the similar "loop through all (n-1) -edge subsets and check if they form a tree" for trees on n nodes.

Answer 1

This is in the Knuth Art of Computer Programming book on combinatorial algorithms. If I remember correctly, this is an exercise. Since he has solutions for this, I point you there.

Answer 2

In some versions of googling, the following description of the algorithm appeared: http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf . They adapt the algorithm for enumerating root trees to enumerate non-Corte trees.

Others seem to have proven that this only requires amortized constant time per tree, and some performance measurements are shown in the PDF document to demonstrate this.