Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/tests/test_tree_isomorphism.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 networkx as nx | |
2 import random | |
3 import time | |
4 from networkx.classes.function import is_directed | |
5 | |
6 from networkx.algorithms.isomorphism.tree_isomorphism import ( | |
7 rooted_tree_isomorphism, | |
8 tree_isomorphism, | |
9 ) | |
10 | |
11 | |
12 # have this work for graph | |
13 # given two trees (either the directed or undirected) | |
14 # transform t2 according to the isomorphism | |
15 # and confirm it is identical to t1 | |
16 # randomize the order of the edges when constructing | |
17 def check_isomorphism(t1, t2, isomorphism): | |
18 | |
19 # get the name of t1, given the name in t2 | |
20 mapping = {v2: v1 for (v1, v2) in isomorphism} | |
21 | |
22 # these should be the same | |
23 d1 = is_directed(t1) | |
24 d2 = is_directed(t2) | |
25 assert d1 == d2 | |
26 | |
27 edges_1 = [] | |
28 for (u, v) in t1.edges(): | |
29 if d1: | |
30 edges_1.append((u, v)) | |
31 else: | |
32 # if not directed, then need to | |
33 # put the edge in a consistent direction | |
34 if u < v: | |
35 edges_1.append((u, v)) | |
36 else: | |
37 edges_1.append((v, u)) | |
38 | |
39 edges_2 = [] | |
40 for (u, v) in t2.edges(): | |
41 # translate to names for t1 | |
42 u = mapping[u] | |
43 v = mapping[v] | |
44 if d2: | |
45 edges_2.append((u, v)) | |
46 else: | |
47 if u < v: | |
48 edges_2.append((u, v)) | |
49 else: | |
50 edges_2.append((v, u)) | |
51 | |
52 return sorted(edges_1) == sorted(edges_2) | |
53 | |
54 | |
55 def test_hardcoded(): | |
56 | |
57 print("hardcoded test") | |
58 | |
59 # define a test problem | |
60 edges_1 = [ | |
61 ("a", "b"), | |
62 ("a", "c"), | |
63 ("a", "d"), | |
64 ("b", "e"), | |
65 ("b", "f"), | |
66 ("e", "j"), | |
67 ("e", "k"), | |
68 ("c", "g"), | |
69 ("c", "h"), | |
70 ("g", "m"), | |
71 ("d", "i"), | |
72 ("f", "l"), | |
73 ] | |
74 | |
75 edges_2 = [ | |
76 ("v", "y"), | |
77 ("v", "z"), | |
78 ("u", "x"), | |
79 ("q", "u"), | |
80 ("q", "v"), | |
81 ("p", "t"), | |
82 ("n", "p"), | |
83 ("n", "q"), | |
84 ("n", "o"), | |
85 ("o", "r"), | |
86 ("o", "s"), | |
87 ("s", "w"), | |
88 ] | |
89 | |
90 # there are two possible correct isomorphisms | |
91 # it currently returns isomorphism1 | |
92 # but the second is also correct | |
93 isomorphism1 = [ | |
94 ("a", "n"), | |
95 ("b", "q"), | |
96 ("c", "o"), | |
97 ("d", "p"), | |
98 ("e", "v"), | |
99 ("f", "u"), | |
100 ("g", "s"), | |
101 ("h", "r"), | |
102 ("i", "t"), | |
103 ("j", "y"), | |
104 ("k", "z"), | |
105 ("l", "x"), | |
106 ("m", "w"), | |
107 ] | |
108 | |
109 # could swap y and z | |
110 isomorphism2 = [ | |
111 ("a", "n"), | |
112 ("b", "q"), | |
113 ("c", "o"), | |
114 ("d", "p"), | |
115 ("e", "v"), | |
116 ("f", "u"), | |
117 ("g", "s"), | |
118 ("h", "r"), | |
119 ("i", "t"), | |
120 ("j", "z"), | |
121 ("k", "y"), | |
122 ("l", "x"), | |
123 ("m", "w"), | |
124 ] | |
125 | |
126 t1 = nx.Graph() | |
127 t1.add_edges_from(edges_1) | |
128 root1 = "a" | |
129 | |
130 t2 = nx.Graph() | |
131 t2.add_edges_from(edges_2) | |
132 root2 = "n" | |
133 | |
134 isomorphism = sorted(rooted_tree_isomorphism(t1, root1, t2, root2)) | |
135 | |
136 # is correct by hand | |
137 assert (isomorphism == isomorphism1) or (isomorphism == isomorphism2) | |
138 | |
139 # check algorithmically | |
140 assert check_isomorphism(t1, t2, isomorphism) | |
141 | |
142 # try again as digraph | |
143 t1 = nx.DiGraph() | |
144 t1.add_edges_from(edges_1) | |
145 root1 = "a" | |
146 | |
147 t2 = nx.DiGraph() | |
148 t2.add_edges_from(edges_2) | |
149 root2 = "n" | |
150 | |
151 isomorphism = sorted(rooted_tree_isomorphism(t1, root1, t2, root2)) | |
152 | |
153 # is correct by hand | |
154 assert (isomorphism == isomorphism1) or (isomorphism == isomorphism2) | |
155 | |
156 # check algorithmically | |
157 assert check_isomorphism(t1, t2, isomorphism) | |
158 | |
159 | |
160 # randomly swap a tuple (a,b) | |
161 def random_swap(t): | |
162 (a, b) = t | |
163 if random.randint(0, 1) == 1: | |
164 return (a, b) | |
165 else: | |
166 return (b, a) | |
167 | |
168 | |
169 # given a tree t1, create a new tree t2 | |
170 # that is isomorphic to t1, with a known isomorphism | |
171 # and test that our algorithm found the right one | |
172 def positive_single_tree(t1): | |
173 | |
174 assert nx.is_tree(t1) | |
175 | |
176 nodes1 = [n for n in t1.nodes()] | |
177 # get a random permutation of this | |
178 nodes2 = nodes1.copy() | |
179 random.shuffle(nodes2) | |
180 | |
181 # this is one isomorphism, however they may be multiple | |
182 # so we don't necessarily get this one back | |
183 someisomorphism = [(u, v) for (u, v) in zip(nodes1, nodes2)] | |
184 | |
185 # map from old to new | |
186 map1to2 = {u: v for (u, v) in someisomorphism} | |
187 | |
188 # get the edges with the transformed names | |
189 edges2 = [random_swap((map1to2[u], map1to2[v])) for (u, v) in t1.edges()] | |
190 # randomly permute, to ensure we're not relying on edge order somehow | |
191 random.shuffle(edges2) | |
192 | |
193 # so t2 is isomorphic to t1 | |
194 t2 = nx.Graph() | |
195 t2.add_edges_from(edges2) | |
196 | |
197 # lets call our code to see if t1 and t2 are isomorphic | |
198 isomorphism = tree_isomorphism(t1, t2) | |
199 | |
200 # make sure we got a correct solution | |
201 # although not necessarily someisomorphism | |
202 assert len(isomorphism) > 0 | |
203 assert check_isomorphism(t1, t2, isomorphism) | |
204 | |
205 | |
206 # run positive_single_tree over all the | |
207 # non-isomorphic trees for k from 4 to maxk | |
208 # k = 4 is the first level that has more than 1 non-isomorphic tree | |
209 # k = 13 takes about 2.86 seconds to run on my laptop | |
210 # larger values run slow down significantly | |
211 # as the number of trees grows rapidly | |
212 def test_positive(maxk=14): | |
213 | |
214 print("positive test") | |
215 | |
216 for k in range(2, maxk + 1): | |
217 start_time = time.time() | |
218 trial = 0 | |
219 for t in nx.nonisomorphic_trees(k): | |
220 positive_single_tree(t) | |
221 trial += 1 | |
222 print(k, trial, time.time() - start_time) | |
223 | |
224 | |
225 # test the trivial case of a single node in each tree | |
226 # note that nonisomorphic_trees doesn't work for k = 1 | |
227 def test_trivial(): | |
228 | |
229 print("trivial test") | |
230 | |
231 # back to an undirected graph | |
232 t1 = nx.Graph() | |
233 t1.add_node("a") | |
234 root1 = "a" | |
235 | |
236 t2 = nx.Graph() | |
237 t2.add_node("n") | |
238 root2 = "n" | |
239 | |
240 isomorphism = rooted_tree_isomorphism(t1, root1, t2, root2) | |
241 | |
242 assert isomorphism == [("a", "n")] | |
243 | |
244 assert check_isomorphism(t1, t2, isomorphism) | |
245 | |
246 | |
247 # test another trivial case where the two graphs have | |
248 # different numbers of nodes | |
249 def test_trivial_2(): | |
250 | |
251 print("trivial test 2") | |
252 | |
253 edges_1 = [("a", "b"), ("a", "c")] | |
254 | |
255 edges_2 = [("v", "y")] | |
256 | |
257 t1 = nx.Graph() | |
258 t1.add_edges_from(edges_1) | |
259 | |
260 t2 = nx.Graph() | |
261 t2.add_edges_from(edges_2) | |
262 | |
263 isomorphism = tree_isomorphism(t1, t2) | |
264 | |
265 # they cannot be isomorphic, | |
266 # since they have different numbers of nodes | |
267 assert isomorphism == [] | |
268 | |
269 | |
270 # the function nonisomorphic_trees generates all the non-isomorphic | |
271 # trees of a given size. Take each pair of these and verify that | |
272 # they are not isomorphic | |
273 # k = 4 is the first level that has more than 1 non-isomorphic tree | |
274 # k = 11 takes about 4.76 seconds to run on my laptop | |
275 # larger values run slow down significantly | |
276 # as the number of trees grows rapidly | |
277 def test_negative(maxk=11): | |
278 | |
279 print("negative test") | |
280 | |
281 for k in range(4, maxk + 1): | |
282 test_trees = list(nx.nonisomorphic_trees(k)) | |
283 start_time = time.time() | |
284 trial = 0 | |
285 for i in range(len(test_trees) - 1): | |
286 for j in range(i + 1, len(test_trees)): | |
287 trial += 1 | |
288 assert tree_isomorphism(test_trees[i], test_trees[j]) == [] | |
289 print(k, trial, time.time() - start_time) |