graph::LowestCommonAncestor Class Reference

Collaboration diagram for graph::LowestCommonAncestor:

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 i-th element of the list is an index of the (2^i)-th ancestor of the vertex.

Protected Member Functions
void	populate_up ()

Detailed Description

A structure that holds a rooted tree and allow for effecient queries of the lowest common ancestor of two given vertices in the tree.

Definition at line 145 of file lowest_common_ancestor.cpp.

Constructor & Destructor Documentation

LowestCommonAncestor()

graph::LowestCommonAncestor::LowestCommonAncestor ( const RootedTree & tree_ )

inlineexplicit

Stores the tree and precomputs "up lifts".

Parameters

tree_

rooted tree.

Definition at line 151 of file lowest_common_ancestor.cpp.

                                                           : tree(tree_) {
        populate_up();
    }

Member Function Documentation

lowest_common_ancestor()

int graph::LowestCommonAncestor::lowest_common_ancestor ( int u, int v ) const

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.

Parameters

u	index of one of the queried vertex
v	index of the other queried vertex

Returns

index of the vertex which is the lowet common ancestor of u and v

Definition at line 164 of file lowest_common_ancestor.cpp.

                                                   {
        // Ensure u is the deeper (higher level) of the two vertices
        if (tree.level[v] > tree.level[u]) {
            std::swap(u, v);
        }
 
        // "Lift" u to the same level as v.
        int level_diff = tree.level[u] - tree.level[v];
        for (int i = 0; (1 << i) <= level_diff; ++i) {
            if (level_diff & (1 << i)) {
                u = up[u][i];
            }
        }
        assert(tree.level[u] == tree.level[v]);
 
        if (u == v) {
            return u;
        }
 
        // "Lift" u and v to their 2^i th ancestor if they are different
        for (int i = static_cast<int>(up[u].size()) - 1; i >= 0; --i) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
 
        // As we regressed u an v such that they cannot further be lifted so
        // that their ancestor would be different, the only logical
        // consequence is that their parent is the sought answer.
        assert(up[u][0] == up[v][0]);
        return up[u][0];
    }

populate_up()

void graph::LowestCommonAncestor::populate_up ( )

inlineprotected

Populate the "up" structure. See above.

Definition at line 212 of file lowest_common_ancestor.cpp.

                       {
        up.resize(tree.number_of_vertices());
        for (int vertex = 0; vertex < tree.number_of_vertices(); ++vertex) {
            up[vertex].push_back(tree.parent[vertex]);
        }
        for (int level = 0; (1 << level) < tree.number_of_vertices(); ++level) {
            for (int vertex = 0; vertex < tree.number_of_vertices(); ++vertex) {
                // up[vertex][level + 1] = 2^(level + 1) th ancestor of vertex =
                // = 2^level th ancestor of 2^level th ancestor of vertex =
                // = 2^level th ancestor of up[vertex][level]
                up[vertex].push_back(up[up[vertex][level]][level]);
            }
        }
    }

Member Data Documentation

tree

const RootedTree& graph::LowestCommonAncestor::tree

Definition at line 199 of file lowest_common_ancestor.cpp.

up

std::vector<std::vector<int> > graph::LowestCommonAncestor::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 i-th element of the list is an index of the (2^i)-th ancestor of the vertex.

Definition at line 206 of file lowest_common_ancestor.cpp.

---

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

• graph/lowest_common_ancestor.cpp