lowest_common_ancestor#

lowest_common_ancestor(G, node1, node2, default=None)[source]#

Compute the lowest common ancestor of the given pair of nodes.

Parameters:
GNetworkX directed graph
node1, node2nodes in the graph.
defaultobject

Returned if no common ancestor between node1 and node2

Returns:
The lowest common ancestor of node1 and node2,
or default if they have no common ancestors.

Notes

Only defined on non-null directed acyclic graphs. Takes n log(n) time in the size of the graph. See all_pairs_lowest_common_ancestor when you have more than one pair of nodes of interest.

Examples

>>> G = nx.DiGraph([(0, 1), (0, 2), (2, 3), (2, 4), (1, 6), (4, 5)])
>>> nx.lowest_common_ancestor(G, 3, 5)
2

We can also set default argument as below. The value of default is returned if there are no common ancestors of given two nodes.

>>> G = nx.DiGraph([(4, 5), (12, 13)])
>>> nx.lowest_common_ancestor(G, 12, 5, default="No common ancestors!")
'No common ancestors!'