Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/lowest_common_ancestors.py: 16%
95 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Algorithms for finding the lowest common ancestor of trees and DAGs."""
2from collections import defaultdict
3from collections.abc import Mapping, Set
4from itertools import combinations_with_replacement
6import networkx as nx
7from networkx.utils import UnionFind, arbitrary_element, not_implemented_for
9__all__ = [
10 "all_pairs_lowest_common_ancestor",
11 "tree_all_pairs_lowest_common_ancestor",
12 "lowest_common_ancestor",
13]
16@not_implemented_for("undirected")
17@nx._dispatch
18def all_pairs_lowest_common_ancestor(G, pairs=None):
19 """Return the lowest common ancestor of all pairs or the provided pairs
21 Parameters
22 ----------
23 G : NetworkX directed graph
25 pairs : iterable of pairs of nodes, optional (default: all pairs)
26 The pairs of nodes of interest.
27 If None, will find the LCA of all pairs of nodes.
29 Yields
30 ------
31 ((node1, node2), lca) : 2-tuple
32 Where lca is least common ancestor of node1 and node2.
33 Note that for the default case, the order of the node pair is not considered,
34 e.g. you will not get both ``(a, b)`` and ``(b, a)``
36 Raises
37 ------
38 NetworkXPointlessConcept
39 If `G` is null.
40 NetworkXError
41 If `G` is not a DAG.
43 Examples
44 --------
45 The default behavior is to yield the lowest common ancestor for all
46 possible combinations of nodes in `G`, including self-pairings:
48 >>> G = nx.DiGraph([(0, 1), (0, 3), (1, 2)])
49 >>> dict(nx.all_pairs_lowest_common_ancestor(G))
50 {(0, 0): 0, (0, 1): 0, (0, 3): 0, (0, 2): 0, (1, 1): 1, (1, 3): 0, (1, 2): 1, (3, 3): 3, (3, 2): 0, (2, 2): 2}
52 The pairs argument can be used to limit the output to only the
53 specified node pairings:
55 >>> dict(nx.all_pairs_lowest_common_ancestor(G, pairs=[(1, 2), (2, 3)]))
56 {(1, 2): 1, (2, 3): 0}
58 Notes
59 -----
60 Only defined on non-null directed acyclic graphs.
62 See Also
63 --------
64 lowest_common_ancestor
65 """
66 if not nx.is_directed_acyclic_graph(G):
67 raise nx.NetworkXError("LCA only defined on directed acyclic graphs.")
68 if len(G) == 0:
69 raise nx.NetworkXPointlessConcept("LCA meaningless on null graphs.")
71 if pairs is None:
72 pairs = combinations_with_replacement(G, 2)
73 else:
74 # Convert iterator to iterable, if necessary. Trim duplicates.
75 pairs = dict.fromkeys(pairs)
76 # Verify that each of the nodes in the provided pairs is in G
77 nodeset = set(G)
78 for pair in pairs:
79 if set(pair) - nodeset:
80 raise nx.NodeNotFound(
81 f"Node(s) {set(pair) - nodeset} from pair {pair} not in G."
82 )
84 # Once input validation is done, construct the generator
85 def generate_lca_from_pairs(G, pairs):
86 ancestor_cache = {}
88 for v, w in pairs:
89 if v not in ancestor_cache:
90 ancestor_cache[v] = nx.ancestors(G, v)
91 ancestor_cache[v].add(v)
92 if w not in ancestor_cache:
93 ancestor_cache[w] = nx.ancestors(G, w)
94 ancestor_cache[w].add(w)
96 common_ancestors = ancestor_cache[v] & ancestor_cache[w]
98 if common_ancestors:
99 common_ancestor = next(iter(common_ancestors))
100 while True:
101 successor = None
102 for lower_ancestor in G.successors(common_ancestor):
103 if lower_ancestor in common_ancestors:
104 successor = lower_ancestor
105 break
106 if successor is None:
107 break
108 common_ancestor = successor
109 yield ((v, w), common_ancestor)
111 return generate_lca_from_pairs(G, pairs)
114@not_implemented_for("undirected")
115@nx._dispatch
116def lowest_common_ancestor(G, node1, node2, default=None):
117 """Compute the lowest common ancestor of the given pair of nodes.
119 Parameters
120 ----------
121 G : NetworkX directed graph
123 node1, node2 : nodes in the graph.
125 default : object
126 Returned if no common ancestor between `node1` and `node2`
128 Returns
129 -------
130 The lowest common ancestor of node1 and node2,
131 or default if they have no common ancestors.
133 Examples
134 --------
135 >>> G = nx.DiGraph()
136 >>> nx.add_path(G, (0, 1, 2, 3))
137 >>> nx.add_path(G, (0, 4, 3))
138 >>> nx.lowest_common_ancestor(G, 2, 4)
139 0
141 See Also
142 --------
143 all_pairs_lowest_common_ancestor"""
145 ans = list(all_pairs_lowest_common_ancestor(G, pairs=[(node1, node2)]))
146 if ans:
147 assert len(ans) == 1
148 return ans[0][1]
149 return default
152@not_implemented_for("undirected")
153@nx._dispatch
154def tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None):
155 r"""Yield the lowest common ancestor for sets of pairs in a tree.
157 Parameters
158 ----------
159 G : NetworkX directed graph (must be a tree)
161 root : node, optional (default: None)
162 The root of the subtree to operate on.
163 If None, assume the entire graph has exactly one source and use that.
165 pairs : iterable or iterator of pairs of nodes, optional (default: None)
166 The pairs of interest. If None, Defaults to all pairs of nodes
167 under `root` that have a lowest common ancestor.
169 Returns
170 -------
171 lcas : generator of tuples `((u, v), lca)` where `u` and `v` are nodes
172 in `pairs` and `lca` is their lowest common ancestor.
174 Examples
175 --------
176 >>> import pprint
177 >>> G = nx.DiGraph([(1, 3), (2, 4), (1, 2)])
178 >>> pprint.pprint(dict(nx.tree_all_pairs_lowest_common_ancestor(G)))
179 {(1, 1): 1,
180 (2, 1): 1,
181 (2, 2): 2,
182 (3, 1): 1,
183 (3, 2): 1,
184 (3, 3): 3,
185 (3, 4): 1,
186 (4, 1): 1,
187 (4, 2): 2,
188 (4, 4): 4}
190 We can also use `pairs` argument to specify the pairs of nodes for which we
191 want to compute lowest common ancestors. Here is an example:
193 >>> dict(nx.tree_all_pairs_lowest_common_ancestor(G, pairs=[(1, 4), (2, 3)]))
194 {(2, 3): 1, (1, 4): 1}
196 Notes
197 -----
198 Only defined on non-null trees represented with directed edges from
199 parents to children. Uses Tarjan's off-line lowest-common-ancestors
200 algorithm. Runs in time $O(4 \times (V + E + P))$ time, where 4 is the largest
201 value of the inverse Ackermann function likely to ever come up in actual
202 use, and $P$ is the number of pairs requested (or $V^2$ if all are needed).
204 Tarjan, R. E. (1979), "Applications of path compression on balanced trees",
205 Journal of the ACM 26 (4): 690-715, doi:10.1145/322154.322161.
207 See Also
208 --------
209 all_pairs_lowest_common_ancestor: similar routine for general DAGs
210 lowest_common_ancestor: just a single pair for general DAGs
211 """
212 if len(G) == 0:
213 raise nx.NetworkXPointlessConcept("LCA meaningless on null graphs.")
215 # Index pairs of interest for efficient lookup from either side.
216 if pairs is not None:
217 pair_dict = defaultdict(set)
218 # See note on all_pairs_lowest_common_ancestor.
219 if not isinstance(pairs, (Mapping, Set)):
220 pairs = set(pairs)
221 for u, v in pairs:
222 for n in (u, v):
223 if n not in G:
224 msg = f"The node {str(n)} is not in the digraph."
225 raise nx.NodeNotFound(msg)
226 pair_dict[u].add(v)
227 pair_dict[v].add(u)
229 # If root is not specified, find the exactly one node with in degree 0 and
230 # use it. Raise an error if none are found, or more than one is. Also check
231 # for any nodes with in degree larger than 1, which would imply G is not a
232 # tree.
233 if root is None:
234 for n, deg in G.in_degree:
235 if deg == 0:
236 if root is not None:
237 msg = "No root specified and tree has multiple sources."
238 raise nx.NetworkXError(msg)
239 root = n
240 # checking deg>1 is not sufficient for MultiDiGraphs
241 elif deg > 1 and len(G.pred[n]) > 1:
242 msg = "Tree LCA only defined on trees; use DAG routine."
243 raise nx.NetworkXError(msg)
244 if root is None:
245 raise nx.NetworkXError("Graph contains a cycle.")
247 # Iterative implementation of Tarjan's offline lca algorithm
248 # as described in CLRS on page 521 (2nd edition)/page 584 (3rd edition)
249 uf = UnionFind()
250 ancestors = {}
251 for node in G:
252 ancestors[node] = uf[node]
254 colors = defaultdict(bool)
255 for node in nx.dfs_postorder_nodes(G, root):
256 colors[node] = True
257 for v in pair_dict[node] if pairs is not None else G:
258 if colors[v]:
259 # If the user requested both directions of a pair, give it.
260 # Otherwise, just give one.
261 if pairs is not None and (node, v) in pairs:
262 yield (node, v), ancestors[uf[v]]
263 if pairs is None or (v, node) in pairs:
264 yield (v, node), ancestors[uf[v]]
265 if node != root:
266 parent = arbitrary_element(G.pred[node])
267 uf.union(parent, node)
268 ancestors[uf[parent]] = parent