1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
"""
Fast checking to see if graphs are not isomorphic.
This isn't a graph isomorphism checker.
"""
__author__ = """Pieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
# Copyright (C) 2004-2008 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
import networkx as nx
from networkx.exception import NetworkXException, NetworkXError
__all__ = ['could_be_isomorphic',
'fast_could_be_isomorphic',
'faster_could_be_isomorphic',
'is_isomorphic']
def could_be_isomorphic(G1,G2):
"""Returns False if graphs are definitely not isomorphic.
True does NOT guarantee isomorphism.
Parameters
----------
G1, G2 : NetworkX graph instances
The two graphs G1 and G2 must be the same type.
Notes
-----
Checks for matching degree, triangle, and number of cliques sequences.
"""
# Check global properties
if G1.order() != G2.order(): return False
# Check local properties
d1=G1.degree()
t1=nx.triangles(G1)
c1=nx.number_of_cliques(G1)
props1=[ [d1[v], t1[v], c1[v]] for v in d1 ]
props1.sort()
d2=G2.degree()
t2=nx.triangles(G2)
c2=nx.number_of_cliques(G2)
props2=[ [d2[v], t2[v], c2[v]] for v in d2 ]
props2.sort()
if props1 != props2:
# print props1
# print props2
return False
# OK...
return True
graph_could_be_isomorphic=could_be_isomorphic
def fast_could_be_isomorphic(G1,G2):
"""Returns False if graphs are definitely not isomorphic.
True does NOT guarantee isomorphism.
Parameters
----------
G1, G2 : NetworkX graph instances
The two graphs G1 and G2 must be the same type.
Notes
-----
Checks for matching degree and triangle sequences.
"""
# Check global properties
if G1.order() != G2.order(): return False
# Check local properties
d1=G1.degree()
t1=nx.triangles(G1)
props1=[ [d1[v], t1[v]] for v in d1 ]
props1.sort()
d2=G2.degree()
t2=nx.triangles(G2)
props2=[ [d2[v], t2[v]] for v in d2 ]
props2.sort()
if props1 != props2: return False
# OK...
return True
fast_graph_could_be_isomorphic=fast_could_be_isomorphic
def faster_could_be_isomorphic(G1,G2):
"""Returns False if graphs are definitely not isomorphic.
True does NOT guarantee isomorphism.
Parameters
----------
G1, G2 : NetworkX graph instances
The two graphs G1 and G2 must be the same type.
Notes
-----
Checks for matching degree sequences.
"""
# Check global properties
if G1.order() != G2.order(): return False
# Check local properties
d1=G1.degree().values()
d1.sort()
d2=G2.degree().values()
d2.sort()
if d1 != d2: return False
# OK...
return True
faster_graph_could_be_isomorphic=faster_could_be_isomorphic
def is_isomorphic(G1,G2,weighted=False,rtol=1e-6,atol=1e-9):
"""Returns True if the graphs G1 and G2 are isomorphic and False otherwise.
Parameters
----------
G1, G2: NetworkX graph instances
The two graphs G1 and G2 must be the same type.
weighted: bool, optional
Optionally check isomorphism for weighted graphs.
G1 and G2 must be valid weighted graphs.
rtol: float, optional
The relative error tolerance when checking weighted edges
atol: float, optional
The absolute error tolerance when checking weighted edges
Notes
-----
Uses the vf2 algorithm.
Works for Graph, DiGraph, MultiGraph, and MultiDiGraph
See Also
--------
isomorphvf2()
"""
gm=None
if weighted==True:
# assert(G1.weighted and G2.weighted)
if not G1.is_directed() and not G1.is_multigraph():
assert(not G2.is_directed() and not G2.is_multigraph())
gm = nx.WeightedGraphMatcher(G1,G2,rtol,atol)
elif not G1.is_directed() and G1.is_multigraph():
assert(not G2.is_directed() and G2.is_multigraph())
gm = nx.WeightedMultiGraphMatcher(G1,G2,rtol,atol)
elif G1.is_directed() and not G1.is_multigraph():
assert(G2.is_directed() and not G2.is_multigraph())
gm = nx.WeightedDiGraphMatcher(G1,G2,rtol,atol)
else:
assert(G2.is_directed() and G2.is_multigraph())
gm = nx.WeightedMultiDiGraphMatcher(G1,G2,rtol,atol)
else:
if G1.is_directed() and G2.is_directed():
gm= nx.DiGraphMatcher(G1,G2)
elif not (G1.is_directed() and G2.is_directed()):
gm = nx.GraphMatcher(G1,G2)
if gm==None:
# Graphs are of mixed type. We could just return False,
# but then there is the case of completely disconnected graphs...
# which could be isomorphic.
raise NetworkXError("Graphs G1 and G2 are not of the same type.")
return gm.is_isomorphic()
|
