networkx.algorithms.lowest_common_ancestors.tree_all_pairs_lowest_common_ancestor¶

tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None)[source]¶

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

Parameters:	G (NetworkX directed graph (must be a tree)) root (node, optional (default: None)) – The root of the subtree to operate on. If None, assume the entire graph has exactly one source and use that. pairs (iterable 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:	lcas – in `pairs` and `lca` is their lowest common ancestor.
Return type:	generator of tuples `((u, v), lca)` where `u` and `v` are nodes

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.