totPathLen {treebalance}

Calculation of the total path length for rooted trees

Description

This function calculates the total path length TPL(T) for a given rooted tree T. The tree must not necessarily be binary. TPL(T) is defined as

TPL(T)=\sum_{x\in V(T)} \delta(x)

in which V(T) denotes the set of vertices of T, and \delta(x) denotes the depth of the vertex x. The total path length is an imbalance index.

For n=1 the function returns TPL(T)=0 and a warning.

For details on the total path length, see also Chapter 23 in "Tree balance indices: a comprehensive survey" (https://doi.org/10.1007/978-3-031-39800-1_23).

Usage

totPathLen(tree)

Arguments

tree

A rooted tree in phylo format.

Value

totPathLen returns the total path length of the given tree.

Author(s)

Luise Kuehn

References

see e.g. R. P. Dobrow, J. A. Fill. Total path length for random recursive trees. Combinatorics, Probability and Computing, 8(4):317–333, 1999. doi: 10.1017/S0963548399003855.

see e.g. L. Takacs. On the total heights of random rooted trees. Journal of Applied Probability, 29(3):543–556, 1992. doi: 10.2307/3214892.

see e.g. L. Takacs. On the total heights of random rooted binary trees. Journal of Combinatorial Theory, Series B, 61(2):155–166, 1994. ISSN 0095-8956. doi: 10.1006/jctb.1994.1041.

Examples

tree <- ape::read.tree(text="((((,),),(,)),(((,,),),(,)));")
totPathLen(tree)