A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LcaLookup Class Reference

#include <genesis/tree/function/lca_lookup.hpp>

Detailed Description

Fast lookup of the lowest common ancestor (LCA) of two TreeNodes, relative to an arbitrary root node.

The class offers to look up the LCA of two TreeNodes. It can use the root node of the Tree as base to consider which nodes are "lower", or any arbitrary other node of the tree. See operator() for the lookup functions.

Internally, the class uses a RangeMinimumQuery (RMQ) and indices of nodes during an eulertour() of the tree. This makes it fast even for large trees.

Caveat: The Tree object is referenced from inside this class. Its livetime thus needs to be longer than an instance of this class.

Definition at line 66 of file lca_lookup.hpp.

Public Member Functions

 LcaLookup ()=default
 
 LcaLookup (Tree const &tree)
 
 LcaLookup (LcaLookup const &other)=default
 
 LcaLookup (LcaLookup &&)=default
 
 ~LcaLookup ()=default
 
std::size_t operator() (size_t node_index_a, size_t node_index_b, size_t root_index) const
 
TreeNode const & operator() (TreeNode const &node_a, TreeNode const &node_b, TreeNode const &root_node) const
 
size_t operator() (size_t node_index_a, size_t node_index_b) const
 
TreeNode const & operator() (TreeNode const &node_a, TreeNode const &node_b) const
 
LcaLookupoperator= (LcaLookup const &other)=default
 
LcaLookupoperator= (LcaLookup &&)=default
 

Constructor & Destructor Documentation

LcaLookup ( )
default
LcaLookup ( Tree const &  tree)
explicit

Definition at line 50 of file lca_lookup.cpp.

~LcaLookup ( )
default
LcaLookup ( LcaLookup const &  other)
default
LcaLookup ( LcaLookup &&  )
default

Member Function Documentation

size_t operator() ( size_t  node_index_a,
size_t  node_index_b,
size_t  root_index 
) const

Definition at line 60 of file lca_lookup.cpp.

TreeNode const & operator() ( TreeNode const &  node_a,
TreeNode const &  node_b,
TreeNode const &  root_node 
) const

Definition at line 65 of file lca_lookup.cpp.

size_t operator() ( size_t  node_index_a,
size_t  node_index_b 
) const

Definition at line 71 of file lca_lookup.cpp.

TreeNode const & operator() ( TreeNode const &  node_a,
TreeNode const &  node_b 
) const

Definition at line 76 of file lca_lookup.cpp.

LcaLookup& operator= ( LcaLookup const &  other)
default
LcaLookup& operator= ( LcaLookup &&  )
default

The documentation for this class was generated from the following files: