get_tree_traversal_root_to_tips {castor} | R Documentation |
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)
tree |
A rooted tree of class "phylo". The root is assumed to be the unique node with no incoming edge. |
include_tips |
Include tips in the tarversal queue. If FALSE, then only nodes are included in the queue. |
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.
A list with the following elements:
queue |
An integer vector of size Nnodes (if |
edges |
An integer vector of size Nedges ( |
node2first_edge |
An integer vector of size Nnodes listing the location of the first outgoing edge of each node in |
node2last_edge |
An integer vector of size Nnodes listing the location of the last outgoing edge of each node in |
Stilianos Louca
## 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) ## End(Not run)