Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/isomorphism/matchhelpers.py: 26%

1"""Functions which help end users define customize node_match and 

2edge_match functions to use during isomorphism checks. 

3""" 

4import math 

5import types 

6from itertools import permutations 

7 

8__all__ = [ 

9 "categorical_node_match", 

10 "categorical_edge_match", 

11 "categorical_multiedge_match", 

12 "numerical_node_match", 

13 "numerical_edge_match", 

14 "numerical_multiedge_match", 

15 "generic_node_match", 

16 "generic_edge_match", 

17 "generic_multiedge_match", 

18] 

19 

20 

21def copyfunc(f, name=None): 

22 """Returns a deepcopy of a function.""" 

23 return types.FunctionType( 

24 f.__code__, f.__globals__, name or f.__name__, f.__defaults__, f.__closure__ 

25 ) 

26 

27 

28def allclose(x, y, rtol=1.0000000000000001e-05, atol=1e-08): 

29 """Returns True if x and y are sufficiently close, elementwise. 

30 

31 Parameters 

32 ---------- 

33 rtol : float 

34 The relative error tolerance. 

35 atol : float 

36 The absolute error tolerance. 

37 

38 """ 

39 # assume finite weights, see numpy.allclose() for reference 

40 return all(math.isclose(xi, yi, rel_tol=rtol, abs_tol=atol) for xi, yi in zip(x, y)) 

41 

42 

43categorical_doc = """ 

44Returns a comparison function for a categorical node attribute. 

45 

46The value(s) of the attr(s) must be hashable and comparable via the == 

47operator since they are placed into a set([]) object. If the sets from 

48G1 and G2 are the same, then the constructed function returns True. 

49 

50Parameters 

51---------- 

52attr : string | list 

53 The categorical node attribute to compare, or a list of categorical 

54 node attributes to compare. 

55default : value | list 

56 The default value for the categorical node attribute, or a list of 

57 default values for the categorical node attributes. 

58 

59Returns 

60------- 

61match : function 

62 The customized, categorical `node_match` function. 

63 

64Examples 

65-------- 

66>>> import networkx.algorithms.isomorphism as iso 

67>>> nm = iso.categorical_node_match("size", 1) 

68>>> nm = iso.categorical_node_match(["color", "size"], ["red", 2]) 

69 

70""" 

71 

72 

73def categorical_node_match(attr, default): 

74 if isinstance(attr, str): 

75 

76 def match(data1, data2): 

77 return data1.get(attr, default) == data2.get(attr, default) 

78 

79 else: 

80 attrs = list(zip(attr, default)) # Python 3 

81 

82 def match(data1, data2): 

83 return all(data1.get(attr, d) == data2.get(attr, d) for attr, d in attrs) 

84 

85 return match 

86 

87 

88categorical_edge_match = copyfunc(categorical_node_match, "categorical_edge_match") 

89 

90 

91def categorical_multiedge_match(attr, default): 

92 if isinstance(attr, str): 

93 

94 def match(datasets1, datasets2): 

95 values1 = {data.get(attr, default) for data in datasets1.values()} 

96 values2 = {data.get(attr, default) for data in datasets2.values()} 

97 return values1 == values2 

98 

99 else: 

100 attrs = list(zip(attr, default)) # Python 3 

101 

102 def match(datasets1, datasets2): 

103 values1 = set() 

104 for data1 in datasets1.values(): 

105 x = tuple(data1.get(attr, d) for attr, d in attrs) 

106 values1.add(x) 

107 values2 = set() 

108 for data2 in datasets2.values(): 

109 x = tuple(data2.get(attr, d) for attr, d in attrs) 

110 values2.add(x) 

111 return values1 == values2 

112 

113 return match 

114 

115 

116# Docstrings for categorical functions. 

117categorical_node_match.__doc__ = categorical_doc 

118categorical_edge_match.__doc__ = categorical_doc.replace("node", "edge") 

119tmpdoc = categorical_doc.replace("node", "edge") 

120tmpdoc = tmpdoc.replace("categorical_edge_match", "categorical_multiedge_match") 

121categorical_multiedge_match.__doc__ = tmpdoc 

122 

123 

124numerical_doc = """ 

125Returns a comparison function for a numerical node attribute. 

126 

127The value(s) of the attr(s) must be numerical and sortable. If the 

128sorted list of values from G1 and G2 are the same within some 

129tolerance, then the constructed function returns True. 

130 

131Parameters 

132---------- 

133attr : string | list 

134 The numerical node attribute to compare, or a list of numerical 

135 node attributes to compare. 

136default : value | list 

137 The default value for the numerical node attribute, or a list of 

138 default values for the numerical node attributes. 

139rtol : float 

140 The relative error tolerance. 

141atol : float 

142 The absolute error tolerance. 

143 

144Returns 

145------- 

146match : function 

147 The customized, numerical `node_match` function. 

148 

149Examples 

150-------- 

151>>> import networkx.algorithms.isomorphism as iso 

152>>> nm = iso.numerical_node_match("weight", 1.0) 

153>>> nm = iso.numerical_node_match(["weight", "linewidth"], [0.25, 0.5]) 

154 

155""" 

156 

157 

158def numerical_node_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08): 

159 if isinstance(attr, str): 

160 

161 def match(data1, data2): 

162 return math.isclose( 

163 data1.get(attr, default), 

164 data2.get(attr, default), 

165 rel_tol=rtol, 

166 abs_tol=atol, 

167 ) 

168 

169 else: 

170 attrs = list(zip(attr, default)) # Python 3 

171 

172 def match(data1, data2): 

173 values1 = [data1.get(attr, d) for attr, d in attrs] 

174 values2 = [data2.get(attr, d) for attr, d in attrs] 

