tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None)¶
Yield the lowest common ancestor for sets of pairs in a tree.
- 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
rootthat have a lowest common ancestor.
lcas – in
lcais their lowest common ancestor.
generator of tuples
((u, v), lca)where
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.