Lowest Common Ancestor (LCA) queries using binary lifting.
This module preprocesses a tree in O(V log V) time to answer LCA queries and tree distance queries in O(log V) time per query.
Algorithm
- BFS from the root to compute depth and immediate parent for each node.
- Build a binary lifting table where
up[k][v]is the 2^k-th ancestor of v. - Answer LCA queries by lifting the deeper node up, then lifting both nodes together until their ancestors differ.
Complexity
- Preprocessing: O(V log V)
- LCA Query: O(log V)
- Distance Query: O(log V)
Example
iex> tree = Yog.from_edges(:undirected, [{1, 2, 1}, {1, 3, 1}, {2, 4, 1}, {2, 5, 1}])
iex> {:ok, state} = Yog.Pathfinding.LCA.lca_preprocess(tree, 1)
iex> Yog.Pathfinding.LCA.lca(state, 4, 5)
{:ok, 2}
iex> Yog.Pathfinding.LCA.tree_distance(state, 4, 3)
{:ok, 3}References
Summary
Functions
Returns the lowest common ancestor of two nodes.
Preprocesses the tree for LCA queries.
Calculates the tree distance (number of edges) between two nodes.
Functions
@spec lca(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) :: {:ok, Yog.node_id()} | {:error, :node_not_found}
Returns the lowest common ancestor of two nodes.
Errors
{:error, :node_not_found}- One or both nodes are not in the tree
@spec lca_preprocess(Yog.Graph.t(), Yog.node_id()) :: {:ok, Yog.Pathfinding.LCA.State.t()} | {:error, :root_not_found | :not_a_tree}
Preprocesses the tree for LCA queries.
Returns {:ok, state} on success, or {:error, reason} if the graph
is not a valid tree connected at the given root.
Errors
{:error, :root_not_found}- The root node does not exist in the graph{:error, :not_a_tree}- The graph contains a cycle or is disconnected
@spec tree_distance(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) :: {:ok, non_neg_integer()} | {:error, :node_not_found}
Calculates the tree distance (number of edges) between two nodes.
Computed as depth[a] + depth[b] - 2 * depth[lca].
Errors
{:error, :node_not_found}- One or both nodes are not in the tree