TreeShape: Integer representing shape of a tree

Description

Returns an integer that uniquely represents the shape of an n-tip binary tree, ignoring tip labels.

Usage

RootedTreeShape(tree)
RootedTreeWithShape(shape, nTip, tipLabels = rep("", nTip))
UnrootedTreeWithShape(shape, nTip, tipLabels = rep("", nTip))
UnrootedTreeWithKey(key, nTip, tipLabels = rep("", nTip))
UnrootedTreeShape(tree)
UnrootedTreeKey(tree)
.UnrootedKeys(nTip)
UnrootedKeys(..., envir = parent.frame())
NUnrootedShapes(nTip)
NRootedShapes(nTip)

Arguments

tree

A tree of class phylo.

shape

Integer specifying shape of tree, perhaps generated by TreeShape.

nTip

Integer specifying number of tips.

tipLabels

Character vector listing the labels assigned to each tip in a tree, perhaps obtained using TipLabels.

key

Integer specifying the key (not number) of an unrooted tree.

…

Value of nTip, to pass to memoized .UnrootedKeys.

envir

Unused; passed to addMemoization.

Value

TreeShape returns an integer specifying the shape of a tree, ignoring tip labels.

RootedTreeWithShape returns a tree of class phylo corresponding to the shape provided. Tips are unlabelled.

UnrootedTreeWithShape returns a tree of class phylo corresponding to the shape provided. Tips are unlabelled.

UnrootedTreeWithKey returns a tree of class phylo corresponding to the key provided. Tips are unlabelled.

UnrootedKeys returns a vector of integers corresponding to the keys (not shape numbers) of unrooted tree shapes with nTip tips. It is a wrapper to .UnrootedKeys, with memoization, meaning that results once calculated are cached and need not be calculated on future calls to the function.

TreeShapes returns an integer specifying the number of unique unrooted tree shapes with nTip tips.

RootedTreeShapes returns an integer specifying the number of unique rooted tree shapes with nTip tips.

Details

Rooted trees are numbered working up from the root.

The root node divides n tips into two subtrees. The smaller subtree may contain $a = 1, 2, ..., n/2$ tips, leaving $b = n - a$ tips in These options are worked through in turn.

For the first shape of the smaller subtree, work through each possible shape for the larger subtree. Then, move to the next shape of the smaller subtree, and work through each possible shape of the larger subtree.

Stop when the desired topology is encountered.

Unrooted trees are numbered less elegantly. Each cherry (i.e. node subtending a pair of tips) is treated in turn. The subtended tips are removed, and the node treated as the root of a rooted tree. The number of this rooted tree is then calculated. The tree is assigned a key corresponding to the lowest such value. The keys of all unrooted tree shapes on n tips are ranked, and the unrooted tree shape is assigned a number based on the rank order of its key among all possible keys, counting from zero.

If UnrootedTreeShape or UnrootedTreeKey is passed a rooted tree, the position of the root will be ignored.

Examples

Run this code

# NOT RUN {
RootedTreeShape(PectinateTree(8))
plot(RootedTreeWithShape(0, nTip = 8L))

NRootedShapes(8L)
# Shapes are numbered from 0 to NRootedShapes(n) - 1.  The maximum shape is:
RootedTreeShape(BalancedTree(8))

# Unique shapes of unrooted trees:
NUnrootedShapes(8L)

# Keys of these trees:
UnrootedKeys(8L)

# A tree may be represented by multiple keys.
# For a one-to-one correspondence, use a number instead:
allShapes <- lapply(seq_len(NUnrootedShapes(8L)) - 1L,
                    UnrootedTreeWithShape, 8L)
plot(allShapes[[1]])
sapply(allShapes, UnrootedTreeShape)
sapply(allShapes, UnrootedTreeKey) # Key >= number


# }