9
$\begingroup$

Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes in the linear arrangement of the tree. Let the length sequence $L$ of $T$ be the sorted sequence of lengths of all the edges in $T$.

An example tree is shown below. Each edge is marked with its length. The length sequence for this tree is $(1, 1, 1, 1, 2, 2, 3)$.

Example tree

My question is: Given a length sequence $L$, is there an efficient algorithm to generate a labeled tree $T$ with length sequence $L$, randomly at uniform from the set of all such trees? Or failing that, to enumerate the set of trees with a given length sequence $L$?

To clarify, here is an extremely inefficient algorithm that does what I want. We have a desired length sequence $L$, let's say (1,1,1,1,2,2,3). To generate a random tree with the desired edge lengths:

  1. Generate a random labeled tree $T$ on $n=8$ nodes by sampling a random Prüfer code.
  2. Check if the length sequence of $T$ matches $L=(1,1,1,1,2,2,3)$. If yes, accept $T$. If not, goto 1.

This is very inefficient because there are $n^{n-2}$ possible trees generated in step 1, and only a very small number of those trees matches the desired $L$, especially as the trees get large.

Update: I have an algorithm that seems to work, but it seems like it could be made more efficient.

Algorithm:

  1. Let $T$ be a graph with nodes $V$ and empty edge set $E$.

  2. For each possible edge length $l$ in $\{1, \dots, \text{max}(L)\}$,

  3. Let $k$ be the number of entries in $L$ matching $l$. So for example, if $L=(1,1,1,1,2,2,3)$ and $l=1$, then $k=4$.

  4. If $k=0$, skip to the next $l$.

  5. Generate the set of possible new edges $P = \{(u,v) : u \in V, v \in V, (u,v) \not\in E, u = v+l \text{ or } u = v-l\}$

  6. If $P$ is empty, fail and start over again from 1.

  7. Generate the set $Q$ of all combinations of size $k$ of elements of $P$

  8. Randomly choose an element of $Q$, which is a set of $k$ edges. Add this set of edges to $E$.

  9. If the resulting $T$ is not a forest, fail and start over again from 1. Otherwise, continue to the next $l$.

Basically, this generates the random graphs matching $L$, then filters them to be trees.

$\endgroup$
  • $\begingroup$ My gut tells me the combinatorial explosion for this problem is absolutely massive. It sounds very hard, but perhaps someone else will know a clever trick. $\endgroup$ – orlp Oct 23 '19 at 22:27
1
$\begingroup$

I'm not entirely sure of what you're asking for, but I think it might be one of these three:

Permutations that preserve topological structure
The tree you listed in parenthetical notation is (5 (2 (1 4) ) (3) (5 (6 (7 (8) ) ) ). Are you looking for permutations of this tree structure, because you can simply calculate all n! permutations of nodes and put them in the same tree structure:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (5) (4 (3 (1 (2) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (2 (3) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (3 (2) ) ) )
...
(This would yield 362,880 distinct trees).

Note, this class of trees would preserve the sequences of lengths of the current tree. Now, if you have an array of these, simply use a good PRNG.

Permutations that calculate topological isomorphisms
It also would preserve topological properties, so if you want to generate other isomorphic topologies, then you can take the structure of the tree and do permutations on the sequences at the same level. Hence:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (4 (3 (2 (1) ) ) (5) )
(9 (5) (8 (7 6) ) (4 (3 (2 (1) ) ) )
(9 (5) (4 (3 (2 (1) ) ) (8 (7 6) ) )
...
(This will be a variable number of permutations, in this case (3!(1!)(2!)(1!)) or 12 trees.)

Permutations that calculate equivalent lengths

Let your tree be [1 2[1 4] 3 4 *5[2 3 6] 6[7] 7[8] 8] where * represents root, and nodes inside of brackets are pointers. Notice it's possible to calculate lengths by taking the absolute value of the difference between nodes (2[4]->2[[2]] The node two which points to [node four] is a node that has an [[edge length 2]]). Then use [1 2[[1 2]] 3 4 *5[[3 2 1]] 6[[1]] 7[[1]] 8 9] -> {1, 1, 1, 1, 2, 3}. Now we can simply replicate this by traversing the original tree and constructing isomorphisms of length. Hence:

  1. Determine root
    Rnd(1-9)->3 -> [1 2 *3 4 5 6 7 8]
  2. Permute first level by taking three lengths and finding candidates
    [1 2 *3[[3 2 1]] 4 5 6 7 8 9]-> (note three lengths)
    [3]±[[3]]->{0,6} (0 is invalid so don't push on the stack)
    [3]±[[2]]->{1,5}
    [3]±[[1]]->{2,4}
    Note we need to select P(2,1) on all three sets iteratively.
    So, randomly, one permutation is {6,1,4} :[1[] 2 *3[1 4 6] 4[] 5 6[] 7 8].
  3. Call this recursively on [1], [4], [6] over the set {with [[1], [[1]], and [[1 2]] with the base case being any tree that satisfies {1, 1, 1, 1, 2, 3}.

Now, I think that preserving the lengths as a function of order of the sequence might yield a very small set, because certain trees, might only have a single isomorphism. Consider:

(1 (2 (3 (4 (5 (6 (7 (8)))))))) ~ (8 (7 (6 (5 (4 (3 (2 (1))))))))
{1 1 1 1 1 1 1} = {1 1 1 1 1 1 1}

There's only one isomophism because of the way a tree when considering edges whose lengths are caculated from sequences partitions. In fact, every tree done in this manner might have at most 1, but I'd have to think about how to prove that after implementing code.

Let me know what you think; if you can clarify what you're seeking, I might be able to help.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The last one is the closest to what I'm asking. What you're describing is how to take a directed labeled tree T and generate a random linear arrangement of T that preserves the edge lengths. What I'm asking for in this question is not a random linear arrangement, but a random tree structure that matches the edge lengths (without preserving topology). In fact, the random linear arrangement problem here is also interesting to me, and I'm going to ask it in a separate question. $\endgroup$ – Richard Futrell Oct 30 '19 at 16:10

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.