lowest_common_ancestor

lowest_common_ancestor(G, node1, node2, default=None)

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.

See also

tree_all_pairs_lowest_common_ancestor

all_pairs_lowest_common_ancestor

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.