1
"""Functions which help end users define customize node_match and
2
edge_match functions to use during isomorphism checks.
3
"""
4 1
from itertools import permutations
5 1
import types
6

7 1
__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 1
def copyfunc(f, name=None):
21
    """Returns a deepcopy of a function."""
22 1
    return types.FunctionType(
23
        f.__code__, f.__globals__, name or f.__name__, f.__defaults__, f.__closure__
24
    )
25

26

27 1
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 1
    for xi, yi in zip(x, y):
40 1
        if not (abs(xi - yi) <= atol + rtol * abs(yi)):
41 1
            return False
42 1
    return True
43

44

45 1
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 1
    return abs(x - y) <= atol + rtol * abs(y)
58

59

60 1
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 1
def categorical_node_match(attr, default):
91 1
    if isinstance(attr, str):
92

93 1
        def match(data1, data2):
94 1
            return data1.get(attr, default) == data2.get(attr, default)
95

96
    else:
97 1
        attrs = list(zip(attr, default))  # Python 3
98

99 1
        def match(data1, data2):
100 1
            return all(data1.get(attr, d) == data2.get(attr, d) for attr, d in attrs)
101

102 1
    return match
103

104

105 1
categorical_edge_match = copyfunc(categorical_node_match, "categorical_edge_match")
106

107

108 1
def categorical_multiedge_match(attr, default):
109 1
    if isinstance(attr, str):
110

111 1
        def match(datasets1, datasets2):
112 1
            values1 = {data.get(attr, default) for data in datasets1.values()}
113 1
            values2 = {data.get(attr, default) for data in datasets2.values()}
114 1
            return values1 == values2
115

116
    else:
117 1
        attrs = list(zip(attr, default))  # Python 3
118

119 1
        def match(datasets1, datasets2):
120 1
            values1 = set()
121 1
            for data1 in datasets1.values():
122 1
                x = tuple(data1.get(attr, d) for attr, d in attrs)
123 1
                values1.add(x)
124 1
            values2 = set()
125 1
            for data2 in datasets2.values():
126 1
                x = tuple(data2.get(attr, d) for attr, d in attrs)
127 1
                values2.add(x)
128 1
            return values1 == values2
129

130 1
    return match
131

132

133
# Docstrings for categorical functions.
134 1
categorical_node_match.__doc__ = categorical_doc
135 1
categorical_edge_match.__doc__ = categorical_doc.replace("node", "edge")
136 1
tmpdoc = categorical_doc.replace("node", "edge")
137 1
tmpdoc = tmpdoc.replace("categorical_edge_match", "categorical_multiedge_match")
138 1
categorical_multiedge_match.__doc__ = tmpdoc
139

140

141 1
numerical_doc = """
142
Returns a comparison function for a numerical node attribute.
143

144
The value(s) of the attr(s) must be numerical and sortable.  If the
145
sorted list of values from G1 and G2 are the same within some
146
tolerance, then the constructed function returns True.
147

148
Parameters
149
----------
150
attr : string | list
151
    The numerical node attribute to compare, or a list of numerical
152
    node attributes to compare.
153
default : value | list
154
    The default value for the numerical node attribute, or a list of
155
    default values for the numerical node attributes.
156
rtol : float
157
    The relative error tolerance.
158
atol : float
159
    The absolute error tolerance.
160

161
Returns
162
-------
163
match : function
164
    The customized, numerical `node_match` function.
165

166
Examples
167
--------
168
>>> import networkx.algorithms.isomorphism as iso
169
>>> nm = iso.numerical_node_match("weight", 1.0)
170
>>> nm = iso.numerical_node_match(["weight", "linewidth"], [0.25, 0.5])
171

172
"""
173

174

175 1
def numerical_node_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08):
176 1
    if isinstance(attr, str):
177

178 1
        def match(data1, data2):
179 1
            return close(
180
                data1.get(attr, default), data2.get(attr, default), rtol=rtol, atol=atol
181
            )
182

183
    else:
184 1
        attrs = list(zip(attr, default))  # Python 3
185

186 1
        def match(data1, data2):
187 1
            values1 = [data1.get(attr, d) for attr, d in attrs]
188 1
            values2 = [data2.get(attr, d) for attr, d in attrs]
189 0
            return allclose(values1, values2, rtol=rtol, atol=atol)
190

191 1
    return match
192

193

194 1
numerical_edge_match = copyfunc(numerical_node_match, "numerical_edge_match")
195

196

197 1
def numerical_multiedge_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08):
198 1
    if isinstance(attr, str):
199

200 1
        def match(datasets1, datasets2):
201 1
            values1 = sorted([data.get(attr, default) for data in datasets1.values()])
202 1
            values2 = sorted([data.get(attr, default) for data in datasets2.values()])
203 1
            return allclose(values1, values2, rtol=rtol, atol=atol)
204

205
    else:
206 1
        attrs = list(zip(attr, default))  # Python 3
207

208 1
        def match(datasets1, datasets2):
209 1
            values1 = []
210 1
            for data1 in datasets1.values():
211 1
                x = tuple(data1.get(attr, d) for attr, d in attrs)
212 1
                values1.append(x)
213 1
            values2 = []
214 1
            for data2 in datasets2.values():
215 1
                x = tuple(data2.get(attr, d) for attr, d in attrs)
