RenumberTree: Reorder tree edges and nodes

Description

Functions for systematically ordering the internal edges of trees.

Usage

RenumberTree(parent, child, weight)
RenumberEdges(parent, child, ...)
Cladewise(tree, nTip, edge)
# S3 method for phylo
Cladewise(tree, nTip = NTip(tree), edge = tree[["edge"]])
# S3 method for list
Cladewise(tree, nTip, edge)
# S3 method for multiPhylo
Cladewise(tree, nTip, edge)
# S3 method for matrix
Cladewise(tree, nTip = min(tree[, 1]) - 1L, edge)
# S3 method for `NULL`
Cladewise(tree, nTip = min(tree[, 1]) - 1L, edge)
ApePostorder(tree, nTip, edge)
# S3 method for phylo
ApePostorder(tree, nTip = NTip(tree), edge = tree[["edge"]])
# S3 method for list
ApePostorder(tree, nTip, edge)
# S3 method for `NULL`
ApePostorder(tree, nTip, edge)
# S3 method for multiPhylo
ApePostorder(tree, nTip, edge)
Postorder(tree, force = FALSE)
# S3 method for phylo
Postorder(tree, force = FALSE)
# S3 method for `NULL`
Postorder(tree, force = FALSE)
# S3 method for list
Postorder(tree, force = FALSE)
# S3 method for multiPhylo
Postorder(tree, force = FALSE)
# S3 method for numeric
Postorder(tree, force = FALSE)
PostorderOrder(tree)
# S3 method for phylo
PostorderOrder(tree)
# S3 method for numeric
PostorderOrder(tree)
Pruningwise(tree, nTip, edge)
# S3 method for phylo
Pruningwise(tree, nTip = NTip(tree), edge = tree[["edge"]])
# S3 method for list
Pruningwise(tree, nTip, edge)
# S3 method for multiPhylo
Pruningwise(tree, nTip, edge)
# S3 method for `NULL`
Pruningwise(tree, nTip, edge)
Preorder(tree)
# S3 method for phylo
Preorder(tree)
# S3 method for numeric
Preorder(tree)
# S3 method for multiPhylo
Preorder(tree)
# S3 method for list
Preorder(tree)
# S3 method for `NULL`
Preorder(tree)
TntOrder(tree)
TNTOrder(tree)
# S3 method for phylo
TntOrder(tree)
# S3 method for numeric
TntOrder(tree)
# S3 method for multiPhylo
TntOrder(tree)
# S3 method for list
TntOrder(tree)
# S3 method for `NULL`
TntOrder(tree)

Value

RenumberTree() returns an edge matrix for a tree of class phylo

following the preorder convention for edge and node numbering.

RenumberEdges() formats the output of RenumberTree() into a list whose two entries correspond to the new parent and child vectors, in preorder.

ApePostorder(), Cladewise(), Postorder(), Preorder() and Pruningwise() each return a tree of class phylo with nodes following the specified numbering scheme.

Postorder.numeric accepts a numeric matrix corresponding to the edge entry of a tree of class phylo, and returns a two-column array corresponding to tree, with edges listed in postorder

PostorderOrder() returns an integer vector. Visiting edges in this order will traverse the tree in postorder.

Arguments

parent: Integer vector corresponding to the first column of the edge matrix of a tree of class phylo, i.e. tree[["edge"]][, 1]
child: Integer vector corresponding to the second column of the edge matrix of a tree of class phylo, i.e. tree[["edge"]][, 2].
weight: Optional vector specifying the weight of each edge, corresponding to the edge.length property of a phylo object.
...: Deprecated; included for compatibility with previous versions.
tree: A tree of class phylo.
nTip: Integer specifying number of tips (leaves).
edge: Two-column matrix listing the parent and child of each edge in a tree, corresponding to tree[["edge"]]. Optional in Cladewise().
force: Logical specifying whether to rearrange trees already in postorder, in order to ensure edges are ordered in the "TreeTools" fashion.

Functions

Cladewise(): Reorder tree cladewise.
ApePostorder(): Reorder tree in Postorder using ape's postorder function, which is robust to unconventional node numbering.
Pruningwise(): Reorder tree Pruningwise.
Preorder(): Reorder tree in Preorder (special case of cladewise).
TntOrder(): Reorder tree in postorder, numbering internal nodes according to TNT's rules, which number the root node as nTip + 1, then the remaining nodes in the sequence encountered when traversing the tree in postorder, starting from each tip in sequence.

Author

Preorder() and Postorder(): Martin R. Smith.

Cladewise(), ApePostorder() and Pruningwise(): modified by Martin R. Smith from .reorder_ape() in ape (Emmanuel Paradis).

Details

Reorder() is a wrapper for ape:::.reorder_ape. Calling this C function directly is approximately twice as fast as using ape::cladewise or ape::postorder

Cladewise(), ApePostorder() and Pruningwise() are convenience functions to the corresponding functions in "ape". Single nodes may need to be collapsed using ape::collapse.singles first. "ape" functions can cause crashes if nodes are numbered unconventionally -- sometimes arising after using tree rearrangement functions, e.g. phangorn::SPR().

Preorder() is more robust: it supports polytomies, nodes may be numbered in any sequence, and edges may be listed in any order in the input tree. Its output is guaranteed to be identical for any tree of an equivalent leaf labelling (see RenumberTips()) and topology, allowing unique trees to be detected by comparing sorted edge matrices alone.

Nodes and edges in a preorder tree are numbered starting from the deepest node. Each node is numbered in the sequence in which it is encountered, and each edge is listed in the sequence in which it is visited.

At each node, child edges are sorted from left to right in order of the lowest-numbered leaf in the subtree subtended by each edge; i.e. an edge that leads eventually to tip 1 will be to the left of an edge leading to a subtree containing tip 2.

Numbering begins by following the leftmost edge of the root node, and sorting its descendant subtree into preorder. Then, the next edge at the root node is followed, and its descendants sorted into preorder, until each edge has been visited.

RenumberTree() and RenumberEdges() are wrappers for the C function preorder_edges_and_nodes(); they do not perform the same checks on input as Preorder() and are intended for use where performance is at a premium.

Postorder() numbers nodes as in Preorder(), and lists edges in descending order of parent node number, breaking ties by listing child nodes in increasing order. If a tree is already in postorder, it will not be rearranged unless force = TRUE.

Methods applied to numeric inputs do not check input for sanity, so should be used with caution: malformed input may cause undefined results, including crashing R.

Trees with >8191 leaves require additional memory and are not handled by Postorder() at present. If you need to process such large trees, please contact the maintainer for advice.