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.

Examples

>>> G = nx.DiGraph()
>>> nx.add_path(G, (0, 1, 2, 3))
>>> nx.add_path(G, (0, 4, 3))
>>> nx.lowest_common_ancestor(G, 2, 4)
0

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.