tree_all_pairs_lowest_common_ancestor

tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None)

Yield the lowest common ancestor for sets of pairs in a tree.

Parameters

GNetworkX directed graph (must be a tree)

rootnode, optional (default: None)

The root of the subtree to operate on. If None, assume the entire graph has exactly one source and use that.

pairsiterable or iterator of pairs of nodes, optional (default: None)

The pairs of interest. If None, Defaults to all pairs of nodes under root that have a lowest common ancestor.

Returns

lcasgenerator of tuples ((u, v), lca) where u and v are nodes

in pairs and lca is their lowest common ancestor.

See also

all_pairs_lowest_common_ancestor

similar routine for general DAGs

lowest_common_ancestor

just a single pair for general DAGs

Notes

Only defined on non-null trees represented with directed edges from parents to children. Uses Tarjan’s off-line lowest-common-ancestors algorithm. Runs in time \(O(4 \times (V + E + P))\) time, where 4 is the largest value of the inverse Ackermann function likely to ever come up in actual use, and \(P\) is the number of pairs requested (or \(V^2\) if all are needed).

Tarjan, R. E. (1979), “Applications of path compression on balanced trees”, Journal of the ACM 26 (4): 690-715, doi:10.1145/322154.322161.