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
andlca
is their lowest common ancestor.- Return type
generator of tuples
((u, v), lca)
whereu
andv
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.