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

1""" 

2Graph isomorphism functions. 

3""" 

4import networkx as nx 

5from networkx.exception import NetworkXError 

6 

7__all__ = [ 

8 "could_be_isomorphic", 

9 "fast_could_be_isomorphic", 

10 "faster_could_be_isomorphic", 

11 "is_isomorphic", 

12] 

13 

14 

15@nx._dispatch(graphs={"G1": 0, "G2": 1}) 

16def could_be_isomorphic(G1, G2): 

17 """Returns False if graphs are definitely not isomorphic. 

18 True does NOT guarantee isomorphism. 

19 

20 Parameters 

21 ---------- 

22 G1, G2 : graphs 

23 The two graphs G1 and G2 must be the same type. 

24 

25 Notes 

26 ----- 

27 Checks for matching degree, triangle, and number of cliques sequences. 

28 The triangle sequence contains the number of triangles each node is part of. 

29 The clique sequence contains for each node the number of maximal cliques 

30 involving that node. 

31 

32 """ 

33 

34 # Check global properties 

35 if G1.order() != G2.order(): 

36 return False 

37 

38 # Check local properties 

39 d1 = G1.degree() 

40 t1 = nx.triangles(G1) 

41 clqs_1 = list(nx.find_cliques(G1)) 

42 c1 = {n: sum(1 for c in clqs_1 if n in c) for n in G1} # number of cliques 

43 props1 = [[d, t1[v], c1[v]] for v, d in d1] 

44 props1.sort() 

45 

46 d2 = G2.degree() 

47 t2 = nx.triangles(G2) 

48 clqs_2 = list(nx.find_cliques(G2)) 

49 c2 = {n: sum(1 for c in clqs_2 if n in c) for n in G2} # number of cliques 

50 props2 = [[d, t2[v], c2[v]] for v, d in d2] 

51 props2.sort() 

52 

53 if props1 != props2: 

54 return False 

55 

56 # OK... 

57 return True 

58 

59 

60graph_could_be_isomorphic = could_be_isomorphic 

61 

62 

63@nx._dispatch(graphs={"G1": 0, "G2": 1}) 

64def fast_could_be_isomorphic(G1, G2): 

65 """Returns False if graphs are definitely not isomorphic. 

66 

67 True does NOT guarantee isomorphism. 

68 

69 Parameters 

70 ---------- 

71 G1, G2 : graphs 

72 The two graphs G1 and G2 must be the same type. 

73 

74 Notes 

75 ----- 

76 Checks for matching degree and triangle sequences. The triangle 

77 sequence contains the number of triangles each node is part of. 

78 """ 

79 # Check global properties 

80 if G1.order() != G2.order(): 

81 return False 

82 

83 # Check local properties 

84 d1 = G1.degree() 

85 t1 = nx.triangles(G1) 

86 props1 = [[d, t1[v]] for v, d in d1] 

87 props1.sort() 

88 

89 d2 = G2.degree() 

90 t2 = nx.triangles(G2) 

91 props2 = [[d, t2[v]] for v, d in d2] 

92 props2.sort() 

93 

94 if props1 != props2: 

95 return False 

96 

97 # OK... 

98 return True 

99 

100 

101fast_graph_could_be_isomorphic = fast_could_be_isomorphic 

102 

103 

104@nx._dispatch(graphs={"G1": 0, "G2": 1}) 

105def faster_could_be_isomorphic(G1, G2): 

106 """Returns False if graphs are definitely not isomorphic. 

107 

108 True does NOT guarantee isomorphism. 

109 

110 Parameters 

111 ---------- 

112 G1, G2 : graphs 

113 The two graphs G1 and G2 must be the same type. 

114 

115 Notes 

116 ----- 

117 Checks for matching degree sequences. 

118 """ 

119 # Check global properties 

120 if G1.order() != G2.order(): 

121 return False 

122 

123 # Check local properties 

124 d1 = sorted(d for n, d in G1.degree()) 

125 d2 = sorted(d for n, d in G2.degree()) 

126 

127 if d1 != d2: 

128 return False 

129 

130 # OK... 

131 return True 

132 

133 

134faster_graph_could_be_isomorphic = faster_could_be_isomorphic 

135 

136 

137@nx._dispatch( 

138 graphs={"G1": 0, "G2": 1}, 

139 preserve_edge_attrs="edge_match", 

140 preserve_node_attrs="node_match", 

141) 

142def is_isomorphic(G1, G2, node_match=None, edge_match=None): 