175 return allclose(values1, values2, rtol=rtol, atol=atol) 

176 

177 return match 

178 

179 

180numerical_edge_match = copyfunc(numerical_node_match, "numerical_edge_match") 

181 

182 

183def numerical_multiedge_match(attr, default, rtol=1.0000000000000001e-05, atol=1e-08): 

184 if isinstance(attr, str): 

185 

186 def match(datasets1, datasets2): 

187 values1 = sorted(data.get(attr, default) for data in datasets1.values()) 

188 values2 = sorted(data.get(attr, default) for data in datasets2.values()) 

189 return allclose(values1, values2, rtol=rtol, atol=atol) 

190 

191 else: 

192 attrs = list(zip(attr, default)) # Python 3 

193 

194 def match(datasets1, datasets2): 

195 values1 = [] 

196 for data1 in datasets1.values(): 

197 x = tuple(data1.get(attr, d) for attr, d in attrs) 

198 values1.append(x) 

199 values2 = [] 

200 for data2 in datasets2.values(): 

201 x = tuple(data2.get(attr, d) for attr, d in attrs) 

202 values2.append(x) 

203 values1.sort() 

204 values2.sort() 

205 for xi, yi in zip(values1, values2): 

206 if not allclose(xi, yi, rtol=rtol, atol=atol): 

207 return False 

208 else: 

209 return True 

210 

211 return match 

212 

213 

214# Docstrings for numerical functions. 

215numerical_node_match.__doc__ = numerical_doc 

216numerical_edge_match.__doc__ = numerical_doc.replace("node", "edge") 

217tmpdoc = numerical_doc.replace("node", "edge") 

218tmpdoc = tmpdoc.replace("numerical_edge_match", "numerical_multiedge_match") 

219numerical_multiedge_match.__doc__ = tmpdoc 

220 

221 

222generic_doc = """ 

223Returns a comparison function for a generic attribute. 

224 

225The value(s) of the attr(s) are compared using the specified 

226operators. If all the attributes are equal, then the constructed 

227function returns True. 

228 

229Parameters 

230---------- 

231attr : string | list 

232 The node attribute to compare, or a list of node attributes 

233 to compare. 

234default : value | list 

235 The default value for the node attribute, or a list of 

236 default values for the node attributes. 

237op : callable | list 

238 The operator to use when comparing attribute values, or a list 

239 of operators to use when comparing values for each attribute. 

240 

241Returns 

242------- 

243match : function 

244 The customized, generic `node_match` function. 

245 

246Examples 

247-------- 

248>>> from operator import eq 

249>>> from math import isclose 

250>>> from networkx.algorithms.isomorphism import generic_node_match 

251>>> nm = generic_node_match("weight", 1.0, isclose) 

252>>> nm = generic_node_match("color", "red", eq) 

253>>> nm = generic_node_match(["weight", "color"], [1.0, "red"], [isclose, eq]) 

254 

255""" 

256 

257 

258def generic_node_match(attr, default, op): 

259 if isinstance(attr, str): 

260 

261 def match(data1, data2): 

262 return op(data1.get(attr, default), data2.get(attr, default)) 

263 

264 else: 

265 attrs = list(zip(attr, default, op)) # Python 3 

266 

267 def match(data1, data2): 

268 for attr, d, operator in attrs: 

269 if not operator(data1.get(attr, d), data2.get(attr, d)): 

270 return False 

271 else: 

272 return True 

273 

274 return match 

275 

276 

277generic_edge_match = copyfunc(generic_node_match, "generic_edge_match") 

278 

279 

280def generic_multiedge_match(attr, default, op): 

281 """Returns a comparison function for a generic attribute. 

282 

283 The value(s) of the attr(s) are compared using the specified 

284 operators. If all the attributes are equal, then the constructed 

285 function returns True. Potentially, the constructed edge_match 

286 function can be slow since it must verify that no isomorphism 

287 exists between the multiedges before it returns False. 

288 

289 Parameters 

290 ---------- 

291 attr : string | list 

292 The edge attribute to compare, or a list of node attributes 

293 to compare. 

294 default : value | list 

295 The default value for the edge attribute, or a list of 

296 default values for the edgeattributes. 

297 op : callable | list 

298 The operator to use when comparing attribute values, or a list 

299 of operators to use when comparing values for each attribute. 

300 

301 Returns 

302 ------- 

303 match : function 

304 The customized, generic `edge_match` function. 

305 

306 Examples 

307 -------- 

308 >>> from operator import eq 

309 >>> from math import isclose 

310 >>> from networkx.algorithms.isomorphism import generic_node_match 

311 >>> nm = generic_node_match("weight", 1.0, isclose) 

312 >>> nm = generic_node_match("color", "red", eq) 

313 >>> nm = generic_node_match(["weight", "color"], [1.0, "red"], [isclose, eq]) 

314 ... 

315 

316 """ 

317 

318 # This is slow, but generic. 

319 # We must test every possible isomorphism between the edges. 

320 if isinstance(attr, str): 

321 attr = [attr] 

322 default = [default] 

323 op = [op] 

324 attrs = list(zip(attr, default)) # Python 3 

325 

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 in zip(values1, vals2): 

337 if not all(map(lambda x, y, z: z(x, y), xi, yi, op)): 

338 # This is not an isomorphism, go to next permutation. 

339 break 

340 else: 

341 # Then we found an isomorphism. 

342 return True 

343 else: 

344 # Then there are no isomorphisms between the multiedges. 

345 return False 

346 

347 return match 

348 

349 

350# Docstrings for numerical functions. 

351generic_node_match.__doc__ = generic_doc 

352generic_edge_match.__doc__ = generic_doc.replace("node", "edge")