3
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ +1. I prefer the first variant. $\endgroup$
    – user64494
    Feb 28, 2021 at 15:59
  • 2
    $\begingroup$ @user64494 The second one just calls a purpose-made external tool to do the job, but it will be much, much faster. I highly recommend the tools from the nauty suite. $\endgroup$
    – Szabolcs
    Feb 28, 2021 at 17:02
  • $\begingroup$ Thank you. I'll try it. $\endgroup$
    – user64494
    Feb 28, 2021 at 17:04
  • $\begingroup$ @Szabolcs Thank you for the answer. Your first approach is faster than mine but is the same in the concept. I am interested in the problem with $n$ up to 20. Your first approach doesn't work on my PC (and, of cause my one). I am looking for another concept of solution, this is a reason that I do not accept your answer. $\endgroup$ Feb 28, 2021 at 17:46
  • 2
    $\begingroup$ @KirilDanilchenko Why don't you use the second approach then? On my computer it takes less than a second and generates 823065 trees. $\endgroup$
    – Szabolcs
    Feb 28, 2021 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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