Create data structures for traversing a tree from root to tips, and for efficient retrieval of a node's outgoing edges and children.
get_tree_traversal_root_to_tips(tree, include_tips)A rooted tree of class "phylo". The root is assumed to be the unique node with no incoming edge.
Include tips in the tarversal queue. If FALSE, then only nodes are included in the queue.
A list with the following elements:
An integer vector of size Nnodes (if include_tips was FALSE) or of size Nnodes+Ntips (if include_tips was TRUE), listing indices of nodes (and optionally tips) in the order root-->tips described above. In particular, queue[1] will be the index of the tree's root (typically Ntips+1).
An integer vector of size Nedges (=nrow(tree$edge)), listing indices of edges (corresponding to tree$edge) such that outgoing edges of the same node are listed in consequtive order.
An integer vector of size Nnodes listing the location of the first outgoing edge of each node in edges. That is, edges[node2first_edge[n]] points to the first outgoing edge of node n in tree$edge.
An integer vector of size Nnodes listing the location of the last outgoing edge of each node in edges. That is, edges[node2last_edge[n]] points to the last outgoing edge of node n in tree$edge. The total number of outgoing edges of a node is thus given by 1+node2last_edge[n]-node2first_edge[n].
Many dynamic programming algorithms for phylogenetics involve traversing the tree in a certain direction (root to tips or tips to root), and efficient (O(1) complexity) access to a node's direct children can significantly speed up those algorithms. This function is meant to provide data structures that allow traversing the tree's nodes (and optionally tips) in such an order that each node is traversed prior to its descendants (root-->tips) or such that each node is traversed after its descendants (tips-->root). This function is mainly meant for use in other algorithms, and is probably of little relevance to the average user.
The tree may include multi-furcations as well as mono-furcations (i.e. nodes with only one child).
The asymptotic time and memory complexity of this function is O(Ntips), where Ntips is the number of tips in the tree.
# NOT RUN {
# generate a random tree
tree = generate_random_tree(list(birth_rate_factor=1), max_tips=100)$tree
# get tree traversal
traversal = get_tree_traversal_root_to_tips(tree, include_tips=TRUE)
# }
Run the code above in your browser using DataLab