Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# 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. lcas – in pairs and lca is their lowest common ancestor. 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.