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.