Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/isomorphism/matchhelpers.py: 27%

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

2edge_match functions to use during isomorphism checks. 

3""" 

4 

5import math 

6import types 

7from itertools import permutations 

8 

9__all__ = [ 

10 "categorical_node_match", 

11 "categorical_edge_match", 

12 "categorical_multiedge_match", 

13 "numerical_node_match", 

14 "numerical_edge_match", 

15 "numerical_multiedge_match", 

16 "generic_node_match", 

17 "generic_edge_match", 

18 "generic_multiedge_match", 

19] 

20 

21 

22def copyfunc(f, name=None): 

23 """Returns a deepcopy of a function.""" 

24 return types.FunctionType( 

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

26 ) 

27 

28 

29def 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 return all(math.isclose(xi, yi, rel_tol=rtol, abs_tol=atol) for xi, yi in zip(x, y)) 

42 

43 

44categorical_doc = """ 

45Returns a comparison function for a categorical node attribute. 

46 

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

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

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

50 

51Parameters 

52---------- 

53attr : string | list 

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

55 node attributes to compare. 

56default : value | list 

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

58 default values for the categorical node attributes. 

59 

60Returns 

61------- 

62match : function 

63 The customized, categorical `node_match` function. 

64 

65Examples 

66-------- 

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

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

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

70 

71""" 

72 

73 

74def categorical_node_match(attr, default): 

75 if isinstance(attr, str): 

76 

77 def match(data1, data2): 

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

79 

80 else: 

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

82 

83 def match(data1, data2): 

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

85 

86 return match 

87 

88 

89categorical_edge_match = copyfunc(categorical_node_match, "categorical_edge_match") 

90 

91 

92def categorical_multiedge_match(attr, default): 

93 if isinstance(attr, str): 

94 

95 def match(datasets1, datasets2): 

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

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

98 return values1 == values2 

99 

100 else: 

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

102 

103 def match(datasets1, datasets2): 

104 values1 = set() 

105 for data1 in datasets1.values(): 

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

107 values1.add(x) 

108 values2 = set() 

109 for data2 in datasets2.values(): 

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

111 values2.add(x) 

112 return values1 == values2 

113 

114 return match 

115 

116 

117# Docstrings for categorical functions. 

118categorical_node_match.__doc__ = categorical_doc 

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

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

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

122categorical_multiedge_match.__doc__ = tmpdoc 

123 

124 

125numerical_doc = """ 

126Returns a comparison function for a numerical node attribute. 

127 

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

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

130tolerance, then the constructed function returns True. 

131 

132Parameters 

133---------- 

134attr : string | list 

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

136 node attributes to compare. 

137default : value | list 

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

139 default values for the numerical node attributes. 

140rtol : float 

141 The relative error tolerance. 

142atol : float 

143 The absolute error tolerance. 

144 

145Returns 

146------- 

147match : function 

148 The customized, numerical `node_match` function. 

149 

150Examples 

151-------- 

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

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

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

155 

156""" 

157 

158 

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

160 if isinstance(attr, str): 

161 

162 def match(data1, data2): 

163 return math.isclose( 

164 data1.get(attr, default), 

165 data2.get(attr, default), 

166 rel_tol=rtol, 

167 abs_tol=atol, 

168 ) 

169 

170 else: 

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

172 

173 def match(data1, data2): 

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

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

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

177 

178 return match 

179 

180 

181numerical_edge_match = copyfunc(numerical_node_match, "numerical_edge_match") 

182 

183 

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

185 if isinstance(attr, str): 

186 

187 def match(datasets1, datasets2): 

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

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

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

191 

192 else: 

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

194 

195 def match(datasets1, datasets2): 

196 values1 = [] 

197 for data1 in datasets1.values(): 

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

199 values1.append(x) 

200 values2 = [] 

201 for data2 in datasets2.values(): 

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

203 values2.append(x) 

204 values1.sort() 

205 values2.sort() 

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

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

208 return False 

209 else: 

210 return True 

211 

212 return match 

213 

214 

215# Docstrings for numerical functions. 

216numerical_node_match.__doc__ = numerical_doc 

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

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

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

220numerical_multiedge_match.__doc__ = tmpdoc 

221 

222 

223generic_doc = """ 

224Returns a comparison function for a generic attribute. 

225 

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

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

228function returns True. 

229 

230Parameters 

231---------- 

232attr : string | list 

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

234 to compare. 

235default : value | list 

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

237 default values for the node attributes. 

238op : callable | list 

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

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

241 

242Returns 

243------- 

244match : function 

245 The customized, generic `node_match` function. 

246 

247Examples 

248-------- 

249>>> from operator import eq 

250>>> from math import isclose 

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

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

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

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

255 

256""" 

257 

258 

259def generic_node_match(attr, default, op): 

260 if isinstance(attr, str): 

261 

262 def match(data1, data2): 

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

264 

265 else: 

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

267 

268 def match(data1, data2): 

269 for attr, d, operator in attrs: 

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

271 return False 

272 else: 

273 return True 

274 

275 return match 

276 

277 

278generic_edge_match = copyfunc(generic_node_match, "generic_edge_match") 

279 

280 

281def generic_multiedge_match(attr, default, op): 

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

283 

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

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

286 function returns True. Potentially, the constructed edge_match 

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

288 exists between the multiedges before it returns False. 

289 

290 Parameters 

291 ---------- 

292 attr : string | list 

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

294 to compare. 

295 default : value | list 

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

297 default values for the edgeattributes. 

298 op : callable | list 

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

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

301 

302 Returns 

303 ------- 

304 match : function 

305 The customized, generic `edge_match` function. 

306 

307 Examples 

308 -------- 

309 >>> from operator import eq 

310 >>> from math import isclose 

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

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

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

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

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")