Tarjan Offline Least Common Ancestor

Tarjan Offline Least Common Ancestor

The Tarjan off-line least common ancestor is an algorithm for computing lowest common ancestors for pairs of nodes in a tree (based on the union-find data structure).

The AlgorithmExtensions.OfflineLeastCommonAncestor returns a delegate that can be queried for each pair. The delegate returns true if there is a common ancestor and assigns the out parameter.

var graph = new AdjacencyGraph<int, Edge<int>>();
int root = ...; // Root vertex
IEnumerable<SEquatableEdge<TVertex>> pairs = ...; // Vertex pairs
TryFunc<SEquatableEdge<TVertex>, TVertex> lca = graph.OfflineLeastCommonAncestor(root, pairs);

// Fetching the ancestor
foreach(SEquatableEdge<TVertex> pair in pairs)
{
    if (lca(pair, out TVertex ancestor))
    {
        Console.WriteLine($"The ancestor of {ancestor} is {pair}"); 
    }
}