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