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.

See also

all_pairs_lowest_common_ancestor(), lowest_common_ancestor()