### comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/matchhelpers.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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)
131 values2 = set()
132 for data2 in datasets2.values():
133 x = tuple(data2.get(attr, d) for attr, d in attrs)
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")