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)
DeleteDuplicatesBy[trees, CanonicalGraph]
. It will be much faster because it does not do pairwise comparisons. $\endgroup$