Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_lowest_common_ancestors.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 import pytest | |
2 from itertools import chain, combinations, product | |
3 | |
4 import networkx as nx | |
5 | |
6 tree_all_pairs_lca = nx.tree_all_pairs_lowest_common_ancestor | |
7 all_pairs_lca = nx.all_pairs_lowest_common_ancestor | |
8 | |
9 | |
10 def get_pair(dictionary, n1, n2): | |
11 if (n1, n2) in dictionary: | |
12 return dictionary[n1, n2] | |
13 else: | |
14 return dictionary[n2, n1] | |
15 | |
16 | |
17 class TestTreeLCA: | |
18 @classmethod | |
19 def setup_class(cls): | |
20 cls.DG = nx.DiGraph() | |
21 edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)] | |
22 cls.DG.add_edges_from(edges) | |
23 cls.ans = dict(tree_all_pairs_lca(cls.DG, 0)) | |
24 gold = {(n, n): n for n in cls.DG} | |
25 gold.update({(0, i): 0 for i in range(1, 7)}) | |
26 gold.update( | |
27 { | |
28 (1, 2): 0, | |
29 (1, 3): 1, | |
30 (1, 4): 1, | |
31 (1, 5): 0, | |
32 (1, 6): 0, | |
33 (2, 3): 0, | |
34 (2, 4): 0, | |
35 (2, 5): 2, | |
36 (2, 6): 2, | |
37 (3, 4): 1, | |
38 (3, 5): 0, | |
39 (3, 6): 0, | |
40 (4, 5): 0, | |
41 (4, 6): 0, | |
42 (5, 6): 2, | |
43 } | |
44 ) | |
45 | |
46 cls.gold = gold | |
47 | |
48 @staticmethod | |
49 def assert_has_same_pairs(d1, d2): | |
50 for (a, b) in ((min(pair), max(pair)) for pair in chain(d1, d2)): | |
51 assert get_pair(d1, a, b) == get_pair(d2, a, b) | |
52 | |
53 def test_tree_all_pairs_lowest_common_ancestor1(self): | |
54 """Specifying the root is optional.""" | |
55 assert dict(tree_all_pairs_lca(self.DG)) == self.ans | |
56 | |
57 def test_tree_all_pairs_lowest_common_ancestor2(self): | |
58 """Specifying only some pairs gives only those pairs.""" | |
59 test_pairs = [(0, 1), (0, 1), (1, 0)] | |
60 ans = dict(tree_all_pairs_lca(self.DG, 0, test_pairs)) | |
61 assert (0, 1) in ans and (1, 0) in ans | |
62 assert len(ans) == 2 | |
63 | |
64 def test_tree_all_pairs_lowest_common_ancestor3(self): | |
65 """Specifying no pairs same as specifying all.""" | |
66 all_pairs = chain(combinations(self.DG, 2), ((node, node) for node in self.DG)) | |
67 | |
68 ans = dict(tree_all_pairs_lca(self.DG, 0, all_pairs)) | |
69 self.assert_has_same_pairs(ans, self.ans) | |
70 | |
71 def test_tree_all_pairs_lowest_common_ancestor4(self): | |
72 """Gives the right answer.""" | |
73 ans = dict(tree_all_pairs_lca(self.DG)) | |
74 self.assert_has_same_pairs(self.gold, ans) | |
75 | |
76 def test_tree_all_pairs_lowest_common_ancestor5(self): | |
77 """Handles invalid input correctly.""" | |
78 empty_digraph = tree_all_pairs_lca(nx.DiGraph()) | |
79 pytest.raises(nx.NetworkXPointlessConcept, list, empty_digraph) | |
80 | |
81 bad_pairs_digraph = tree_all_pairs_lca(self.DG, pairs=[(-1, -2)]) | |
82 pytest.raises(nx.NodeNotFound, list, bad_pairs_digraph) | |
83 | |
84 def test_tree_all_pairs_lowest_common_ancestor6(self): | |
85 """Works on subtrees.""" | |
86 ans = dict(tree_all_pairs_lca(self.DG, 1)) | |
87 gold = { | |
88 pair: lca | |
89 for (pair, lca) in self.gold.items() | |
90 if all(n in (1, 3, 4) for n in pair) | |
91 } | |
92 self.assert_has_same_pairs(gold, ans) | |
93 | |
94 def test_tree_all_pairs_lowest_common_ancestor7(self): | |
95 """Works on disconnected nodes.""" | |
96 G = nx.DiGraph() | |
97 G.add_node(1) | |
98 assert {(1, 1): 1} == dict(tree_all_pairs_lca(G)) | |
99 | |
100 G.add_node(0) | |
101 assert {(1, 1): 1} == dict(tree_all_pairs_lca(G, 1)) | |
102 assert {(0, 0): 0} == dict(tree_all_pairs_lca(G, 0)) | |
103 | |
104 pytest.raises(nx.NetworkXError, list, tree_all_pairs_lca(G)) | |
105 | |
106 def test_tree_all_pairs_lowest_common_ancestor8(self): | |
107 """Raises right errors if not a tree.""" | |
108 # Cycle | |
109 G = nx.DiGraph([(1, 2), (2, 1)]) | |
110 pytest.raises(nx.NetworkXError, list, tree_all_pairs_lca(G)) | |
111 # DAG | |
112 G = nx.DiGraph([(0, 2), (1, 2)]) | |
113 pytest.raises(nx.NetworkXError, list, tree_all_pairs_lca(G)) | |
114 | |
115 def test_tree_all_pairs_lowest_common_ancestor9(self): | |
116 """Test that pairs works correctly as a generator.""" | |
117 pairs = iter([(0, 1), (0, 1), (1, 0)]) | |
118 some_pairs = dict(tree_all_pairs_lca(self.DG, 0, pairs)) | |
119 assert (0, 1) in some_pairs and (1, 0) in some_pairs | |
120 assert len(some_pairs) == 2 | |
121 | |
122 def test_tree_all_pairs_lowest_common_ancestor10(self): | |
123 """Test that pairs not in the graph raises error.""" | |
124 lca = tree_all_pairs_lca(self.DG, 0, [(-1, -1)]) | |
125 pytest.raises(nx.NodeNotFound, list, lca) | |
126 | |
127 def test_tree_all_pairs_lowest_common_ancestor11(self): | |
128 """Test that None as a node in the graph raises an error.""" | |
129 G = nx.DiGraph([(None, 3)]) | |
130 pytest.raises(nx.NetworkXError, list, tree_all_pairs_lca(G)) | |
131 pytest.raises( | |
132 nx.NodeNotFound, list, tree_all_pairs_lca(self.DG, pairs=G.edges()) | |
133 ) | |
134 | |
135 def test_tree_all_pairs_lowest_common_ancestor12(self): | |
136 """Test that tree routine bails on DAGs.""" | |
137 G = nx.DiGraph([(3, 4), (5, 4)]) | |
138 pytest.raises(nx.NetworkXError, list, tree_all_pairs_lca(G)) | |
139 | |
140 def test_not_implemented_for(self): | |
141 NNI = nx.NetworkXNotImplemented | |
142 G = nx.Graph([(0, 1)]) | |
143 pytest.raises(NNI, tree_all_pairs_lca, G) | |
144 pytest.raises(NNI, all_pairs_lca, G) | |
145 pytest.raises(NNI, nx.lowest_common_ancestor, G, 0, 1) | |
146 G = nx.MultiGraph([(0, 1)]) | |
147 pytest.raises(NNI, tree_all_pairs_lca, G) | |
148 pytest.raises(NNI, all_pairs_lca, G) | |
149 pytest.raises(NNI, nx.lowest_common_ancestor, G, 0, 1) | |
150 G = nx.MultiDiGraph([(0, 1)]) | |
151 pytest.raises(NNI, tree_all_pairs_lca, G) | |
152 pytest.raises(NNI, all_pairs_lca, G) | |
153 pytest.raises(NNI, nx.lowest_common_ancestor, G, 0, 1) | |
154 | |
155 def test_tree_all_pairs_lowest_common_ancestor13(self): | |
156 """Test that it works on non-empty trees with no LCAs.""" | |
157 G = nx.DiGraph() | |
158 G.add_node(3) | |
159 ans = list(tree_all_pairs_lca(G)) | |
160 assert ans == [((3, 3), 3)] | |
161 | |
162 | |
163 class TestDAGLCA: | |
164 @classmethod | |
165 def setup_class(cls): | |
166 cls.DG = nx.DiGraph() | |
167 nx.add_path(cls.DG, (0, 1, 2, 3)) | |
168 nx.add_path(cls.DG, (0, 4, 3)) | |
169 nx.add_path(cls.DG, (0, 5, 6, 8, 3)) | |
170 nx.add_path(cls.DG, (5, 7, 8)) | |
171 cls.DG.add_edge(6, 2) | |
172 cls.DG.add_edge(7, 2) | |
173 | |
174 cls.root_distance = nx.shortest_path_length(cls.DG, source=0) | |
175 | |
176 cls.gold = { | |
177 (1, 1): 1, | |
178 (1, 2): 1, | |
179 (1, 3): 1, | |
180 (1, 4): 0, | |
181 (1, 5): 0, | |
182 (1, 6): 0, | |
183 (1, 7): 0, | |
184 (1, 8): 0, | |
185 (2, 2): 2, | |
186 (2, 3): 2, | |
187 (2, 4): 0, | |
188 (2, 5): 5, | |
189 (2, 6): 6, | |
190 (2, 7): 7, | |
191 (2, 8): 7, | |
192 (3, 3): 8, | |
193 (3, 4): 4, | |
194 (3, 5): 5, | |
195 (3, 6): 6, | |
196 (3, 7): 7, | |
197 (3, 8): 8, | |
198 (4, 4): 4, | |
199 (4, 5): 0, | |
200 (4, 6): 0, | |
201 (4, 7): 0, | |
202 (4, 8): 0, | |
203 (5, 5): 5, | |
204 (5, 6): 5, | |
205 (5, 7): 5, | |
206 (5, 8): 5, | |
207 (6, 6): 6, | |
208 (6, 7): 5, | |
209 (6, 8): 6, | |
210 (7, 7): 7, | |
211 (7, 8): 7, | |
212 (8, 8): 8, | |
213 } | |
214 cls.gold.update(((0, n), 0) for n in cls.DG) | |
215 | |
216 def assert_lca_dicts_same(self, d1, d2, G=None): | |
217 """Checks if d1 and d2 contain the same pairs and | |
218 have a node at the same distance from root for each. | |
219 If G is None use self.DG.""" | |
220 if G is None: | |
221 G = self.DG | |
222 root_distance = self.root_distance | |
223 else: | |
224 roots = [n for n, deg in G.in_degree if deg == 0] | |
225 assert len(roots) == 1 | |
226 root_distance = nx.shortest_path_length(G, source=roots[0]) | |
227 | |
228 for a, b in ((min(pair), max(pair)) for pair in chain(d1, d2)): | |
229 assert ( | |
230 root_distance[get_pair(d1, a, b)] == root_distance[get_pair(d2, a, b)] | |
231 ) | |
232 | |
233 def test_all_pairs_lowest_common_ancestor1(self): | |
234 """Produces the correct results.""" | |
235 self.assert_lca_dicts_same(dict(all_pairs_lca(self.DG)), self.gold) | |
236 | |
237 def test_all_pairs_lowest_common_ancestor2(self): | |
238 """Produces the correct results when all pairs given.""" | |
239 all_pairs = list(product(self.DG.nodes(), self.DG.nodes())) | |
240 ans = all_pairs_lca(self.DG, pairs=all_pairs) | |
241 self.assert_lca_dicts_same(dict(ans), self.gold) | |
242 | |
243 def test_all_pairs_lowest_common_ancestor3(self): | |
244 """Produces the correct results when all pairs given as a generator.""" | |
245 all_pairs = product(self.DG.nodes(), self.DG.nodes()) | |
246 ans = all_pairs_lca(self.DG, pairs=all_pairs) | |
247 self.assert_lca_dicts_same(dict(ans), self.gold) | |
248 | |
249 def test_all_pairs_lowest_common_ancestor4(self): | |
250 """Graph with two roots.""" | |
251 G = self.DG.copy() | |
252 G.add_edge(9, 10) | |
253 G.add_edge(9, 4) | |
254 gold = self.gold.copy() | |
255 gold[9, 9] = 9 | |
256 gold[9, 10] = 9 | |
257 gold[9, 4] = 9 | |
258 gold[9, 3] = 9 | |
259 gold[10, 4] = 9 | |
260 gold[10, 3] = 9 | |
261 gold[10, 10] = 10 | |
262 | |
263 testing = dict(all_pairs_lca(G)) | |
264 | |
265 G.add_edge(-1, 9) | |
266 G.add_edge(-1, 0) | |
267 self.assert_lca_dicts_same(testing, gold, G) | |
268 | |
269 def test_all_pairs_lowest_common_ancestor5(self): | |
270 """Test that pairs not in the graph raises error.""" | |
271 pytest.raises(nx.NodeNotFound, all_pairs_lca, self.DG, [(-1, -1)]) | |
272 | |
273 def test_all_pairs_lowest_common_ancestor6(self): | |
274 """Test that pairs with no LCA specified emits nothing.""" | |
275 G = self.DG.copy() | |
276 G.add_node(-1) | |
277 gen = all_pairs_lca(G, [(-1, -1), (-1, 0)]) | |
278 assert dict(gen) == {(-1, -1): -1} | |
279 | |
280 def test_all_pairs_lowest_common_ancestor7(self): | |
281 """Test that LCA on null graph bails.""" | |
282 pytest.raises(nx.NetworkXPointlessConcept, all_pairs_lca, nx.DiGraph()) | |
283 | |
284 def test_all_pairs_lowest_common_ancestor8(self): | |
285 """Test that LCA on non-dags bails.""" | |
286 pytest.raises(nx.NetworkXError, all_pairs_lca, nx.DiGraph([(3, 4), (4, 3)])) | |
287 | |
288 def test_all_pairs_lowest_common_ancestor9(self): | |
289 """Test that it works on non-empty graphs with no LCAs.""" | |
290 G = nx.DiGraph() | |
291 G.add_node(3) | |
292 ans = list(all_pairs_lca(G)) | |
293 assert ans == [((3, 3), 3)] | |
294 | |
295 def test_all_pairs_lowest_common_ancestor10(self): | |
296 """Test that it bails on None as a node.""" | |
297 G = nx.DiGraph([(None, 3)]) | |
298 pytest.raises(nx.NetworkXError, all_pairs_lca, G) | |
299 pytest.raises(nx.NodeNotFound, all_pairs_lca, self.DG, pairs=G.edges()) | |
300 | |
301 def test_lowest_common_ancestor1(self): | |
302 """Test that the one-pair function works on default.""" | |
303 G = nx.DiGraph([(0, 1), (2, 1)]) | |
304 sentinel = object() | |
305 assert nx.lowest_common_ancestor(G, 0, 2, default=sentinel) is sentinel | |
306 | |
307 def test_lowest_common_ancestor2(self): | |
308 """Test that the one-pair function works on identity.""" | |
309 G = nx.DiGraph() | |
310 G.add_node(3) | |
311 assert nx.lowest_common_ancestor(G, 3, 3) == 3 |