LCA.H File Reference

Lowest Common Ancestor (LCA) on rooted trees represented as Aleph graphs. More...

#include <algorithm>
#include <bit>
#include <cstddef>
#include <limits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_dynListStack.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynMapTree.H>
#include <tpl_graph.H>
#include <tpl_sparse_table.H>

Include dependency graph for LCA.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::lca_detail::Rooted_Tree_Data< GT, SA >
struct	Aleph::lca_detail::Depth_Node
struct	Aleph::lca_detail::Depth_Node_Min_Op
class	Aleph::Gen_Binary_Lifting_LCA< GT, SA >
	LCA via binary lifting on a rooted tree. More...
class	Aleph::Gen_Euler_RMQ_LCA< GT, SA >
	LCA via Euler tour + RMQ on depth in a rooted tree. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::lca_detail

Typedefs
template<class GT , class SA = Dft_Show_Arc<GT>>
using	Aleph::Binary_Lifting_LCA = Gen_Binary_Lifting_LCA< GT, SA >
	Convenience alias for binary-lifting LCA.
template<class GT , class SA = Dft_Show_Arc<GT>>
using	Aleph::Euler_RMQ_LCA = Gen_Euler_RMQ_LCA< GT, SA >
	Convenience alias for Euler+RMQ LCA.

Detailed Description

Lowest Common Ancestor (LCA) on rooted trees represented as Aleph graphs.

The Lowest Common Ancestor (LCA) of two nodes \(u\) and \(v\) in a rooted tree is the deepest node that is an ancestor of both \(u\) and \(v\).

Concept Visualization

   [0] (Root)          LCA(4, 5) = 2
  /   \                LCA(4, 6) = 0
[1]   [2]              LCA(1, 4) = 0
     /   \             LCA(2, 5) = 2 (a node can be its own ancestor)
   [3]   [4]
        /
      [5]

This header provides two distinct LCA engines with different trade-offs:

1. Binary Lifting (<tt>Gen_Binary_Lifting_LCA</tt>)

Uses a jump table (sparse table over ancestors) where up[k][v] stores the \(2^k\)-th ancestor of node \(v\).

• Preprocessing: \(O(n \log n)\) time and space.
• Query: \(O(\log n)\) time.
• Best for: General purpose, especially when memory is more constrained than the Euler approach, or when path-based properties are not needed.

2. Euler Tour + RMQ (<tt>Gen_Euler_RMQ_LCA</tt>)

Reduces the LCA problem to a Range Minimum Query (RMQ) problem. It performs an Euler tour (recording nodes as they are visited and returned to) and stores the depths. The LCA of \(u\) and \(v\) is the node with minimum depth between their first occurrences in the tour.

• Preprocessing: \(O(n \log n)\) time and space (using a Sparse Table for RMQ).
• Query: \(O(1)\) time.
• Best for: Heavy query workloads where constant-time response is critical.

Both classes:

• Work on Aleph graph backends (List_Graph, List_SGraph, Array_Graph).
• Accept arc filters (SA) to define the tree topology over a general graph.
• Strict Validation: Upon construction, the filtered graph is validated to be a valid tree (connected, acyclic, \(m = n - 1\)). If validation fails, a domain error exception is thrown.
• Provide distance calculation between any two nodes: \(dist(u, v) = depth(u) + depth(v) - 2 \cdot depth(LCA(u, v))\).

Example: Distance between nodes

using G = List_Graph<Graph_Node<int>, Graph_Arc<int>>;
G g;
// ... build a tree in g ...
Euler_RMQ_LCA<G> lca(g, root);
 
size_t d = lca.distance(node1, node2);
std::cout << "Distance: " << d << " edges\n";

See also

tpl_sparse_table.H

tpl_graph.H

Author

Leandro Rabindranath León

Definition in file LCA.H.