Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/tests/test_ismags.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 """ | |
2 Tests for ISMAGS isomorphism algorithm. | |
3 """ | |
4 | |
5 import pytest | |
6 import networkx as nx | |
7 from networkx.algorithms import isomorphism as iso | |
8 | |
9 | |
10 def _matches_to_sets(matches): | |
11 """ | |
12 Helper function to facilitate comparing collections of dictionaries in | |
13 which order does not matter. | |
14 """ | |
15 return set(map(lambda m: frozenset(m.items()), matches)) | |
16 | |
17 | |
18 class TestSelfIsomorphism: | |
19 data = [ | |
20 ( | |
21 [ | |
22 (0, dict(name="a")), | |
23 (1, dict(name="a")), | |
24 (2, dict(name="b")), | |
25 (3, dict(name="b")), | |
26 (4, dict(name="a")), | |
27 (5, dict(name="a")), | |
28 ], | |
29 [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)], | |
30 ), | |
31 (range(1, 5), [(1, 2), (2, 4), (4, 3), (3, 1)]), | |
32 ( | |
33 [], | |
34 [ | |
35 (0, 1), | |
36 (1, 2), | |
37 (2, 3), | |
38 (3, 4), | |
39 (4, 5), | |
40 (5, 0), | |
41 (0, 6), | |
42 (6, 7), | |
43 (2, 8), | |
44 (8, 9), | |
45 (4, 10), | |
46 (10, 11), | |
47 ], | |
48 ), | |
49 ([], [(0, 1), (1, 2), (1, 4), (2, 3), (3, 5), (3, 6)]), | |
50 ] | |
51 | |
52 def test_self_isomorphism(self): | |
53 """ | |
54 For some small, symmetric graphs, make sure that 1) they are isomorphic | |
55 to themselves, and 2) that only the identity mapping is found. | |
56 """ | |
57 for node_data, edge_data in self.data: | |
58 graph = nx.Graph() | |
59 graph.add_nodes_from(node_data) | |
60 graph.add_edges_from(edge_data) | |
61 | |
62 ismags = iso.ISMAGS( | |
63 graph, graph, node_match=iso.categorical_node_match("name", None) | |
64 ) | |
65 assert ismags.is_isomorphic() | |
66 assert ismags.subgraph_is_isomorphic() | |
67 assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [ | |
68 {n: n for n in graph.nodes} | |
69 ] | |
70 | |
71 def test_edgecase_self_isomorphism(self): | |
72 """ | |
73 This edgecase is one of the cases in which it is hard to find all | |
74 symmetry elements. | |
75 """ | |
76 graph = nx.Graph() | |
77 nx.add_path(graph, range(5)) | |
78 graph.add_edges_from([(2, 5), (5, 6)]) | |
79 | |
80 ismags = iso.ISMAGS(graph, graph) | |
81 ismags_answer = list(ismags.find_isomorphisms(True)) | |
82 assert ismags_answer == [{n: n for n in graph.nodes}] | |
83 | |
84 graph = nx.relabel_nodes(graph, {0: 0, 1: 1, 2: 2, 3: 3, 4: 6, 5: 4, 6: 5}) | |
85 ismags = iso.ISMAGS(graph, graph) | |
86 ismags_answer = list(ismags.find_isomorphisms(True)) | |
87 assert ismags_answer == [{n: n for n in graph.nodes}] | |
88 | |
89 @pytest.mark.skip() | |
90 def test_directed_self_isomorphism(self): | |
91 """ | |
92 For some small, directed, symmetric graphs, make sure that 1) they are | |
93 isomorphic to themselves, and 2) that only the identity mapping is | |
94 found. | |
95 """ | |
96 for node_data, edge_data in self.data: | |
97 graph = nx.Graph() | |
98 graph.add_nodes_from(node_data) | |
99 graph.add_edges_from(edge_data) | |
100 | |
101 ismags = iso.ISMAGS( | |
102 graph, graph, node_match=iso.categorical_node_match("name", None) | |
103 ) | |
104 assert ismags.is_isomorphic() | |
105 assert ismags.subgraph_is_isomorphic() | |
106 assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [ | |
107 {n: n for n in graph.nodes} | |
108 ] | |
109 | |
110 | |
111 class TestSubgraphIsomorphism: | |
112 def test_isomorphism(self): | |
113 g1 = nx.Graph() | |
114 nx.add_cycle(g1, range(4)) | |
115 | |
116 g2 = nx.Graph() | |
117 nx.add_cycle(g2, range(4)) | |
118 g2.add_edges_from([(n, m) for n, m in zip(g2, range(4, 8))]) | |
119 ismags = iso.ISMAGS(g2, g1) | |
120 assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [ | |
121 {n: n for n in g1.nodes} | |
122 ] | |
123 | |
124 def test_isomorphism2(self): | |
125 g1 = nx.Graph() | |
126 nx.add_path(g1, range(3)) | |
127 | |
128 g2 = g1.copy() | |
129 g2.add_edge(1, 3) | |
130 | |
131 ismags = iso.ISMAGS(g2, g1) | |
132 matches = ismags.subgraph_isomorphisms_iter(symmetry=True) | |
133 expected_symmetric = [ | |
134 {0: 0, 1: 1, 2: 2}, | |
135 {0: 0, 1: 1, 3: 2}, | |
136 {2: 0, 1: 1, 3: 2}, | |
137 ] | |
138 assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric) | |
139 | |
140 matches = ismags.subgraph_isomorphisms_iter(symmetry=False) | |
141 expected_asymmetric = [ | |
142 {0: 2, 1: 1, 2: 0}, | |
143 {0: 2, 1: 1, 3: 0}, | |
144 {2: 2, 1: 1, 3: 0}, | |
145 ] | |
146 assert _matches_to_sets(matches) == _matches_to_sets( | |
147 expected_symmetric + expected_asymmetric | |
148 ) | |
149 | |
150 def test_labeled_nodes(self): | |
151 g1 = nx.Graph() | |
152 nx.add_cycle(g1, range(3)) | |
153 g1.nodes[1]["attr"] = True | |
154 | |
155 g2 = g1.copy() | |
156 g2.add_edge(1, 3) | |
157 ismags = iso.ISMAGS(g2, g1, node_match=lambda x, y: x == y) | |
158 matches = ismags.subgraph_isomorphisms_iter(symmetry=True) | |
159 expected_symmetric = [{0: 0, 1: 1, 2: 2}] | |
160 assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric) | |
161 | |
162 matches = ismags.subgraph_isomorphisms_iter(symmetry=False) | |
163 expected_asymmetric = [{0: 2, 1: 1, 2: 0}] | |
164 assert _matches_to_sets(matches) == _matches_to_sets( | |
165 expected_symmetric + expected_asymmetric | |
166 ) | |
167 | |
168 def test_labeled_edges(self): | |
169 g1 = nx.Graph() | |
170 nx.add_cycle(g1, range(3)) | |
171 g1.edges[1, 2]["attr"] = True | |
172 | |
173 g2 = g1.copy() | |
174 g2.add_edge(1, 3) | |
175 ismags = iso.ISMAGS(g2, g1, edge_match=lambda x, y: x == y) | |
176 matches = ismags.subgraph_isomorphisms_iter(symmetry=True) | |
177 expected_symmetric = [{0: 0, 1: 1, 2: 2}] | |
178 assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric) | |
179 | |
180 matches = ismags.subgraph_isomorphisms_iter(symmetry=False) | |
181 expected_asymmetric = [{1: 2, 0: 0, 2: 1}] | |
182 assert _matches_to_sets(matches) == _matches_to_sets( | |
183 expected_symmetric + expected_asymmetric | |
184 ) | |
185 | |
186 | |
187 class TestWikipediaExample: | |
188 # Nodes 'a', 'b', 'c' and 'd' form a column. | |
189 # Nodes 'g', 'h', 'i' and 'j' form a column. | |
190 g1edges = [ | |
191 ["a", "g"], | |
192 ["a", "h"], | |
193 ["a", "i"], | |
194 ["b", "g"], | |
195 ["b", "h"], | |
196 ["b", "j"], | |
197 ["c", "g"], | |
198 ["c", "i"], | |
199 ["c", "j"], | |
200 ["d", "h"], | |
201 ["d", "i"], | |
202 ["d", "j"], | |
203 ] | |
204 | |
205 # Nodes 1,2,3,4 form the clockwise corners of a large square. | |
206 # Nodes 5,6,7,8 form the clockwise corners of a small square | |
207 g2edges = [ | |
208 [1, 2], | |
209 [2, 3], | |
210 [3, 4], | |
211 [4, 1], | |
212 [5, 6], | |
213 [6, 7], | |
214 [7, 8], | |
215 [8, 5], | |
216 [1, 5], | |
217 [2, 6], | |
218 [3, 7], | |
219 [4, 8], | |
220 ] | |
221 | |
222 def test_graph(self): | |
223 g1 = nx.Graph() | |
224 g2 = nx.Graph() | |
225 g1.add_edges_from(self.g1edges) | |
226 g2.add_edges_from(self.g2edges) | |
227 gm = iso.ISMAGS(g1, g2) | |
228 assert gm.is_isomorphic() | |
229 | |
230 | |
231 class TestLargestCommonSubgraph: | |
232 def test_mcis(self): | |
233 # Example graphs from DOI: 10.1002/spe.588 | |
234 graph1 = nx.Graph() | |
235 graph1.add_edges_from([(1, 2), (2, 3), (2, 4), (3, 4), (4, 5)]) | |
236 graph1.nodes[1]["color"] = 0 | |
237 | |
238 graph2 = nx.Graph() | |
239 graph2.add_edges_from( | |
240 [(1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (5, 6), (5, 7), (6, 7)] | |
241 ) | |
242 graph2.nodes[1]["color"] = 1 | |
243 graph2.nodes[6]["color"] = 2 | |
244 graph2.nodes[7]["color"] = 2 | |
245 | |
246 ismags = iso.ISMAGS( | |
247 graph1, graph2, node_match=iso.categorical_node_match("color", None) | |
248 ) | |
249 assert list(ismags.subgraph_isomorphisms_iter(True)) == [] | |
250 assert list(ismags.subgraph_isomorphisms_iter(False)) == [] | |
251 found_mcis = _matches_to_sets(ismags.largest_common_subgraph()) | |
252 expected = _matches_to_sets( | |
253 [{2: 2, 3: 4, 4: 3, 5: 5}, {2: 4, 3: 2, 4: 3, 5: 5}] | |
254 ) | |
255 assert expected == found_mcis | |
256 | |
257 ismags = iso.ISMAGS( | |
258 graph2, graph1, node_match=iso.categorical_node_match("color", None) | |
259 ) | |
260 assert list(ismags.subgraph_isomorphisms_iter(True)) == [] | |
261 assert list(ismags.subgraph_isomorphisms_iter(False)) == [] | |
262 found_mcis = _matches_to_sets(ismags.largest_common_subgraph()) | |
263 # Same answer, but reversed. | |
264 expected = _matches_to_sets( | |
265 [{2: 2, 3: 4, 4: 3, 5: 5}, {4: 2, 2: 3, 3: 4, 5: 5}] | |
266 ) | |
267 assert expected == found_mcis | |
268 | |
269 def test_symmetry_mcis(self): | |
270 graph1 = nx.Graph() | |
271 nx.add_path(graph1, range(4)) | |
272 | |
273 graph2 = nx.Graph() | |
274 nx.add_path(graph2, range(3)) | |
275 graph2.add_edge(1, 3) | |
276 | |
277 # Only the symmetry of graph2 is taken into account here. | |
278 ismags1 = iso.ISMAGS( | |
279 graph1, graph2, node_match=iso.categorical_node_match("color", None) | |
280 ) | |
281 assert list(ismags1.subgraph_isomorphisms_iter(True)) == [] | |
282 found_mcis = _matches_to_sets(ismags1.largest_common_subgraph()) | |
283 expected = _matches_to_sets([{0: 0, 1: 1, 2: 2}, {1: 0, 3: 2, 2: 1}]) | |
284 assert expected == found_mcis | |
285 | |
286 # Only the symmetry of graph1 is taken into account here. | |
287 ismags2 = iso.ISMAGS( | |
288 graph2, graph1, node_match=iso.categorical_node_match("color", None) | |
289 ) | |
290 assert list(ismags2.subgraph_isomorphisms_iter(True)) == [] | |
291 found_mcis = _matches_to_sets(ismags2.largest_common_subgraph()) | |
292 expected = _matches_to_sets( | |
293 [ | |
294 {3: 2, 0: 0, 1: 1}, | |
295 {2: 0, 0: 2, 1: 1}, | |
296 {3: 0, 0: 2, 1: 1}, | |
297 {3: 0, 1: 1, 2: 2}, | |
298 {0: 0, 1: 1, 2: 2}, | |
299 {2: 0, 3: 2, 1: 1}, | |
300 ] | |
301 ) | |
302 | |
303 assert expected == found_mcis | |
304 | |
305 found_mcis1 = _matches_to_sets(ismags1.largest_common_subgraph(False)) | |
306 found_mcis2 = ismags2.largest_common_subgraph(False) | |
307 found_mcis2 = [{v: k for k, v in d.items()} for d in found_mcis2] | |
308 found_mcis2 = _matches_to_sets(found_mcis2) | |
309 | |
310 expected = _matches_to_sets( | |
311 [ | |
312 {3: 2, 1: 3, 2: 1}, | |
313 {2: 0, 0: 2, 1: 1}, | |
314 {1: 2, 3: 3, 2: 1}, | |
315 {3: 0, 1: 3, 2: 1}, | |
316 {0: 2, 2: 3, 1: 1}, | |
317 {3: 0, 1: 2, 2: 1}, | |
318 {2: 0, 0: 3, 1: 1}, | |
319 {0: 0, 2: 3, 1: 1}, | |
320 {1: 0, 3: 3, 2: 1}, | |
321 {1: 0, 3: 2, 2: 1}, | |
322 {0: 3, 1: 1, 2: 2}, | |
323 {0: 0, 1: 1, 2: 2}, | |
324 ] | |
325 ) | |
326 assert expected == found_mcis1 | |
327 assert expected == found_mcis2 |