6
$\begingroup$

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:

enter image description here

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)

$\endgroup$
  • $\begingroup$ It seems that you have a non-recursive algorithm to generate the trees -- can you make it recursive? Meaning, can you turn your current algorithm to find n-level trees from (n-1)-levels trees? Can you post your code? $\endgroup$ – Anton Antonov Jul 12 '17 at 15:15
  • $\begingroup$ For the last step, use DeleteDuplicatesBy[trees, CanonicalGraph]. It will be much faster because it does not do pairwise comparisons. $\endgroup$ – Szabolcs Nov 14 '18 at 20:02
2
$\begingroup$

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} *)
$\endgroup$

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.