Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/matchhelpers.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 """Functions which help end users define customize node_match and | |
2 edge_match functions to use during isomorphism checks. | |
3 """ | |
4 from itertools import permutations | |
5 import types | |
6 | |
7 __all__ = [ | |
8 "categorical_node_match", | |
9 "categorical_edge_match", | |
10 "categorical_multiedge_match", | |
11 "numerical_node_match", | |
12 "numerical_edge_match", | |
13 "numerical_multiedge_match", | |
14 "generic_node_match", | |
15 "generic_edge_match", | |
16 "generic_multiedge_match", | |
17 ] | |
18 | |
19 | |
20 def copyfunc(f, name=None): | |
21 """Returns a deepcopy of a function.""" | |
22 return types.FunctionType( | |
23 f.__code__, f.__globals__, name or f.__name__, f.__defaults__, f.__closure__ | |
24 ) | |
25 | |
26 | |
27 def allclose(x, y, rtol=1.0000000000000001e-05, atol=1e-08): | |
28 """Returns True if x and y are sufficiently close, elementwise. | |
29 | |
30 Parameters | |
31 ---------- | |
32 rtol : float | |
33 The relative error tolerance. | |
34 atol : float | |
35 The absolute error tolerance. | |
36 | |
37 """ | |
38 # assume finite weights, see numpy.allclose() for reference | |
39 for xi, yi in zip(x, y): | |
40 if not (abs(xi - yi) <= atol + rtol * abs(yi)): | |
41 return False | |
42 return True | |
43 | |
44 | |
45 def close(x, y, rtol=1.0000000000000001e-05, atol=1e-08): | |
46 """Returns True if x and y are sufficiently close. | |
47 | |
48 Parameters | |
49 ---------- | |
50 rtol : float | |
51 The relative error tolerance. | |
52 atol : float | |
53 The absolute error tolerance. | |
54 | |
55 """ | |
56 # assume finite weights, see numpy.allclose() for reference | |
57 return abs(x - y) <= atol + rtol * abs(y) | |
58 | |
59 | |
60 categorical_doc = """ | |
61 Returns a comparison function for a categorical node attribute. | |
62 | |
63 The value(s) of the attr(s) must be hashable and comparable via the == | |
64 operator since they are placed into a set([]) object. If the sets from | |
65 G1 and G2 are the same, then the constructed function returns True. | |
66 | |
67 Parameters | |
68 ---------- | |
69 attr : string | list | |
70 The categorical node attribute to compare, or a list of categorical | |
71 node attributes to compare. | |
72 default : value | list | |
73 The default value for the categorical node attribute, or a list of | |
74 default values for the categorical node attributes. | |
75 | |
76 Returns | |
77 ------- | |
78 match : function | |
79 The customized, categorical `node_match` function. | |
80 | |
81 Examples | |
82 -------- | |
83 >>> import networkx.algorithms.isomorphism as iso | |
84 >>> nm = iso.categorical_node_match("size", 1) | |
85 >>> nm = iso.categorical_node_match(["color", "size"], ["red", 2]) | |
86 | |
87 """ | |
88 | |
89 | |
90 def categorical_node_match(attr, default): | |
91 if isinstance(attr, str): | |
92 | |
93 def match(data1, data2): | |
94 return data1.get(attr, default) == data2.get(attr, default) | |
95 | |
96 else: | |
97 attrs = list(zip(attr, default)) # Python 3 | |
98 | |
99 def match(data1, data2): | |
100 return all(data1.get(attr, d) == data2.get(attr, d) for attr, d in attrs) | |
101 | |
102 return match | |
103 | |
104 | |
105 try: | |
106 categorical_edge_match = copyfunc(categorical_node_match, "categorical_edge_match") | |
107 except NotImplementedError: | |
108 # IronPython lacks support for types.FunctionType. | |
109 # https://github.com/networkx/networkx/issues/949 | |
110 # https://github.com/networkx/networkx/issues/1127 | |
111 def categorical_edge_match(*args, **kwargs): | |
112 return categorical_node_match(*args, **kwargs) | |
113 | |
114 | |
115 def categorical_multiedge_match(attr, default): | |
116 if isinstance(attr, str): | |
117 | |
118 def match(datasets1, datasets2): | |
119 values1 = {data.get(attr, default) for data in datasets1.values()} | |
120 values2 = {data.get(attr, default) for data in datasets2.values()} | |
121 return values1 == values2 | |
122 | |
123 else: | |
124 attrs = list(zip(attr, default)) # Python 3 | |
125 | |
126 def match(datasets1, datasets2): | |
127 values1 = set() | |
128 for data1 in datasets1.values(): | |
129 x = tuple(data1.get(attr, d) for attr, d in attrs) | |
130 values1.add(x) | |
131 values2 = set() | |
132 for data2 in datasets2.values(): | |
133 x = tuple(data2.get(attr, d) for attr, d in attrs) | |
134 values2.add(x) | |
135 return values1 == values2 | |
136 | |
137 return match | |
138 | |
139 | |
140 # Docstrings for categorical functions. | |
141 categorical_node_match.__doc__ = categorical_doc | |
142 categorical_edge_match.__doc__ = categorical_doc.replace("node", "edge") | |
143 tmpdoc = categorical_doc.replace("node", "edge") | |
144 tmpdoc = tmpdoc.replace("categorical_edge_match", "categorical_multiedge_match") | |
145 categorical_multiedge_match.__doc__ = tmpdoc | |
146 | |
147 | |
148 numerical_doc = """ | |
149 Returns a comparison function for a numerical node attribute. | |
150 | |
151 The value(s) of the attr(s) must be numerical and sortable. If the | |
152 sorted list of values from G1 and G2 are the same within some | |
153 tolerance, then the constructed function returns True. | |
154 | |
155 Parameters | |
156 ---------- | |
157 attr : string | list | |
158 The numerical node attribute to compare, or a list of numerical | |
159 node attributes to compare. | |
160 default : value | list | |
161 The default value for the numerical node attribute, or a list of | |
162 default values for the numerical node attributes. | |
163 rtol : float | |
164 The relative error tolerance. | |
165 atol : float | |
166 The absolute error tolerance. | |
167 | |
168 Returns | |
169 ------- | |
170 match : function | |
171 The customized, numerical `node_match` function. | |
172 | |
173 Examples | |
174 -------- | |
175 >>> import networkx.algorithms.isomorphism as iso | |
176 >>> nm = iso.numerical_node_match("weight", 1.0) | |
177 >>> nm = iso.numerical_node_match(["weight", "linewidth"], [0.25, 0.5]) | |
178 | |
179 """ | |
180 | |
181 | |
182 def numerical_node_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08): | |
183 if isinstance(attr, str): | |
184 | |
185 def match(data1, data2): | |
186 return close( | |
187 data1.get(attr, default), data2.get(attr, default), rtol=rtol, atol=atol | |
188 ) | |
189 | |
190 else: | |
191 attrs = list(zip(attr, default)) # Python 3 | |
192 | |
193 def match(data1, data2): | |
194 values1 = [data1.get(attr, d) for attr, d in attrs] | |
195 values2 = [data2.get(attr, d) for attr, d in attrs] | |
196 return allclose(values1, values2, rtol=rtol, atol=atol) | |
197 | |
198 return match | |
199 | |
200 | |
201 try: | |
202 numerical_edge_match = copyfunc(numerical_node_match, "numerical_edge_match") | |
203 except NotImplementedError: | |
204 # IronPython lacks support for types.FunctionType. | |
205 # https://github.com/networkx/networkx/issues/949 | |
206 # https://github.com/networkx/networkx/issues/1127 | |
207 def numerical_edge_match(*args, **kwargs): | |
208 return numerical_node_match(*args, **kwargs) | |
209 | |
210 | |
211 def numerical_multiedge_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08): | |
212 if isinstance(attr, str): | |
213 | |
214 def match(datasets1, datasets2): | |
215 values1 = sorted([data.get(attr, default) for data in datasets1.values()]) | |
216 values2 = sorted([data.get(attr, default) for data in datasets2.values()]) | |
217 return allclose(values1, values2, rtol=rtol, atol=atol) | |
218 | |
219 else: | |
220 attrs = list(zip(attr, default)) # Python 3 | |
221 | |
222 def match(datasets1, datasets2): | |
223 values1 = [] | |
224 for data1 in datasets1.values(): | |
225 x = tuple(data1.get(attr, d) for attr, d in attrs) | |
226 values1.append(x) | |
227 values2 = [] | |
228 for data2 in datasets2.values(): | |
229 x = tuple(data2.get(attr, d) for attr, d in attrs) | |
230 values2.append(x) | |
231 values1.sort() | |
232 values2.sort() | |
233 for xi, yi in zip(values1, values2): | |
234 if not allclose(xi, yi, rtol=rtol, atol=atol): | |
235 return False | |
236 else: | |
237 return True | |
238 | |
239 return match | |
240 | |
241 | |
242 # Docstrings for numerical functions. | |
243 numerical_node_match.__doc__ = numerical_doc | |
244 numerical_edge_match.__doc__ = numerical_doc.replace("node", "edge") | |
245 tmpdoc = numerical_doc.replace("node", "edge") | |
246 tmpdoc = tmpdoc.replace("numerical_edge_match", "numerical_multiedge_match") | |
247 numerical_multiedge_match.__doc__ = tmpdoc | |
248 | |
249 | |
250 generic_doc = """ | |
251 Returns a comparison function for a generic attribute. | |
252 | |
253 The value(s) of the attr(s) are compared using the specified | |
254 operators. If all the attributes are equal, then the constructed | |
255 function returns True. | |
256 | |
257 Parameters | |
258 ---------- | |
259 attr : string | list | |
260 The node attribute to compare, or a list of node attributes | |
261 to compare. | |
262 default : value | list | |
263 The default value for the node attribute, or a list of | |
264 default values for the node attributes. | |
265 op : callable | list | |
266 The operator to use when comparing attribute values, or a list | |
267 of operators to use when comparing values for each attribute. | |
268 | |
269 Returns | |
270 ------- | |
271 match : function | |
272 The customized, generic `node_match` function. | |
273 | |
274 Examples | |
275 -------- | |
276 >>> from operator import eq | |
277 >>> from networkx.algorithms.isomorphism.matchhelpers import close | |
278 >>> from networkx.algorithms.isomorphism import generic_node_match | |
279 >>> nm = generic_node_match("weight", 1.0, close) | |
280 >>> nm = generic_node_match("color", "red", eq) | |
281 >>> nm = generic_node_match(["weight", "color"], [1.0, "red"], [close, eq]) | |
282 | |
283 """ | |
284 | |
285 | |
286 def generic_node_match(attr, default, op): | |
287 if isinstance(attr, str): | |
288 | |
289 def match(data1, data2): | |
290 return op(data1.get(attr, default), data2.get(attr, default)) | |
291 | |
292 else: | |
293 attrs = list(zip(attr, default, op)) # Python 3 | |
294 | |
295 def match(data1, data2): | |
296 for attr, d, operator in attrs: | |
297 if not operator(data1.get(attr, d), data2.get(attr, d)): | |
298 return False | |
299 else: | |
300 return True | |
301 | |
302 return match | |
303 | |
304 | |
305 try: | |
306 generic_edge_match = copyfunc(generic_node_match, "generic_edge_match") | |
307 except NotImplementedError: | |
308 # IronPython lacks support for types.FunctionType. | |
309 # https://github.com/networkx/networkx/issues/949 | |
310 # https://github.com/networkx/networkx/issues/1127 | |
311 def generic_edge_match(*args, **kwargs): | |
312 return generic_node_match(*args, **kwargs) | |
313 | |
314 | |
315 def generic_multiedge_match(attr, default, op): | |
316 """Returns a comparison function for a generic attribute. | |
317 | |
318 The value(s) of the attr(s) are compared using the specified | |
319 operators. If all the attributes are equal, then the constructed | |
320 function returns True. Potentially, the constructed edge_match | |
321 function can be slow since it must verify that no isomorphism | |
322 exists between the multiedges before it returns False. | |
323 | |
324 Parameters | |
325 ---------- | |
326 attr : string | list | |
327 The edge attribute to compare, or a list of node attributes | |
328 to compare. | |
329 default : value | list | |
330 The default value for the edge attribute, or a list of | |
331 default values for the dgeattributes. | |
332 op : callable | list | |
333 The operator to use when comparing attribute values, or a list | |
334 of operators to use when comparing values for each attribute. | |
335 | |
336 Returns | |
337 ------- | |
338 match : function | |
339 The customized, generic `edge_match` function. | |
340 | |
341 Examples | |
342 -------- | |
343 >>> from operator import eq | |
344 >>> from networkx.algorithms.isomorphism.matchhelpers import close | |
345 >>> from networkx.algorithms.isomorphism import generic_node_match | |
346 >>> nm = generic_node_match("weight", 1.0, close) | |
347 >>> nm = generic_node_match("color", "red", eq) | |
348 >>> nm = generic_node_match(["weight", "color"], [1.0, "red"], [close, eq]) | |
349 ... | |
350 | |
351 """ | |
352 | |
353 # This is slow, but generic. | |
354 # We must test every possible isomorphism between the edges. | |
355 if isinstance(attr, str): | |
356 attr = [attr] | |
357 default = [default] | |
358 op = [op] | |
359 attrs = list(zip(attr, default)) # Python 3 | |
360 | |
361 def match(datasets1, datasets2): | |
362 values1 = [] | |
363 for data1 in datasets1.values(): | |
364 x = tuple(data1.get(attr, d) for attr, d in attrs) | |
365 values1.append(x) | |
366 values2 = [] | |
367 for data2 in datasets2.values(): | |
368 x = tuple(data2.get(attr, d) for attr, d in attrs) | |
369 values2.append(x) | |
370 for vals2 in permutations(values2): | |
371 for xi, yi in zip(values1, vals2): | |
372 if not all(map(lambda x, y, z: z(x, y), xi, yi, op)): | |
373 # This is not an isomorphism, go to next permutation. | |
374 break | |
375 else: | |
376 # Then we found an isomorphism. | |
377 return True | |
378 else: | |
379 # Then there are no isomorphisms between the multiedges. | |
380 return False | |
381 | |
382 return match | |
383 | |
384 | |
385 # Docstrings for numerical functions. | |
386 generic_node_match.__doc__ = generic_doc | |
387 generic_edge_match.__doc__ = generic_doc.replace("node", "edge") |