Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
graph::LowestCommonAncestor Class Reference
Collaboration diagram for graph::LowestCommonAncestor:
[legend]

Public Member Functions

 LowestCommonAncestor (const RootedTree &tree_)
 Stores the tree and precomputs "up lifts". More...
 
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. More...
 

Public Attributes

const RootedTreetree
 
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.

Constructor & Destructor Documentation

◆ LowestCommonAncestor()

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

Stores the tree and precomputs "up lifts".

Parameters
tree_rooted tree.
151  : tree(tree_) {
152  populate_up();
153  }
Here is the call graph for this function:

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
uindex of one of the queried vertex
vindex of the other queried vertex
Returns
index of the vertex which is the lowet common ancestor of u and v
164  {
165  // Ensure u is the deeper (higher level) of the two vertices
166  if (tree.level[v] > tree.level[u]) {
167  std::swap(u, v);
168  }
169 
170  // "Lift" u to the same level as v.
171  int level_diff = tree.level[u] - tree.level[v];
172  for (int i = 0; (1 << i) <= level_diff; ++i) {
173  if (level_diff & (1 << i)) {
174  u = up[u][i];
175  }
176  }
177  assert(tree.level[u] == tree.level[v]);
178 
179  if (u == v) {
180  return u;
181  }
182 
183  // "Lift" u and v to their 2^i th ancestor if they are different
184  for (int i = static_cast<int>(up[u].size()) - 1; i >= 0; --i) {
185  if (up[u][i] != up[v][i]) {
186  u = up[u][i];
187  v = up[v][i];
188  }
189  }
190 
191  // As we regressed u an v such that they cannot further be lifted so
192  // that their ancestor would be different, the only logical
193  // consequence is that their parent is the sought answer.
194  assert(up[u][0] == up[v][0]);
195  return up[u][0];
196  }
Here is the call graph for this function:

◆ populate_up()

void graph::LowestCommonAncestor::populate_up ( )
inlineprotected

Populate the "up" structure. See above.

212  {
213  up.resize(tree.number_of_vertices());
214  for (int vertex = 0; vertex < tree.number_of_vertices(); ++vertex) {
215  up[vertex].push_back(tree.parent[vertex]);
216  }
217  for (int level = 0; (1 << level) < tree.number_of_vertices(); ++level) {
218  for (int vertex = 0; vertex < tree.number_of_vertices(); ++vertex) {
219  // up[vertex][level + 1] = 2^(level + 1) th ancestor of vertex =
220  // = 2^level th ancestor of 2^level th ancestor of vertex =
221  // = 2^level th ancestor of up[vertex][level]
222  up[vertex].push_back(up[up[vertex][level]][level]);
223  }
224  }
225  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
std::vector::resize
T resize(T... args)
graph::RootedTree::level
std::vector< int > level
Stores the distance from the root.
Definition: lowest_common_ancestor.cpp:106
graph::LowestCommonAncestor::populate_up
void populate_up()
Definition: lowest_common_ancestor.cpp:212
std::vector::push_back
T push_back(T... args)
graph::LowestCommonAncestor::up
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 o...
Definition: lowest_common_ancestor.cpp:206
graph::RootedTree::parent
std::vector< int > parent
Stores parent of every vertex and for root its own index. The root is technically not its own parent,...
Definition: lowest_common_ancestor.cpp:104
std::swap
T swap(T... args)
graph::Graph::number_of_vertices
int number_of_vertices() const
Definition: lowest_common_ancestor.cpp:74