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