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.