216 1
                values2.append(x)
217 1
            values1.sort()
218 1
            values2.sort()
219 1
            for xi, yi in zip(values1, values2):
220 1
                if not allclose(xi, yi, rtol=rtol, atol=atol):
221 0
                    return False
222
            else:
223 1
                return True
224

225 1
    return match
226

227

228
# Docstrings for numerical functions.
229 1
numerical_node_match.__doc__ = numerical_doc
230 1
numerical_edge_match.__doc__ = numerical_doc.replace("node", "edge")
231 1
tmpdoc = numerical_doc.replace("node", "edge")
232 1
tmpdoc = tmpdoc.replace("numerical_edge_match", "numerical_multiedge_match")
233 1
numerical_multiedge_match.__doc__ = tmpdoc
234

235

236 1
generic_doc = """
237
Returns a comparison function for a generic attribute.
238

239
The value(s) of the attr(s) are compared using the specified
240
operators. If all the attributes are equal, then the constructed
241
function returns True.
242

243
Parameters
244
----------
245
attr : string | list
246
    The node attribute to compare, or a list of node attributes
247
    to compare.
248
default : value | list
249
    The default value for the node attribute, or a list of
250
    default values for the node attributes.
251
op : callable | list
252
    The operator to use when comparing attribute values, or a list
253
    of operators to use when comparing values for each attribute.
254

255
Returns
256
-------
257
match : function
258
    The customized, generic `node_match` function.
259

260
Examples
261
--------
262
>>> from operator import eq
263
>>> from networkx.algorithms.isomorphism.matchhelpers import close
264
>>> from networkx.algorithms.isomorphism import generic_node_match
265
>>> nm = generic_node_match("weight", 1.0, close)
266
>>> nm = generic_node_match("color", "red", eq)
267
>>> nm = generic_node_match(["weight", "color"], [1.0, "red"], [close, eq])
268

269
"""
270

271

272 1
def generic_node_match(attr, default, op):
273 1
    if isinstance(attr, str):
274

275 1
        def match(data1, data2):
276 0
            return op(data1.get(attr, default), data2.get(attr, default))
277

278
    else:
279 1
        attrs = list(zip(attr, default, op))  # Python 3
280

281 1
        def match(data1, data2):
282 1
            for attr, d, operator in attrs:
283 1
                if not operator(data1.get(attr, d), data2.get(attr, d)):
284 0
                    return False
285
            else:
286 0
                return True
287

288 1
    return match
289

290

291 1
generic_edge_match = copyfunc(generic_node_match, "generic_edge_match")
292

293

294 1
def generic_multiedge_match(attr, default, op):
295
    """Returns a comparison function for a generic attribute.
296

297
    The value(s) of the attr(s) are compared using the specified
298
    operators. If all the attributes are equal, then the constructed
299
    function returns True. Potentially, the constructed edge_match
300
    function can be slow since it must verify that no isomorphism
301
    exists between the multiedges before it returns False.
302

303
    Parameters
304
    ----------
305
    attr : string | list
306
        The edge attribute to compare, or a list of node attributes
307
        to compare.
308
    default : value | list
309
        The default value for the edge attribute, or a list of
310
        default values for the dgeattributes.
311
    op : callable | list
312
        The operator to use when comparing attribute values, or a list
313
        of operators to use when comparing values for each attribute.
314

315
    Returns
316
    -------
317
    match : function
318
        The customized, generic `edge_match` function.
319

320
    Examples
321
    --------
322
    >>> from operator import eq
323
    >>> from networkx.algorithms.isomorphism.matchhelpers import close
324
    >>> from networkx.algorithms.isomorphism import generic_node_match
325
    >>> nm = generic_node_match("weight", 1.0, close)
326
    >>> nm = generic_node_match("color", "red", eq)
327
    >>> nm = generic_node_match(["weight", "color"], [1.0, "red"], [close, eq])
328
    ...
329

330
    """
331

332
    # This is slow, but generic.
333
    # We must test every possible isomorphism between the edges.
334 1
    if isinstance(attr, str):
335 1
        attr = [attr]
336 1
        default = [default]
337 1
        op = [op]
338 1
    attrs = list(zip(attr, default))  # Python 3
339

340 1
    def match(datasets1, datasets2):
341 1
        values1 = []
342 1
        for data1 in datasets1.values():
343 1
            x = tuple(data1.get(attr, d) for attr, d in attrs)
344 1
            values1.append(x)
345 1
        values2 = []
346 1
        for data2 in datasets2.values():
347 1
            x = tuple(data2.get(attr, d) for attr, d in attrs)
348 1
            values2.append(x)
349 1
        for vals2 in permutations(values2):
350 1
            for xi, yi in zip(values1, vals2):
351 1
                if not all(map(lambda x, y, z: z(x, y), xi, yi, op)):
352
                    # This is not an isomorphism, go to next permutation.
353 1
                    break
354
            else:
355
                # Then we found an isomorphism.
356 1
                return True
357
        else:
358
            # Then there are no isomorphisms between the multiedges.
359 1
            return False
360

361 1
    return match
362

363

364
# Docstrings for numerical functions.
365 1
generic_node_match.__doc__ = generic_doc
366 1
generic_edge_match.__doc__ = generic_doc.replace("node", "edge")

Read our documentation on viewing source code .

Loading