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.all_pairs_lowest_common_ancestor

all_pairs_lowest_common_ancestor(G, pairs=None)[source]

Compute the lowest common ancestor for pairs of nodes.

Parameters:
  • G (NetworkX directed graph)
  • pairs (iterable 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.
Returns:

  • An iterator over ((node1, node2), lca) where (node1, node2) are
  • the pairs specified and lca is a lowest common ancestor of the pair.
  • Note that for the default of all pairs in G, we consider
  • unordered pairs, e.g. you will not get both (b, a) and (a, b).

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.