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
- GNetworkX directed graph (must be a tree)
- rootnode, optional (default: None)
The root of the subtree to operate on. If None, assume the entire graph has exactly one source and use that.
- pairsiterable 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
- lcasgenerator of tuples
((u, v), lca)
whereu
andv
are nodes in
pairs
andlca
is their lowest common ancestor.
- lcasgenerator of tuples
See also
all_pairs_lowest_common_ancestor
similar routine for general DAGs
lowest_common_ancestor
just a single pair for general DAGs
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.