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


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

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 under root that have a lowest common ancestor.

lcas – in pairs and lca is their lowest common ancestor.

Return type:

generator of tuples ((u, v), lca) where u and v are nodes


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.