Module lca 

Lowest Common Ancestor (LCA) finding for the event DAG.

Given two tip events in a DAG, the LCA is the most recent event that is an ancestor of both tips. Finding the LCA identifies the point where two branches diverged, which is the key input for divergent-branch replay.

Algorithm

We use a bidirectional BFS: walk upward from both tips simultaneously, alternating between them. The first node visited by both walks is the LCA. This runs in O(divergent) — proportional to the events since divergence, not the total DAG size.

Edge Cases

• If one tip is an ancestor of the other, the ancestor tip is the LCA.
• If both tips are the same event, that event is the LCA.
• If the tips have no common ancestor (disjoint roots), returns None.

Enums

LcaError

Errors from LCA computation.

Functions

find_all_lcas

Find all LCAs (there can be multiple in a DAG with diamond merges).

find_lca

Find the Lowest Common Ancestor of two events in the DAG.