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) where u and v are nodes: in pairs and lca is their lowest common ancestor.

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.

Examples

>>> import pprint
>>> G = nx.DiGraph([(1, 3), (2, 4), (1, 2)])
>>> pprint.pprint(dict(nx.tree_all_pairs_lowest_common_ancestor(G)))
{(1, 1): 1,
 (2, 1): 1,
 (2, 2): 2,
 (3, 1): 1,
 (3, 2): 1,
 (3, 3): 3,
 (3, 4): 1,
 (4, 1): 1,
 (4, 2): 2,
 (4, 4): 4}

We can also use pairs argument to specify the pairs of nodes for which we want to compute lowest common ancestors. Here is an example:

>>> dict(nx.tree_all_pairs_lowest_common_ancestor(G, pairs=[(1, 4), (2, 3)]))
{(2, 3): 1, (1, 4): 1}