Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / isomorphism / matchhelpers.py @ 5cef0f13

History | View | Annotate | Download (12.4 KB)

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
import networkx as nx
7

    
8
__all__ = ['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
    try:
23
        # Python <3
24
        return types.FunctionType(f.func_code, f.func_globals,
25
                                  name or f.__name__, f.func_defaults,
26
                                  f.func_closure)
27
    except AttributeError:
28
        # Python >=3
29
        return types.FunctionType(f.__code__, f.__globals__,
30
                                  name or f.__name__, f.__defaults__,
31
                                  f.__closure__)
32

    
33

    
34
def allclose(x, y, rtol=1.0000000000000001e-05, atol=1e-08):
35
    """Returns True if x and y are sufficiently close, elementwise.
36

37
    Parameters
38
    ----------
39
    rtol : float
40
        The relative error tolerance.
41
    atol : float
42
        The absolute error tolerance.
43

44
    """
45
    # assume finite weights, see numpy.allclose() for reference
46
    for xi, yi in zip(x, y):
47
        if not (abs(xi - yi) <= atol + rtol * abs(yi)):
48
            return False
49
    return True
50

    
51

    
52
def close(x, y, rtol=1.0000000000000001e-05, atol=1e-08):
53
    """Returns True if x and y are sufficiently close.
54

55
    Parameters
56
    ----------
57
    rtol : float
58
        The relative error tolerance.
59
    atol : float
60
        The absolute error tolerance.
61

62
    """
63
    # assume finite weights, see numpy.allclose() for reference
64
    return abs(x - y) <= atol + rtol * abs(y)
65

    
66

    
67
categorical_doc = """
68
Returns a comparison function for a categorical node attribute.
69

70
The value(s) of the attr(s) must be hashable and comparable via the ==
71
operator since they are placed into a set([]) object.  If the sets from
72
G1 and G2 are the same, then the constructed function returns True.
73

74
Parameters
75
----------
76
attr : string | list
77
    The categorical node attribute to compare, or a list of categorical
78
    node attributes to compare.
79
default : value | list
80
    The default value for the categorical node attribute, or a list of
81
    default values for the categorical node attributes.
82

83
Returns
84
-------
85
match : function
86
    The customized, categorical `node_match` function.
87

88
Examples
89
--------
90
>>> import networkx.algorithms.isomorphism as iso
91
>>> nm = iso.categorical_node_match('size', 1)
92
>>> nm = iso.categorical_node_match(['color', 'size'], ['red', 2])
93

94
"""
95

    
96

    
97
def categorical_node_match(attr, default):
98
    if nx.utils.is_string_like(attr):
99
        def match(data1, data2):
100
            return data1.get(attr, default) == data2.get(attr, default)
101
    else:
102
        attrs = list(zip(attr, default))  # Python 3
103

    
104
        def match(data1, data2):
105
            return all(data1.get(attr, d) == data2.get(attr, d) for attr, d in attrs)
106
    return match
107

    
108

    
109
try:
110
    categorical_edge_match = copyfunc(categorical_node_match, 'categorical_edge_match')
111
except NotImplementedError:
112
    # IronPython lacks support for types.FunctionType.
113
    # https://github.com/networkx/networkx/issues/949
114
    # https://github.com/networkx/networkx/issues/1127
115
    def categorical_edge_match(*args, **kwargs):
116
        return categorical_node_match(*args, **kwargs)
117

    
118

    
119
def categorical_multiedge_match(attr, default):
120
    if nx.utils.is_string_like(attr):
121
        def match(datasets1, datasets2):
122
            values1 = set([data.get(attr, default) for data in datasets1.values()])
123
            values2 = set([data.get(attr, default) for data in datasets2.values()])
124
            return values1 == values2
125
    else:
126
        attrs = list(zip(attr, default))  # Python 3
127

    
128
        def match(datasets1, datasets2):
129
            values1 = set([])
130
            for data1 in datasets1.values():
131
                x = tuple(data1.get(attr, d) for attr, d in attrs)
132
                values1.add(x)
133
            values2 = set([])
134
            for data2 in datasets2.values():
135
                x = tuple(data2.get(attr, d) for attr, d in attrs)
136
                values2.add(x)
137
            return values1 == values2
138
    return match
139

    
140

    
141
# Docstrings for categorical functions.
142
categorical_node_match.__doc__ = categorical_doc
143
categorical_edge_match.__doc__ = categorical_doc.replace('node', 'edge')
144
tmpdoc = categorical_doc.replace('node', 'edge')
145
tmpdoc = tmpdoc.replace('categorical_edge_match', 'categorical_multiedge_match')
146
categorical_multiedge_match.__doc__ = tmpdoc
147

    
148

    
149
numerical_doc = """
150
Returns a comparison function for a numerical node attribute.
151

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

156
Parameters
157
----------
158
attr : string | list
159
    The numerical node attribute to compare, or a list of numerical
160
    node attributes to compare.
161
default : value | list
162
    The default value for the numerical node attribute, or a list of
163
    default values for the numerical node attributes.
164
rtol : float
165
    The relative error tolerance.
166
atol : float
167
    The absolute error tolerance.
168

169
Returns
170
-------
171
match : function
172
    The customized, numerical `node_match` function.
173

174
Examples
175
--------
176
>>> import networkx.algorithms.isomorphism as iso
177
>>> nm = iso.numerical_node_match('weight', 1.0)
178
>>> nm = iso.numerical_node_match(['weight', 'linewidth'], [.25, .5])
179

180
"""
181

    
182

    
183
def numerical_node_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08):
184
    if nx.utils.is_string_like(attr):
