all_pairs_lowest_common_ancestor#

all_pairs_lowest_common_ancestor(G, pairs=None)[source]#

Compute the lowest common ancestor for pairs of nodes.

Parameters:
GNetworkX directed graph
pairsiterable of pairs of nodes, optional (default: all pairs)

The pairs of nodes of interest. If None, will find the LCA of all pairs of nodes.

Yields:
((node1, node2), lca)2-tuple

Where lca is least common ancestor of node1 and node2. Note that for the default case, the order of the node pair is not considered, e.g. you will not get both (a, b) and (b, a)

Raises:
NetworkXPointlessConcept

If G is null.

NetworkXError

If G is not a DAG.

Notes

Only defined on non-null directed acyclic graphs.

Uses the \(O(n^3)\) ancestor-list algorithm from: M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, P. Sumazin. “Lowest common ancestors in trees and directed acyclic graphs.” Journal of Algorithms, 57(2): 75-94, 2005.

Examples

The default behavior is to yield the lowest common ancestor for all possible combinations of nodes in G, including self-pairings:

>>> G = nx.DiGraph([(0, 1), (0, 3), (1, 2)])
>>> dict(nx.all_pairs_lowest_common_ancestor(G))
{(2, 2): 2, (1, 1): 1, (2, 1): 1, (1, 3): 0, (2, 3): 0, (3, 3): 3, (0, 0): 0, (1, 0): 0, (2, 0): 0, (3, 0): 0}

The pairs argument can be used to limit the output to only the specified node pairings:

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