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

Improve this question
$\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
    Commented Nov 11, 2020 at 18:50
  • $\begingroup$ Will do!! Thanks for the help! $\endgroup$
    – Madeline Brandt
    Commented Nov 12, 2020 at 16:06

1 Answer 1

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks so much for your answer. This is fantastic! $\endgroup$
    – Madeline Brandt
    Commented Nov 12, 2020 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
    Commented Nov 12, 2020 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
    Commented Nov 12, 2020 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
    Commented Nov 12, 2020 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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