Compute all trees on a given label set

Question

Given a set of labels {a_1,...,a_n} (with some labels possibly appearing multiple times) I would like to efficiently compute all trees with n leaves labelled {a_1,...,a_n} and 2n-2 nodes.  This is equivalent to trees with n leaves labelled {a_1,...,a_n} where all interior (non-leaf) vertices are trivalent. I only wish to produce all trees up to graph isomorphisms that preserve the labels.
For example, the output for {a,a,a,a,1,2} would be the following 8 trees (edit: there should be 9, see solution below):

This is similar to a question I have asked in the past, but now I am adding in some labels where I do care about ordering and some where I do not care about ordering. One (probably non-optimal strategy) would be to produce all of the trees using the code listed there, then produce all of the labellings of those trees (yikes) and then somehow test whether there is a graph isomorphism preserving the labels to eliminate duplicates (I am also not sure yet about how to do this last step).
This seems very inefficient, so I am wondering if there is a better way.
I have thought about trying to use Groupings for this, but I have not yet figured out a way to make it work.

Szabolcs · Accepted Answer

Unfortunately, I don't have time to figure out a full answer, but here are some tips which may help. They require my IGraph/M, which you should find generally useful if you work on such problems.
We can generate all such labelled trees using Prüfer sequences. The degree of a vertex is equal to the number of times it appears in the Prüfer sequence plus one. Let use label interior nodes with $1, 2, ..., n-2$. Then you can use
n=6;
trees = IGFromPrufer[#, GraphStyle -> "DiagramGold"] & /@ Permutations[Join[#, #] & @ Range[n]]

A smarter way to generate Prüfer sequences would significantly reduce the number of generated duplicates.
This list of trees of course has a lot of duplicates you don't want since the interior nodes are indistiguishable and so are some of the leaves.
Use the same method as in my other answer, but use IGBlissCanonicalGraph, which supports colouring. Use your labels the set "colours" for the leaves.
result = DeleteDuplicates[
   IGBlissCanonicalGraph[{#, 
       "VertexColors" -> {0, 0, 0, 0, 1, 2, 3, 3, 3, 3}}] & /@ trees];

Graph[#, GraphStyle -> "DiagramGold", GraphLayout -> "SpringEmbedding"] & /@ 
 IGVertexMap[Placed[#, Center] &, VertexLabels -> IGVertexProp["Color"]] /@ 
  result

I represented "a" from your example with 3.

UPDATE:
Here's one way to significantly reduce the number of Prüfer sequences by generating fewer equivalent ones:
pseqs = Module[{i = 1}, # /. {0 :> i++}] & /@ 
   Cases[{0, ___}]@Permutations[Join[ConstantArray[0, n - 2], Range[n - 2]]];

trees = IGFromPrufer /@ pseqs;

This makes it actually usable for n=7.

Compute all trees on a given label set

One Answer

Add your own answers!

Ask a Question