Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.lowest_common_ancestors.lowest_common_ancestor

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

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

Parameters

• G (NetworkX directed graph)

• node1, node2 (nodes in the graph.)

• default (object) – 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.

See also

tree_all_pairs_lowest_common_ancestor(), all_pairs_lowest_common_ancestor()