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 (LcaLookup &&)=default
	LcaLookup (LcaLookup const &other)=default
	LcaLookup (Tree const &tree)
	~LcaLookup ()=default
size_t	operator() (size_t node_index_a, size_t node_index_b) const
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) const
TreeNode const &	operator() (TreeNode const &node_a, TreeNode const &node_b, TreeNode const &root_node) const
LcaLookup &	operator= (LcaLookup &&)=default
LcaLookup &	operator= (LcaLookup const &other)=default

Constructor & Destructor Documentation

LcaLookup() [1/4]

LcaLookup ( )

default

LcaLookup() [2/4]

LcaLookup ( Tree const &  tree )

explicit

Definition at line 51 of file lca_lookup.cpp.

~LcaLookup()

~LcaLookup ( )

default

LcaLookup() [3/4]

LcaLookup ( LcaLookup const &  other )

default

LcaLookup() [4/4]

LcaLookup ( LcaLookup &&  )

default

Member Function Documentation

operator()() [1/4]

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

Definition at line 72 of file lca_lookup.cpp.

operator()() [2/4]

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

Definition at line 61 of file lca_lookup.cpp.

operator()() [3/4]

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

Definition at line 77 of file lca_lookup.cpp.

operator()() [4/4]

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

Definition at line 66 of file lca_lookup.cpp.

operator=() [1/2]

LcaLookup& operator= ( LcaLookup &&  )

default

operator=() [2/2]

LcaLookup& operator= ( LcaLookup const &  other )

default

---

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

• lca_lookup.hpp
• lca_lookup.cpp