4
$\begingroup$

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): enter image description here

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.

$\endgroup$
2
  • $\begingroup$ If you find IGraph/M useful, and make significant use of it, a citation would be appreciated ;-) Not required, but appreciated. $\endgroup$ – Szabolcs Nov 11 '20 at 18:50
  • $\begingroup$ Will do!! Thanks for the help! $\endgroup$ – Madeline Brandt Nov 12 '20 at 16:06
6
$\begingroup$

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]]

enter image description here

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

enter image description here

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.

$\endgroup$
4
  • $\begingroup$ Thanks so much for your answer. This is fantastic! $\endgroup$ – Madeline Brandt Nov 12 '20 at 16:07
  • $\begingroup$ @MadelineBrandt Another idea, which might lead to (much) faster solutions is to start by generating only the non-isomorphic trees of the type you need (there are two in your example), then label them in all possible ways, finally filter out labellings which are equivalent with IGBlissCanonicalGraph. To generate these, you can use the geng tool from the nauty suite. Something like this: Select[ IGImport["!/opt/local/bin/geng 10 9:9 -c -D3", "Nauty"], FreeQ[VertexDegree[#], 2] & ]. I have geng installed in /opt/local/bin/geng, but it will likely differ for your machine. $\endgroup$ – Szabolcs Nov 12 '20 at 16:17
  • $\begingroup$ @MadelineBrandt The command generates all non-isomorphic graphs with 10 vertices, at least and at most 9 edges (9:9) which are connected (-c) and have maximum degree 3 (-D3). This still gives some trees with degree-2 vertices are filtered out with the Select. $\endgroup$ – Szabolcs Nov 12 '20 at 16:19
  • $\begingroup$ Thanks. I think I will end up needing to do something like this, because for my purposes I also want to exclude certain cases (which appear quite often). For example, I don't like graphs containing a vertex with two leaves, where one leaf is "labelled" and one leaf is "unlabelled" (in the example this takes 9 down to 3). Since this situation happens a lot, it might be easier as you say to first make all non-isomorphic trees, then add the labellings (in ways that I deem allowable), and then filter out equivalent ones. $\endgroup$ – Madeline Brandt Nov 12 '20 at 17:18

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.