Find all non-isomorphic trees with $n$ nodes

Question

I would like to compute all non-isomorphic trees with n nodes efficiently. I use the following approach: I create all possible trees ( Visualizing Cayley's Formula in Mathematica) and filter the list of all possible trees.

fun[code_] := 
 Module[{v = Range[Length[code] + 2], cd = code, e = {}, c},
  While[
   Length[v] != 2,
   c = Sort[Complement[v, cd]];
   AppendTo[e, {cd[[1]], c[[1]]}];
   v = DeleteCases[v, c[[1]]];
   cd = Drop[cd, 1];];
  Graph[UndirectedEdge @@@ AppendTo[e, v], VertexSize -> 0.3, 
   VertexLabels -> 
    Table[i -> Placed[Style[i, White, Bold], {1/2, 1/2}], {i, 
      v[[-1]]}], 
   VertexStyle -> 
    Table[i -> ColorData["Rainbow"][i/v[[-1]]], {i, v[[-1]]}]]]

checkIsomorph[start_ : {}] := Module[{outList, check}, outList = start;
  Function[{seedling}, 
   If[(check = FreeQ[outList, _?(IsomorphicGraphQ[seedling, #] &)]), 
    AppendTo[outList, seedling]];
   check]]

n = 5;
graphs = fun[#] & /@ Tuples[Range[n], n - 2];
selected = checkIsomorph[] /@ graphs;

Any suggestion on how to do it faster?

Edit: I would like to be able to compute up to n=20.

Answer 1

I am using the IGraph/M package for this answer.

Approach 1:

Generate Prüfer sequences, convert to trees, filter duplicates based on canonical labelling.

In[17]:= Needs["IGraphM`"]

In[18]:= n = 7;

In[19]:= DeleteDuplicatesBy[
   IGFromPrufer /@ Tuples[Range[n], n - 2],
   CanonicalGraph
   ] // Length // AbsoluteTiming

Out[19]= {2.0961, 11}

Update: We can eliminate some equivalent Prüfer sequences by exploiting certain symmetries. For example, the numbers in the Prüfer sequence are effectively vertex indices. Shuffling the vertices would create isomorphic trees. Exploiting this, as well as the way Tuples works (which causes the first half of its output to be the same as the second half, up to relabelling), we can do

In[65]:= takeHalf[list_] := Take[list, Ceiling[Length[list]/2]]

In[66]:= n = 9;
ps = Join @@ Table[
    takeHalf@Select[Tuples[Range[k], {n - 2}], Length@Union[#] == k &],
    {k, n - 2}
    ];

In[68]:= DeleteDuplicatesBy[IGFromPrufer /@ ps, CanonicalGraph] // 
  Length // AbsoluteTiming

Out[68]= {3.3142, 47}

This is a very naïve approach. I am sure that thinking a bit more about what the Prüfer sequences of isomorphic trees look like would allow one to achieve much better performance.

Approach 2 (much faster):

Install the nauty suite and use gentreeg. I have these tools installed in /opt/local/bin on my machine.

In[20]:= IGImport["!/opt/local/bin/gentreeg 7", "Sparse6"] // 
  Length // AbsoluteTiming

Out[20]= {0.020838, 11}

You can also do this with Import instead of IGImport, but it will be somewhat slower.