143 """Returns True if the graphs G1 and G2 are isomorphic and False otherwise. 

144 

145 Parameters 

146 ---------- 

147 G1, G2: graphs 

148 The two graphs G1 and G2 must be the same type. 

149 

150 node_match : callable 

151 A function that returns True if node n1 in G1 and n2 in G2 should 

152 be considered equal during the isomorphism test. 

153 If node_match is not specified then node attributes are not considered. 

154 

155 The function will be called like 

156 

157 node_match(G1.nodes[n1], G2.nodes[n2]). 

158 

159 That is, the function will receive the node attribute dictionaries 

160 for n1 and n2 as inputs. 

161 

162 edge_match : callable 

163 A function that returns True if the edge attribute dictionary 

164 for the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should 

165 be considered equal during the isomorphism test. If edge_match is 

166 not specified then edge attributes are not considered. 

167 

168 The function will be called like 

169 

170 edge_match(G1[u1][v1], G2[u2][v2]). 

171 

172 That is, the function will receive the edge attribute dictionaries 

173 of the edges under consideration. 

174 

175 Notes 

176 ----- 

177 Uses the vf2 algorithm [1]_. 

178 

179 Examples 

180 -------- 

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

182 

183 For digraphs G1 and G2, using 'weight' edge attribute (default: 1) 

184 

185 >>> G1 = nx.DiGraph() 

186 >>> G2 = nx.DiGraph() 

187 >>> nx.add_path(G1, [1, 2, 3, 4], weight=1) 

188 >>> nx.add_path(G2, [10, 20, 30, 40], weight=2) 

189 >>> em = iso.numerical_edge_match("weight", 1) 

190 >>> nx.is_isomorphic(G1, G2) # no weights considered 

191 True 

192 >>> nx.is_isomorphic(G1, G2, edge_match=em) # match weights 

193 False 

194 

195 For multidigraphs G1 and G2, using 'fill' node attribute (default: '') 

196 

197 >>> G1 = nx.MultiDiGraph() 

198 >>> G2 = nx.MultiDiGraph() 

199 >>> G1.add_nodes_from([1, 2, 3], fill="red") 

200 >>> G2.add_nodes_from([10, 20, 30, 40], fill="red") 

201 >>> nx.add_path(G1, [1, 2, 3, 4], weight=3, linewidth=2.5) 

202 >>> nx.add_path(G2, [10, 20, 30, 40], weight=3) 

203 >>> nm = iso.categorical_node_match("fill", "red") 

204 >>> nx.is_isomorphic(G1, G2, node_match=nm) 

205 True 

206 

207 For multidigraphs G1 and G2, using 'weight' edge attribute (default: 7) 

208 

209 >>> G1.add_edge(1, 2, weight=7) 

210 1 

211 >>> G2.add_edge(10, 20) 

212 1 

213 >>> em = iso.numerical_multiedge_match("weight", 7, rtol=1e-6) 

214 >>> nx.is_isomorphic(G1, G2, edge_match=em) 

215 True 

216 

217 For multigraphs G1 and G2, using 'weight' and 'linewidth' edge attributes 

218 with default values 7 and 2.5. Also using 'fill' node attribute with 

219 default value 'red'. 

220 

221 >>> em = iso.numerical_multiedge_match(["weight", "linewidth"], [7, 2.5]) 

222 >>> nm = iso.categorical_node_match("fill", "red") 

223 >>> nx.is_isomorphic(G1, G2, edge_match=em, node_match=nm) 

224 True 

225 

226 See Also 

227 -------- 

228 numerical_node_match, numerical_edge_match, numerical_multiedge_match 

229 categorical_node_match, categorical_edge_match, categorical_multiedge_match 

230 

231 References 

232 ---------- 

233 .. [1] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, 

234 "An Improved Algorithm for Matching Large Graphs", 

235 3rd IAPR-TC15 Workshop on Graph-based Representations in 

236 Pattern Recognition, Cuen, pp. 149-159, 2001. 

237 https://www.researchgate.net/publication/200034365_An_Improved_Algorithm_for_Matching_Large_Graphs 

238 """ 

239 if G1.is_directed() and G2.is_directed(): 

240 GM = nx.algorithms.isomorphism.DiGraphMatcher 

241 elif (not G1.is_directed()) and (not G2.is_directed()): 

242 GM = nx.algorithms.isomorphism.GraphMatcher 

243 else: 

244 raise NetworkXError("Graphs G1 and G2 are not of the same type.") 

245 

246 gm = GM(G1, G2, node_match=node_match, edge_match=edge_match) 

247 

248 return gm.is_isomorphic()