185
        def match(data1, data2):
186
            return close(data1.get(attr, default),
187
                         data2.get(attr, default),
188
                         rtol=rtol, atol=atol)
189
    else:
190
        attrs = list(zip(attr, default))  # Python 3
191

    
192
        def match(data1, data2):
193
            values1 = [data1.get(attr, d) for attr, d in attrs]
194
            values2 = [data2.get(attr, d) for attr, d in attrs]
195
            return allclose(values1, values2, rtol=rtol, atol=atol)
196
    return match
197

    
198

    
199
try:
200
    numerical_edge_match = copyfunc(numerical_node_match, 'numerical_edge_match')
201
except NotImplementedError:
202
    # IronPython lacks support for types.FunctionType.
203
    # https://github.com/networkx/networkx/issues/949
204
    # https://github.com/networkx/networkx/issues/1127
205
    def numerical_edge_match(*args, **kwargs):
206
        return numerical_node_match(*args, **kwargs)
207

    
208

    
209
def numerical_multiedge_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08):
210
    if nx.utils.is_string_like(attr):
211
        def match(datasets1, datasets2):
212
            values1 = sorted([data.get(attr, default) for data in datasets1.values()])
213
            values2 = sorted([data.get(attr, default) for data in datasets2.values()])
214
            return allclose(values1, values2, rtol=rtol, atol=atol)
215
    else:
216
        attrs = list(zip(attr, default))  # Python 3
217

    
218
        def match(datasets1, datasets2):
219
            values1 = []
220
            for data1 in datasets1.values():
221
                x = tuple(data1.get(attr, d) for attr, d in attrs)
222
                values1.append(x)
223
            values2 = []
224
            for data2 in datasets2.values():
225
                x = tuple(data2.get(attr, d) for attr, d in attrs)
226
                values2.append(x)
227
            values1.sort()
228
            values2.sort()
229
            for xi, yi in zip(values1, values2):
230
                if not allclose(xi, yi, rtol=rtol, atol=atol):
231
                    return False
232
            else:
233
                return True
234
    return match
235

    
236

    
237
# Docstrings for numerical functions.
238
numerical_node_match.__doc__ = numerical_doc
239
numerical_edge_match.__doc__ = numerical_doc.replace('node', 'edge')
240
tmpdoc = numerical_doc.replace('node', 'edge')
241
tmpdoc = tmpdoc.replace('numerical_edge_match', 'numerical_multiedge_match')
242
numerical_multiedge_match.__doc__ = tmpdoc
243

    
244

    
245
generic_doc = """
246
Returns a comparison function for a generic attribute.
247

248
The value(s) of the attr(s) are compared using the specified
249
operators. If all the attributes are equal, then the constructed
250
function returns True.
251

252
Parameters
253
----------
254
attr : string | list
255
    The node attribute to compare, or a list of node attributes
256
    to compare.
257
default : value | list
258
    The default value for the node attribute, or a list of
259
    default values for the node attributes.
260
op : callable | list
261
    The operator to use when comparing attribute values, or a list
262
    of operators to use when comparing values for each attribute.
263

264
Returns
265
-------
266
match : function
267
    The customized, generic `node_match` function.
268

269
Examples
270
--------
271
>>> from operator import eq
272
>>> from networkx.algorithms.isomorphism.matchhelpers import close
273
>>> from networkx.algorithms.isomorphism import generic_node_match
274
>>> nm = generic_node_match('weight', 1.0, close)
275
>>> nm = generic_node_match('color', 'red', eq)
276
>>> nm = generic_node_match(['weight', 'color'], [1.0, 'red'], [close, eq])
277

278
"""
279

    
280

    
281
def generic_node_match(attr, default, op):
282
    if nx.utils.is_string_like(attr):
