How to efficiently compute all trees with n leaves and 2n-2 nodes

Question

I would like to efficiently compute all trees with n leaves and 2n-2 nodes. This is equivalent to trees with n leaves where all interior (non-leaf) vertices are trivalent.

The input should be the number n and the output should be a list consisting of graphs.

For example, the output for 6 would be:

Ideally I would like to be able to compute up to n=19 or 20. This would give 11020 trees.

Right now I have an extremely slow method which starts from a tree with n leaves and one central node, and then "grows" the interior edges in all ways, and then removes the isomorphic / redundant trees in the end. This allows me to go up to n=10.

Update: Here is the best I have come up with so far...

First there is a command for making a tree object into a graph object (see another one of my questions).

    makeTree[nodes_] := 
     Module[{counter = 0}, 
      traverse[h_[childs___]] := 
       With[{id = 
          counter}, {UndirectedEdge[id, ++counter], 
           traverse[#]} & /@ {childs}];
      traverse[_] := Sequence[];
      Graph[#] &@Flatten[traverse[nodes]]]

Then I make all rooted trees using Groupings:

   AllRootedTrees[n_] := 
   makeTree /@ TreeForm /@ Groupings[Table[a, n - 1], {2, Orderless}]

Then, I remove the isomorphic duplicates:

  AllTrees[n_] := 
  DeleteDuplicates[AllRootedTrees[n], IsomorphicGraphQ[#1, #2] &]

The last step is probably very inefficient but this is the fastest method I have so far.

(the computation for 15 trees takes 25.2 seconds)

Answer 1

I think your code is good. The serious bottleneck is removing isomorphic duplicates. The efficient way to do this is

DeleteDuplicatesBy[graph, CanonicalGraph]

CanonicalGraph will canonically order/label vertices, so that it always maps isomorphic graphs to the same expression (which is also a Graph).

With this sole change,

AllTrees[n_] := DeleteDuplicatesBy[AllRootedTrees[n], CanonicalGraph]

the timing is

AllTrees[20] // Length // AbsoluteTiming
(* {39.6098, 11020} *)