1 """ 2 Graph isomorphism functions. 3 """ 4 import networkx as nx 5 from networkx.exception import NetworkXError 6 __author__ = """\n""".join(['Aric Hagberg (hagberg (at] lanl.gov)', 7 'Pieter Swart (swart (at] lanl.gov)', 8 'Christopher Ellison cellison (at] cse.ucdavis.edu)']) 9 # Copyright (C) 2004-2011 by 10 # Aric Hagberg <hagberg (at] lanl.gov> 11 # Dan Schult <dschult (at] colgate.edu> 12 # Pieter Swart <swart (at] lanl.gov> 13 # All rights reserved. 14 # BSD license. 15 __all__ = ['could_be_isomorphic', 16 'fast_could_be_isomorphic', 17 'faster_could_be_isomorphic', 18 'is_isomorphic'] 19 20 def could_be_isomorphic(G1,G2): 21 """Returns False if graphs are definitely not isomorphic. 22 True does NOT guarantee isomorphism. 23 24 Parameters 25 ---------- 26 G1, G2 : graphs 27 The two graphs G1 and G2 must be the same type. 28 29 Notes 30 ----- 31 Checks for matching degree, triangle, and number of cliques sequences. 32 """ 33 34 # Check global properties 35 if G1.order() != G2.order(): return False 36 37 # Check local properties 38 d1=G1.degree() 39 t1=nx.triangles(G1) 40 c1=nx.number_of_cliques(G1) 41 props1=[ [d1[v], t1[v], c1[v]] for v in d1 ] 42 props1.sort() 43 44 d2=G2.degree() 45 t2=nx.triangles(G2) 46 c2=nx.number_of_cliques(G2) 47 props2=[ [d2[v], t2[v], c2[v]] for v in d2 ] 48 props2.sort() 49 50 if props1 != props2: 51 return False 52 53 # OK... 54 return True 55 56 graph_could_be_isomorphic=could_be_isomorphic 57 58 def fast_could_be_isomorphic(G1,G2): 59 """Returns False if graphs are definitely not isomorphic. 60 61 True does NOT guarantee isomorphism. 62 63 Parameters 64 ---------- 65 G1, G2 : graphs 66 The two graphs G1 and G2 must be the same type. 67 68 Notes 69 ----- 70 Checks for matching degree and triangle sequences. 71 """ 72 # Check global properties 73 if G1.order() != G2.order(): return False 74 75 # Check local properties 76 d1=G1.degree() 77 t1=nx.triangles(G1) 78 props1=[ [d1[v], t1[v]] for v in d1 ] 79 props1.sort() 80 81 d2=G2.degree() 82 t2=nx.triangles(G2) 83 props2=[ [d2[v], t2[v]] for v in d2 ] 84 props2.sort() 85 86 if props1 != props2: return False 87 88 # OK... 89 return True 90 91 fast_graph_could_be_isomorphic=fast_could_be_isomorphic 92 93 def faster_could_be_isomorphic(G1,G2): 94 """Returns False if graphs are definitely not isomorphic. 95 96 True does NOT guarantee isomorphism. 97 98 Parameters 99 ---------- 100 G1, G2 : graphs 101 The two graphs G1 and G2 must be the same type. 102 103 Notes 104 ----- 105 Checks for matching degree sequences. 106 """ 107 # Check global properties 108 if G1.order() != G2.order(): return False 109 110 # Check local properties 111 d1=list(G1.degree().values()) 112 d1.sort() 113 d2=list(G2.degree().values()) 114 d2.sort() 115 116 if d1 != d2: return False 117 118 # OK... 119 return True 120 121 faster_graph_could_be_isomorphic=faster_could_be_isomorphic 122 123 def is_isomorphic(G1, G2, node_match=None, edge_match=None): 124 """Returns True if the graphs G1 and G2 are isomorphic and False otherwise. 125 126 Parameters 127 ---------- 128 G1, G2: graphs 129 The two graphs G1 and G2 must be the same type. 130 131 node_match : callable 132 A function that returns True if node n1 in G1 and n2 in G2 should 133 be considered equal during the isomorphism test. 134 If node_match is not specified then node attributes are not considered. 135 136 The function will be called like 137 138 node_match(G1.node[n1], G2.node[n2]). 139 140 That is, the function will receive the node attribute dictionaries 141 for n1 and n2 as inputs. 142 143 edge_match : callable 144 A function that returns True if the edge attribute dictionary 145 for the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should 146 be considered equal during the isomorphism test. If edge_match is 147 not specified then edge attributes are not considered. 148 149 The function will be called like 150 151 edge_match(G1[u1][v1], G2[u2][v2]). 152 153 That is, the function will receive the edge attribute dictionaries 154 of the edges under consideration. 155 156 Notes 157 ----- 158 Uses the vf2 algorithm [1]_. 159 160 Examples 161 -------- 162 >>> import networkx.algorithms.isomorphism as iso 163 164 For digraphs G1 and G2, using 'weight' edge attribute (default: 1) 165 166 >>> G1 = nx.DiGraph() 167 >>> G2 = nx.DiGraph() 168 >>> G1.add_path([1,2,3,4],weight=1) 169 >>> G2.add_path([10,20,30,40],weight=2) 170 >>> em = iso.numerical_edge_match('weight', 1) 171 >>> nx.is_isomorphic(G1, G2) # no weights considered 172 True 173 >>> nx.is_isomorphic(G1, G2, edge_match=em) # match weights 174 False 175 176 For multidigraphs G1 and G2, using 'fill' node attribute (default: '') 177 178 >>> G1 = nx.MultiDiGraph() 179 >>> G2 = nx.MultiDiGraph() 180 >>> G1.add_nodes_from([1,2,3],fill='red') 181 >>> G2.add_nodes_from([10,20,30,40],fill='red') 182 >>> G1.add_path([1,2,3,4],weight=3, linewidth=2.5) 183 >>> G2.add_path([10,20,30,40],weight=3) 184 >>> nm = iso.categorical_node_match('fill', 'red') 185 >>> nx.is_isomorphic(G1, G2, node_match=nm) 186 True 187 188 For multidigraphs G1 and G2, using 'weight' edge attribute (default: 7) 189 190 >>> G1.add_edge(1,2, weight=7) 191 >>> G2.add_edge(10,20) 192 >>> em = iso.numerical_multiedge_match('weight', 7, rtol=1e-6) 193 >>> nx.is_isomorphic(G1, G2, edge_match=em) 194 True 195 196 For multigraphs G1 and G2, using 'weight' and 'linewidth' edge attributes 197 with default values 7 and 2.5. Also using 'fill' node attribute with 198 default value 'red'. 199 200 >>> em = iso.numerical_multiedge_match(['weight', 'linewidth'], [7, 2.5]) 201 >>> nm = iso.categorical_node_match('fill', 'red') 202 >>> nx.is_isomorphic(G1, G2, edge_match=em, node_match=nm) 203 True 204 205 See Also 206 -------- 207 numerical_node_match, numerical_edge_match, numerical_multiedge_match 208 categorical_node_match, categorical_edge_match, categorical_multiedge_match 209 210 References 211 ---------- 212 .. [1] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, 213 "An Improved Algorithm for Matching Large Graphs", 214 3rd IAPR-TC15 Workshop on Graph-based Representations in 215 Pattern Recognition, Cuen, pp. 149-159, 2001. 216 http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf 217 """ 218 if G1.is_directed() and G2.is_directed(): 219 GM = nx.algorithms.isomorphism.DiGraphMatcher 220 elif (not G1.is_directed()) and (not G2.is_directed()): 221 GM = nx.algorithms.isomorphism.GraphMatcher 222 else: 223 raise NetworkXError("Graphs G1 and G2 are not of the same type.") 224 225 gm = GM(G1, G2, node_match=node_match, edge_match=edge_match) 226 227 return gm.is_isomorphic() 228
