getDescMatrix {treebalance}

Auxiliary functions

Description

getDescMatrix - Creates a matrix that contains the descendants of node i in row i.

getAncVec - Creates a vector that contains the parent (direct ancestor) of node i at position i.

getNodesOfDepth - Creates a matrix that contains the nodes of depth i in row i.

symBucketLexicoSort - Sorts the pairs of numbers lexicographically and returns ranking. Uses bucket sort.

getAllAncestors - Returns all ancestors of v including v itself.

cPL_inv - Returns the binary tree that belongs to the input label in an incomplete Newick format.

maxDepthLeaf - Returns the maximumy< depth of a leaf in the subtree that is rooted at v.

get.subtreesize - Creates a vector that contains at the i-th position the number of leaves in the pending subtree rooted at i.

getlca - Returns the name of the lowest common ancestor of the two input vertices v and w.

we_eth - Returns the Wedderburn-Etherington number we(n) for a given non-negative integer n.

getfurranks - Returns for each vertex i the Furnas rank of the subtree rooted at i.

getsubtree - Returns the pending subtree (in phylo format) that is rooted at the input vertex. If the input vertex is a leaf, the function returns the standard tree for n=1 (with 1 edge).

is_binary - Returns TRUE if the input tree is binary and FALSE otherwise.

is_phylo - Tests all requirements of the phylo format, and returns TRUE if the tree is correctly formatted, else FALSE with detailed feedback on the features that are not met.

tree_decomposition - Returns a list of length two, which contains the two pending subtrees that are rooted at the children of the root of the input tree. The smaller one (according to the number of leaves) is stated first.

tree_merge - Returns a rooted tree T in phylo format, which contains the input trees tree1 and tree2 as "left" and "right" maximal pending subtrees.

treenumber - Returns the unique tree number tn(T) of the given tree. tn(T) is the rank of the tree T among all rooted binary trees in the left-light rooted ordering. It can be calculated as follows:

tn(T)=F(T) + \sum_{i=1}^{n-1} we(i)

in which n is the number of leaves in T, F(T) is the Furnas rank of T, i.e. the rank of T in the left-light rooted ordering of all rooted binary trees with n leaves, and we(i) is the Wedderburn-Etherington number of i. The concept of assigning each rooted binary tree a unique tree number allows to store many trees with minimal storage use. For n=1 the function returns tn(T)=1 and a warning.

treenumber_inv - Returns the unique tree (in phylo format) for the given tree number.

auxE_l_X - Returns the sum of all products of l different values in X.

Usage

getDescMatrix(tree)

getAncVec(tree)

getNodesOfDepth(mat, root, n)

symBucketLexicoSort(workLabs)

getAllAncestors(tree, v)

cPL_inv(label)

maxDepthLeaf(tree, v = length(tree$tip.label) + 1)

get.subtreesize(tree)

getlca(tree, v, w)

we_eth(n)

getfurranks(tree)

getsubtree(tree, subroot)

is_binary(tree)

is_phylo(tree)

tree_decomposition(tree)

tree_merge(tree1, tree2)

treenumber(tree)

treenumber_inv(treenum)

auxE_l_X(subX, Xset)

Arguments

tree

A rooted tree in phylo format, >= 2 leaves

mat

Descendants matrix from getDescMatrix

root

Number (label) of the root of the tree

n

Number of leaves of the tree

workLabs

numeric matrix (2 columns)

v

A vertex of the tree.

label

A Colijn-Plazotta label of desired tree, a positive integer.

w

A vertex of the tree.

subroot

A vertex of the tree. It is not recommended to use leaves as subroots.

tree1

A rooted tree in phylo format.

tree2

A rooted tree in phylo format.

treenum

An integer denoting the tree number of the sought tree.

subX

integer >=1, size of the subsets of X.

Xset

Vector (multiset) of numeric values.

Value

desc_mat numeric matrix

anc_vec numeric vector

nodes_of_depth numeric matrix

ranking numeric vector

vectorWithAncs numeric vector

Author(s)

Sophie Kersting, Luise Kuehn and Lina Herbst

Examples

mat <- cbind(c(7,7,6,5,5,6),c(1,2,3,4,6,7))
tree <- list(edge=mat, tip.label=c("","","",""), Nnode=3)
getDescMatrix(tree)
mat <- cbind(c(5,5,5,5),c(1,2,3,4))
tree <- list(edge=mat, tip.label=c("","","",""), Nnode=1)
getDescMatrix(tree)
getAncVec(tree)
getNodesOfDepth(mat=getDescMatrix(tree),root=length(tree$tip.label)+1,
n=length(tree$tip.label))
myWorkLabs <- cbind(c(0,1,2,3,1,0),c(0,2,2,4,1,0))
symBucketLexicoSort(myWorkLabs)
getAllAncestors(tree,v=6)
cPL_inv(label=6)
maxDepthLeaf(tree,v=6)
get.subtreesize(tree)
getlca(tree,1,2)
we_eth(5)
getfurranks(tree)
getsubtree(tree,4)
is_binary(ape::read.tree(text="((((,),),(,)),(((,),),(,)));"))
is_phylo(ape::read.tree(text="((((,),),(,)),(((,),),(,)));"))
tree_decomposition(ape::read.tree(text="((((,),),(,)),(((,),),(,)));"))
treeA <- ape::read.tree(text="(((,),),(,));")
treeB <- ape::read.tree(text="((,),);")
tree_merge(treeA, treeB)
treenumber(ape::read.tree(text="((((,),),(,)),(((,),),(,)));"))
treenumber_inv(192)
auxE_l_X(subX=3,Xset=c(1,1,2,2))