Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.

Public Member Functions  
LowestCommonAncestor (const RootedTree &tree_)  
Stores the tree and precomputs "up lifts".  
int  lowest_common_ancestor (int u, int v) const 
Query the structure to find the lowest common ancestor. Assumes that the provided numbers are valid indices of vertices. Iterativelly modifies ("lifts") u an v until it finnds their lowest common ancestor.  
Public Attributes  
const RootedTree &  tree 
std::vector< std::vector< int > >  up 
for every vertex stores a list of its ancestors by powers of two For each vertex, the first element of the corresponding list contains the index of its parent. The ith element of the list is an index of the (2^i)th ancestor of the vertex.  
Protected Member Functions  
void  populate_up () 
A structure that holds a rooted tree and allow for effecient queries of the lowest common ancestor of two given vertices in the tree.

inlineexplicit 
Stores the tree and precomputs "up lifts".
tree_  rooted tree. 

inline 
Query the structure to find the lowest common ancestor. Assumes that the provided numbers are valid indices of vertices. Iterativelly modifies ("lifts") u an v until it finnds their lowest common ancestor.
u  index of one of the queried vertex 
v  index of the other queried vertex 

inlineprotected 
Populate the "up" structure. See above.