1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
1 |
"""
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
2 |
Graph isomorphism functions.
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
3 |
"""
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
4 |
import networkx as nx |
5 |
from networkx.exception import NetworkXError |
|
6 |
__author__ = """\n""".join(['Aric Hagberg (hagberg@lanl.gov)', |
|
7 |
'Pieter Swart (swart@lanl.gov)', |
|
8 |
'Christopher Ellison cellison@cse.ucdavis.edu)']) |
|
9 |
# Copyright (C) 2004-2011 by
|
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
10 |
# Aric Hagberg <hagberg@lanl.gov>
|
11 |
# Dan Schult <dschult@colgate.edu>
|
|
12 |
# Pieter Swart <swart@lanl.gov>
|
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
13 |
# All rights reserved.
|
14 |
# BSD license.
|
|
15 |
__all__ = ['could_be_isomorphic', |
|
16 |
'fast_could_be_isomorphic', |
|
17 |
'faster_could_be_isomorphic', |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
18 |
'is_isomorphic'] |
19 |
||
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
20 |
def could_be_isomorphic(G1,G2): |
21 |
"""Returns False if graphs are definitely not isomorphic.
|
|
22 |
True does NOT guarantee isomorphism.
|
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
23 |
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
24 |
Parameters
|
25 |
----------
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
26 |
G1, G2 : graphs
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
27 |
The two graphs G1 and G2 must be the same type.
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
28 |
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
29 |
Notes
|
30 |
-----
|
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
31 |
Checks for matching degree, triangle, and number of cliques sequences.
|
32 |
"""
|
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
33 |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
34 |
# Check global properties
|
35 |
if G1.order() != G2.order(): return False |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
36 |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
37 |
# Check local properties
|
1.1.5
by Sandro Tosi
Import upstream version 1.1 |
38 |
d1=G1.degree() |
39 |
t1=nx.triangles(G1) |
|
40 |
c1=nx.number_of_cliques(G1) |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
41 |
props1=[ [d1[v], t1[v], c1[v]] for v in d1 ] |
42 |
props1.sort() |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
43 |
|
1.1.5
by Sandro Tosi
Import upstream version 1.1 |
44 |
d2=G2.degree() |
45 |
t2=nx.triangles(G2) |
|
46 |
c2=nx.number_of_cliques(G2) |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
47 |
props2=[ [d2[v], t2[v], c2[v]] for v in d2 ] |
48 |
props2.sort() |
|
49 |
||
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
50 |
if props1 != props2: |
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
51 |
return False |
52 |
||
53 |
# OK...
|
|
54 |
return True |
|
55 |
||
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
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.
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
60 |
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
61 |
True does NOT guarantee isomorphism.
|
62 |
||
63 |
Parameters
|
|
64 |
----------
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
65 |
G1, G2 : graphs
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
66 |
The two graphs G1 and G2 must be the same type.
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
67 |
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
68 |
Notes
|
69 |
-----
|
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
70 |
Checks for matching degree and triangle sequences.
|
71 |
"""
|
|
72 |
# Check global properties
|
|
73 |
if G1.order() != G2.order(): return False |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
74 |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
75 |
# Check local properties
|
1.1.5
by Sandro Tosi
Import upstream version 1.1 |
76 |
d1=G1.degree() |
77 |
t1=nx.triangles(G1) |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
78 |
props1=[ [d1[v], t1[v]] for v in d1 ] |
79 |
props1.sort() |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
80 |
|
1.1.5
by Sandro Tosi
Import upstream version 1.1 |
81 |
d2=G2.degree() |
82 |
t2=nx.triangles(G2) |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
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 |
||
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
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.
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
95 |
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
96 |
True does NOT guarantee isomorphism.
|
97 |
||
98 |
Parameters
|
|
99 |
----------
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
100 |
G1, G2 : graphs
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
101 |
The two graphs G1 and G2 must be the same type.
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
102 |
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
103 |
Notes
|
104 |
-----
|
|
105 |
Checks for matching degree sequences.
|
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
106 |
"""
|
107 |
# Check global properties
|
|
108 |
if G1.order() != G2.order(): return False |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
109 |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
110 |
# Check local properties
|
1.2.4
by Sandro Tosi
Import upstream version 1.3 |
111 |
d1=list(G1.degree().values()) |
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
112 |
d1.sort() |
1.2.4
by Sandro Tosi
Import upstream version 1.3 |
113 |
d2=list(G2.degree().values()) |
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
114 |
d2.sort() |
115 |
||
116 |
if d1 != d2: return False |
|
117 |
||
118 |
# OK...
|
|
119 |
return True |
|
120 |
||
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
121 |
faster_graph_could_be_isomorphic=faster_could_be_isomorphic |
122 |
||
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
123 |
def is_isomorphic(G1, G2, node_match=None, edge_match=None): |
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
124 |
"""Returns True if the graphs G1 and G2 are isomorphic and False otherwise.
|
125 |
||
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
126 |
Parameters
|
127 |
----------
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
128 |
G1, G2: graphs
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
129 |
The two graphs G1 and G2 must be the same type.
|
130 |
||
131 |
node_match : callable
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
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.
|
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
135 |
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
136 |
The function will be called like
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
137 |
|
138 |
node_match(G1.node[n1], G2.node[n2]).
|
|
139 |
||
140 |
That is, the function will receive the node attribute dictionaries
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
141 |
for n1 and n2 as inputs.
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
146 |
be considered equal during the isomorphism test. If edge_match is
|
147 |
not specified then edge attributes are not considered.
|
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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 |
||
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
156 |
Notes
|
157 |
-----
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
158 |
Uses the vf2 algorithm [1]_.
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
159 |
|
160 |
Examples
|
|
161 |
--------
|
|
162 |
>>> import networkx.algorithms.isomorphism as iso
|
|
163 |
||
164 |
For digraphs G1 and G2, using 'weight' edge attribute (default: 1)
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
165 |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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: '')
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
177 |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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)
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
189 |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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'.
|
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
199 |
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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
|
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
204 |
|
205 |
See Also
|
|
206 |
--------
|
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
207 |
numerical_node_match, numerical_edge_match, numerical_multiedge_match
|
208 |
categorical_node_match, categorical_edge_match, categorical_multiedge_match
|
|
1.2.3
by Cyril Brulebois
Import upstream version 1.0~rc1~svn1492 |
209 |
|
1.4.1
by Sandro Tosi
Import upstream version 1.7 |
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
|
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
217 |
"""
|
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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 |
|
1.2.2
by Cyril Brulebois
Import upstream version 0.99 |
222 |
else: |
1.2.7
by Sandro Tosi
Import upstream version 1.6 |
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() |