furnasI {treebalance}

Calculation of the Furnas rank for rooted binary trees

Description

This function calculates the Furnas rank F(T) for a given rooted binary tree T. F(T) is the unique rank of the tree T among all rooted binary trees with n leaves in the left-light rooted ordering. For details on the left-light rooted ordering as well as details on how the Furnas rank is computed, see "The generation of random, binary unordered trees" by G.W. Furnas (1984) or "Tree balance indices: a comprehensive survey" by Fischer et al. (2023). The Furnas rank is a balance index.

The concept of assigning each rooted binary tree a unique tuple (rank, n) allows to store many trees with minimal storage use.

For details on the Furnas rank, see also Chapter 22 in "Tree balance indices: a comprehensive survey" (https://doi.org/10.1007/978-3-031-39800-1_22).

Usage

furnasI(tree)

Arguments

tree

A rooted binary tree in phylo format.

Value

furnasI returns the unique Furnas rank of the given tree, i.e. the rank of the tree among all rooted binary trees with n leaves in the left-light rooted ordering. Since the values can get quite large, the function returns them in big.z format (package gmp).

Author(s)

Luise Kuehn, Lina Herbst

References

G. W. Furnas. The generation of random, binary unordered trees. Journal of Classification, 1984. doi: 10.1007/bf01890123. URL https://doi.org/10.1007/bf01890123.

M. Kirkpatrick and M. Slatkin. Searching for evolutionary patterns in the shape of a phylogenetic tree. Evolution, 1993. doi: 10.1111/j.1558-5646.1993.tb02144.x.

Examples

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