4
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ +1. I prefer the first variant. $\endgroup$ Commented 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$ Commented Feb 28, 2021 at 17:02
  • $\begingroup$ Thank you. I'll try it. $\endgroup$ Commented 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$ Commented 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$ Commented Feb 28, 2021 at 18:45

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.