283
        def match(data1, data2):
284
            return op(data1.get(attr, default), data2.get(attr, default))
285
    else:
286
        attrs = list(zip(attr, default, op))  # Python 3
287

    
288
        def match(data1, data2):
289
            for attr, d, operator in attrs:
290
                if not operator(data1.get(attr, d), data2.get(attr, d)):
291
                    return False
292
            else:
293
                return True
294
    return match
295

    
296

    
297
try:
298
    generic_edge_match = copyfunc(generic_node_match, 'generic_edge_match')
299
except NotImplementedError:
300
    # IronPython lacks support for types.FunctionType.
301
    # https://github.com/networkx/networkx/issues/949
302
    # https://github.com/networkx/networkx/issues/1127
303
    def generic_edge_match(*args, **kwargs):
304
        return generic_node_match(*args, **kwargs)
305

    
306

    
307
def generic_multiedge_match(attr, default, op):
308
    """Returns a comparison function for a generic attribute.
309

310
    The value(s) of the attr(s) are compared using the specified
311
    operators. If all the attributes are equal, then the constructed
312
    function returns True. Potentially, the constructed edge_match
313
    function can be slow since it must verify that no isomorphism
314
    exists between the multiedges before it returns False.
315

316
    Parameters
317
    ----------
318
    attr : string | list
319
        The edge attribute to compare, or a list of node attributes
320
        to compare.
321
    default : value | list
322
        The default value for the edge attribute, or a list of
323
        default values for the dgeattributes.
324
    op : callable | list
325
        The operator to use when comparing attribute values, or a list
326
        of operators to use when comparing values for each attribute.
327

328
    Returns
329
    -------
330
    match : function
331
        The customized, generic `edge_match` function.
332

333
    Examples
334
    --------
335
    >>> from operator import eq
336
    >>> from networkx.algorithms.isomorphism.matchhelpers import close
337
    >>> from networkx.algorithms.isomorphism import generic_node_match
338
    >>> nm = generic_node_match('weight', 1.0, close)
339
    >>> nm = generic_node_match('color', 'red', eq)
340
    >>> nm = generic_node_match(['weight', 'color'],
341
    ...                         [1.0, 'red'],
342
    ...                         [close, eq])
343
    ...
344

345
    """
346

    
347
    # This is slow, but generic.
348
    # We must test every possible isomorphism between the edges.
349
    if nx.utils.is_string_like(attr):
350
        attr = [attr]
351
        default = [default]
352
        op = [op]
353
    attrs = list(zip(attr, default))  # Python 3
354

    
355
    def match(datasets1, datasets2):
356
        values1 = []
357
        for data1 in datasets1.values():
358
            x = tuple(data1.get(attr, d) for attr, d in attrs)
359
            values1.append(x)
360
        values2 = []
361
        for data2 in datasets2.values():
362
            x = tuple(data2.get(attr, d) for attr, d in attrs)
363
            values2.append(x)
364
        for vals2 in permutations(values2):
365
            for xi, yi in zip(values1, vals2):
366
                if not all(map(lambda x, y, z: z(x, y), xi, yi, op)):
367
                    # This is not an isomorphism, go to next permutation.
368
                    break
369
            else:
370
                # Then we found an isomorphism.
371
                return True
372
        else:
373
            # Then there are no isomorphisms between the multiedges.
374
            return False
375
    return match
376

    
377

    
378
# Docstrings for numerical functions.
379
generic_node_match.__doc__ = generic_doc
380
generic_edge_match.__doc__ = generic_doc.replace('node', 'edge')