Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/isomorphvf2.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 ************* | |
3 VF2 Algorithm | |
4 ************* | |
5 | |
6 An implementation of VF2 algorithm for graph ismorphism testing. | |
7 | |
8 The simplest interface to use this module is to call networkx.is_isomorphic(). | |
9 | |
10 Introduction | |
11 ------------ | |
12 | |
13 The GraphMatcher and DiGraphMatcher are responsible for matching | |
14 graphs or directed graphs in a predetermined manner. This | |
15 usually means a check for an isomorphism, though other checks | |
16 are also possible. For example, a subgraph of one graph | |
17 can be checked for isomorphism to a second graph. | |
18 | |
19 Matching is done via syntactic feasibility. It is also possible | |
20 to check for semantic feasibility. Feasibility, then, is defined | |
21 as the logical AND of the two functions. | |
22 | |
23 To include a semantic check, the (Di)GraphMatcher class should be | |
24 subclassed, and the semantic_feasibility() function should be | |
25 redefined. By default, the semantic feasibility function always | |
26 returns True. The effect of this is that semantics are not | |
27 considered in the matching of G1 and G2. | |
28 | |
29 Examples | |
30 -------- | |
31 | |
32 Suppose G1 and G2 are isomorphic graphs. Verification is as follows: | |
33 | |
34 >>> from networkx.algorithms import isomorphism | |
35 >>> G1 = nx.path_graph(4) | |
36 >>> G2 = nx.path_graph(4) | |
37 >>> GM = isomorphism.GraphMatcher(G1, G2) | |
38 >>> GM.is_isomorphic() | |
39 True | |
40 | |
41 GM.mapping stores the isomorphism mapping from G1 to G2. | |
42 | |
43 >>> GM.mapping | |
44 {0: 0, 1: 1, 2: 2, 3: 3} | |
45 | |
46 | |
47 Suppose G1 and G2 are isomorphic directed graphs | |
48 graphs. Verification is as follows: | |
49 | |
50 >>> G1 = nx.path_graph(4, create_using=nx.DiGraph()) | |
51 >>> G2 = nx.path_graph(4, create_using=nx.DiGraph()) | |
52 >>> DiGM = isomorphism.DiGraphMatcher(G1, G2) | |
53 >>> DiGM.is_isomorphic() | |
54 True | |
55 | |
56 DiGM.mapping stores the isomorphism mapping from G1 to G2. | |
57 | |
58 >>> DiGM.mapping | |
59 {0: 0, 1: 1, 2: 2, 3: 3} | |
60 | |
61 | |
62 | |
63 Subgraph Isomorphism | |
64 -------------------- | |
65 Graph theory literature can be ambiguous about the meaning of the | |
66 above statement, and we seek to clarify it now. | |
67 | |
68 In the VF2 literature, a mapping M is said to be a graph-subgraph | |
69 isomorphism iff M is an isomorphism between G2 and a subgraph of G1. | |
70 Thus, to say that G1 and G2 are graph-subgraph isomorphic is to say | |
71 that a subgraph of G1 is isomorphic to G2. | |
72 | |
73 Other literature uses the phrase 'subgraph isomorphic' as in 'G1 does | |
74 not have a subgraph isomorphic to G2'. Another use is as an in adverb | |
75 for isomorphic. Thus, to say that G1 and G2 are subgraph isomorphic | |
76 is to say that a subgraph of G1 is isomorphic to G2. | |
77 | |
78 Finally, the term 'subgraph' can have multiple meanings. In this | |
79 context, 'subgraph' always means a 'node-induced subgraph'. Edge-induced | |
80 subgraph isomorphisms are not directly supported, but one should be | |
81 able to perform the check by making use of nx.line_graph(). For | |
82 subgraphs which are not induced, the term 'monomorphism' is preferred | |
83 over 'isomorphism'. | |
84 | |
85 Let G=(N,E) be a graph with a set of nodes N and set of edges E. | |
86 | |
87 If G'=(N',E') is a subgraph, then: | |
88 N' is a subset of N | |
89 E' is a subset of E | |
90 | |
91 If G'=(N',E') is a node-induced subgraph, then: | |
92 N' is a subset of N | |
93 E' is the subset of edges in E relating nodes in N' | |
94 | |
95 If G'=(N',E') is an edge-induced subgraph, then: | |
96 N' is the subset of nodes in N related by edges in E' | |
97 E' is a subset of E | |
98 | |
99 If G'=(N',E') is a monomorphism, then: | |
100 N' is a subset of N | |
101 E' is a subset of the set of edges in E relating nodes in N' | |
102 | |
103 Note that if G' is a node-induced subgraph of G, then it is always a | |
104 subgraph monomorphism of G, but the opposite is not always true, as a | |
105 monomorphism can have fewer edges. | |
106 | |
107 References | |
108 ---------- | |
109 [1] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento, | |
110 "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs", | |
111 IEEE Transactions on Pattern Analysis and Machine Intelligence, | |
112 vol. 26, no. 10, pp. 1367-1372, Oct., 2004. | |
113 http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf | |
114 | |
115 [2] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, "An Improved | |
116 Algorithm for Matching Large Graphs", 3rd IAPR-TC15 Workshop | |
117 on Graph-based Representations in Pattern Recognition, Cuen, | |
118 pp. 149-159, 2001. | |
119 http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf | |
120 | |
121 See Also | |
122 -------- | |
123 syntactic_feasibility(), semantic_feasibility() | |
124 | |
125 Notes | |
126 ----- | |
127 | |
128 The implementation handles both directed and undirected graphs as well | |
129 as multigraphs. | |
130 | |
131 In general, the subgraph isomorphism problem is NP-complete whereas the | |
132 graph isomorphism problem is most likely not NP-complete (although no | |
133 polynomial-time algorithm is known to exist). | |
134 | |
135 """ | |
136 | |
137 # This work was originally coded by Christopher Ellison | |
138 # as part of the Computational Mechanics Python (CMPy) project. | |
139 # James P. Crutchfield, principal investigator. | |
140 # Complexity Sciences Center and Physics Department, UC Davis. | |
141 | |
142 import sys | |
143 | |
144 __all__ = ["GraphMatcher", "DiGraphMatcher"] | |
145 | |
146 | |
147 class GraphMatcher: | |
148 """Implementation of VF2 algorithm for matching undirected graphs. | |
149 | |
150 Suitable for Graph and MultiGraph instances. | |
151 """ | |
152 | |
153 def __init__(self, G1, G2): | |
154 """Initialize GraphMatcher. | |
155 | |
156 Parameters | |
157 ---------- | |
158 G1,G2: NetworkX Graph or MultiGraph instances. | |
159 The two graphs to check for isomorphism or monomorphism. | |
160 | |
161 Examples | |
162 -------- | |
163 To create a GraphMatcher which checks for syntactic feasibility: | |
164 | |
165 >>> from networkx.algorithms import isomorphism | |
166 >>> G1 = nx.path_graph(4) | |
167 >>> G2 = nx.path_graph(4) | |
168 >>> GM = isomorphism.GraphMatcher(G1, G2) | |
169 """ | |
170 self.G1 = G1 | |
171 self.G2 = G2 | |
172 self.G1_nodes = set(G1.nodes()) | |
173 self.G2_nodes = set(G2.nodes()) | |
174 self.G2_node_order = {n: i for i, n in enumerate(G2)} | |
175 | |
176 # Set recursion limit. | |
177 self.old_recursion_limit = sys.getrecursionlimit() | |
178 expected_max_recursion_level = len(self.G2) | |
179 if self.old_recursion_limit < 1.5 * expected_max_recursion_level: | |
180 # Give some breathing room. | |
181 sys.setrecursionlimit(int(1.5 * expected_max_recursion_level)) | |
182 | |
183 # Declare that we will be searching for a graph-graph isomorphism. | |
184 self.test = "graph" | |
185 | |
186 # Initialize state | |
187 self.initialize() | |
188 | |
189 def reset_recursion_limit(self): | |
190 """Restores the recursion limit.""" | |
191 # TODO: | |
192 # Currently, we use recursion and set the recursion level higher. | |
193 # It would be nice to restore the level, but because the | |
194 # (Di)GraphMatcher classes make use of cyclic references, garbage | |
195 # collection will never happen when we define __del__() to | |
196 # restore the recursion level. The result is a memory leak. | |
197 # So for now, we do not automatically restore the recursion level, | |
198 # and instead provide a method to do this manually. Eventually, | |
199 # we should turn this into a non-recursive implementation. | |
200 sys.setrecursionlimit(self.old_recursion_limit) | |
201 | |
202 def candidate_pairs_iter(self): | |
203 """Iterator over candidate pairs of nodes in G1 and G2.""" | |
204 | |
205 # All computations are done using the current state! | |
206 | |
207 G1_nodes = self.G1_nodes | |
208 G2_nodes = self.G2_nodes | |
209 min_key = self.G2_node_order.__getitem__ | |
210 | |
211 # First we compute the inout-terminal sets. | |
212 T1_inout = [node for node in self.inout_1 if node not in self.core_1] | |
213 T2_inout = [node for node in self.inout_2 if node not in self.core_2] | |
214 | |
215 # If T1_inout and T2_inout are both nonempty. | |
216 # P(s) = T1_inout x {min T2_inout} | |
217 if T1_inout and T2_inout: | |
218 node_2 = min(T2_inout, key=min_key) | |
219 for node_1 in T1_inout: | |
220 yield node_1, node_2 | |
221 | |
222 else: | |
223 # If T1_inout and T2_inout were both empty.... | |
224 # P(s) = (N_1 - M_1) x {min (N_2 - M_2)} | |
225 # if not (T1_inout or T2_inout): # as suggested by [2], incorrect | |
226 if 1: # as inferred from [1], correct | |
227 # First we determine the candidate node for G2 | |
228 other_node = min(G2_nodes - set(self.core_2), key=min_key) | |
229 for node in self.G1: | |
230 if node not in self.core_1: | |
231 yield node, other_node | |
232 | |
233 # For all other cases, we don't have any candidate pairs. | |
234 | |
235 def initialize(self): | |
236 """Reinitializes the state of the algorithm. | |
237 | |
238 This method should be redefined if using something other than GMState. | |
239 If only subclassing GraphMatcher, a redefinition is not necessary. | |
240 | |
241 """ | |
242 | |
243 # core_1[n] contains the index of the node paired with n, which is m, | |
244 # provided n is in the mapping. | |
245 # core_2[m] contains the index of the node paired with m, which is n, | |
246 # provided m is in the mapping. | |
247 self.core_1 = {} | |
248 self.core_2 = {} | |
249 | |
250 # See the paper for definitions of M_x and T_x^{y} | |
251 | |
252 # inout_1[n] is non-zero if n is in M_1 or in T_1^{inout} | |
253 # inout_2[m] is non-zero if m is in M_2 or in T_2^{inout} | |
254 # | |
255 # The value stored is the depth of the SSR tree when the node became | |
256 # part of the corresponding set. | |
257 self.inout_1 = {} | |
258 self.inout_2 = {} | |
259 # Practically, these sets simply store the nodes in the subgraph. | |
260 | |
261 self.state = GMState(self) | |
262 | |
263 # Provide a convenient way to access the isomorphism mapping. | |
264 self.mapping = self.core_1.copy() | |
265 | |
266 def is_isomorphic(self): | |
267 """Returns True if G1 and G2 are isomorphic graphs.""" | |
268 | |
269 # Let's do two very quick checks! | |
270 # QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)? | |
271 # For now, I just copy the code. | |
272 | |
273 # Check global properties | |
274 if self.G1.order() != self.G2.order(): | |
275 return False | |
276 | |
277 # Check local properties | |
278 d1 = sorted(d for n, d in self.G1.degree()) | |
279 d2 = sorted(d for n, d in self.G2.degree()) | |
280 if d1 != d2: | |
281 return False | |
282 | |
283 try: | |
284 x = next(self.isomorphisms_iter()) | |
285 return True | |
286 except StopIteration: | |
287 return False | |
288 | |
289 def isomorphisms_iter(self): | |
290 """Generator over isomorphisms between G1 and G2.""" | |
291 # Declare that we are looking for a graph-graph isomorphism. | |
292 self.test = "graph" | |
293 self.initialize() | |
294 yield from self.match() | |
295 | |
296 def match(self): | |
297 """Extends the isomorphism mapping. | |
298 | |
299 This function is called recursively to determine if a complete | |
300 isomorphism can be found between G1 and G2. It cleans up the class | |
301 variables after each recursive call. If an isomorphism is found, | |
302 we yield the mapping. | |
303 | |
304 """ | |
305 if len(self.core_1) == len(self.G2): | |
306 # Save the final mapping, otherwise garbage collection deletes it. | |
307 self.mapping = self.core_1.copy() | |
308 # The mapping is complete. | |
309 yield self.mapping | |
310 else: | |
311 for G1_node, G2_node in self.candidate_pairs_iter(): | |
312 if self.syntactic_feasibility(G1_node, G2_node): | |
313 if self.semantic_feasibility(G1_node, G2_node): | |
314 # Recursive call, adding the feasible state. | |
315 newstate = self.state.__class__(self, G1_node, G2_node) | |
316 yield from self.match() | |
317 | |
318 # restore data structures | |
319 newstate.restore() | |
320 | |
321 def semantic_feasibility(self, G1_node, G2_node): | |
322 """Returns True if adding (G1_node, G2_node) is symantically feasible. | |
323 | |
324 The semantic feasibility function should return True if it is | |
325 acceptable to add the candidate pair (G1_node, G2_node) to the current | |
326 partial isomorphism mapping. The logic should focus on semantic | |
327 information contained in the edge data or a formalized node class. | |
328 | |
329 By acceptable, we mean that the subsequent mapping can still become a | |
330 complete isomorphism mapping. Thus, if adding the candidate pair | |
331 definitely makes it so that the subsequent mapping cannot become a | |
332 complete isomorphism mapping, then this function must return False. | |
333 | |
334 The default semantic feasibility function always returns True. The | |
335 effect is that semantics are not considered in the matching of G1 | |
336 and G2. | |
337 | |
338 The semantic checks might differ based on the what type of test is | |
339 being performed. A keyword description of the test is stored in | |
340 self.test. Here is a quick description of the currently implemented | |
341 tests:: | |
342 | |
343 test='graph' | |
344 Indicates that the graph matcher is looking for a graph-graph | |
345 isomorphism. | |
346 | |
347 test='subgraph' | |
348 Indicates that the graph matcher is looking for a subgraph-graph | |
349 isomorphism such that a subgraph of G1 is isomorphic to G2. | |
350 | |
351 test='mono' | |
352 Indicates that the graph matcher is looking for a subgraph-graph | |
353 monomorphism such that a subgraph of G1 is monomorphic to G2. | |
354 | |
355 Any subclass which redefines semantic_feasibility() must maintain | |
356 the above form to keep the match() method functional. Implementations | |
357 should consider multigraphs. | |
358 """ | |
359 return True | |
360 | |
361 def subgraph_is_isomorphic(self): | |
362 """Returns True if a subgraph of G1 is isomorphic to G2.""" | |
363 try: | |
364 x = next(self.subgraph_isomorphisms_iter()) | |
365 return True | |
366 except StopIteration: | |
367 return False | |
368 | |
369 def subgraph_is_monomorphic(self): | |
370 """Returns True if a subgraph of G1 is monomorphic to G2.""" | |
371 try: | |
372 x = next(self.subgraph_monomorphisms_iter()) | |
373 return True | |
374 except StopIteration: | |
375 return False | |
376 | |
377 # subgraph_is_isomorphic.__doc__ += "\n" + subgraph.replace('\n','\n'+indent) | |
378 | |
379 def subgraph_isomorphisms_iter(self): | |
380 """Generator over isomorphisms between a subgraph of G1 and G2.""" | |
381 # Declare that we are looking for graph-subgraph isomorphism. | |
382 self.test = "subgraph" | |
383 self.initialize() | |
384 yield from self.match() | |
385 | |
386 def subgraph_monomorphisms_iter(self): | |
387 """Generator over monomorphisms between a subgraph of G1 and G2.""" | |
388 # Declare that we are looking for graph-subgraph monomorphism. | |
389 self.test = "mono" | |
390 self.initialize() | |
391 yield from self.match() | |
392 | |
393 # subgraph_isomorphisms_iter.__doc__ += "\n" + subgraph.replace('\n','\n'+indent) | |
394 | |
395 def syntactic_feasibility(self, G1_node, G2_node): | |
396 """Returns True if adding (G1_node, G2_node) is syntactically feasible. | |
397 | |
398 This function returns True if it is adding the candidate pair | |
399 to the current partial isomorphism/monomorphism mapping is allowable. | |
400 The addition is allowable if the inclusion of the candidate pair does | |
401 not make it impossible for an isomorphism/monomorphism to be found. | |
402 """ | |
403 | |
404 # The VF2 algorithm was designed to work with graphs having, at most, | |
405 # one edge connecting any two nodes. This is not the case when | |
406 # dealing with an MultiGraphs. | |
407 # | |
408 # Basically, when we test the look-ahead rules R_neighbor, we will | |
409 # make sure that the number of edges are checked. We also add | |
410 # a R_self check to verify that the number of selfloops is acceptable. | |
411 # | |
412 # Users might be comparing Graph instances with MultiGraph instances. | |
413 # So the generic GraphMatcher class must work with MultiGraphs. | |
414 # Care must be taken since the value in the innermost dictionary is a | |
415 # singlet for Graph instances. For MultiGraphs, the value in the | |
416 # innermost dictionary is a list. | |
417 | |
418 ### | |
419 # Test at each step to get a return value as soon as possible. | |
420 ### | |
421 | |
422 # Look ahead 0 | |
423 | |
424 # R_self | |
425 | |
426 # The number of selfloops for G1_node must equal the number of | |
427 # self-loops for G2_node. Without this check, we would fail on | |
428 # R_neighbor at the next recursion level. But it is good to prune the | |
429 # search tree now. | |
430 | |
431 if self.test == "mono": | |
432 if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges( | |
433 G2_node, G2_node | |
434 ): | |
435 return False | |
436 else: | |
437 if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges( | |
438 G2_node, G2_node | |
439 ): | |
440 return False | |
441 | |
442 # R_neighbor | |
443 | |
444 # For each neighbor n' of n in the partial mapping, the corresponding | |
445 # node m' is a neighbor of m, and vice versa. Also, the number of | |
446 # edges must be equal. | |
447 if self.test != "mono": | |
448 for neighbor in self.G1[G1_node]: | |
449 if neighbor in self.core_1: | |
450 if not (self.core_1[neighbor] in self.G2[G2_node]): | |
451 return False | |
452 elif self.G1.number_of_edges( | |
453 neighbor, G1_node | |
454 ) != self.G2.number_of_edges(self.core_1[neighbor], G2_node): | |
455 return False | |
456 | |
457 for neighbor in self.G2[G2_node]: | |
458 if neighbor in self.core_2: | |
459 if not (self.core_2[neighbor] in self.G1[G1_node]): | |
460 return False | |
461 elif self.test == "mono": | |
462 if self.G1.number_of_edges( | |
463 self.core_2[neighbor], G1_node | |
464 ) < self.G2.number_of_edges(neighbor, G2_node): | |
465 return False | |
466 else: | |
467 if self.G1.number_of_edges( | |
468 self.core_2[neighbor], G1_node | |
469 ) != self.G2.number_of_edges(neighbor, G2_node): | |
470 return False | |
471 | |
472 if self.test != "mono": | |
473 # Look ahead 1 | |
474 | |
475 # R_terminout | |
476 # The number of neighbors of n in T_1^{inout} is equal to the | |
477 # number of neighbors of m that are in T_2^{inout}, and vice versa. | |
478 num1 = 0 | |
479 for neighbor in self.G1[G1_node]: | |
480 if (neighbor in self.inout_1) and (neighbor not in self.core_1): | |
481 num1 += 1 | |
482 num2 = 0 | |
483 for neighbor in self.G2[G2_node]: | |
484 if (neighbor in self.inout_2) and (neighbor not in self.core_2): | |
485 num2 += 1 | |
486 if self.test == "graph": | |
487 if not (num1 == num2): | |
488 return False | |
489 else: # self.test == 'subgraph' | |
490 if not (num1 >= num2): | |
491 return False | |
492 | |
493 # Look ahead 2 | |
494 | |
495 # R_new | |
496 | |
497 # The number of neighbors of n that are neither in the core_1 nor | |
498 # T_1^{inout} is equal to the number of neighbors of m | |
499 # that are neither in core_2 nor T_2^{inout}. | |
500 num1 = 0 | |
501 for neighbor in self.G1[G1_node]: | |
502 if neighbor not in self.inout_1: | |
503 num1 += 1 | |
504 num2 = 0 | |
505 for neighbor in self.G2[G2_node]: | |
506 if neighbor not in self.inout_2: | |
507 num2 += 1 | |
508 if self.test == "graph": | |
509 if not (num1 == num2): | |
510 return False | |
511 else: # self.test == 'subgraph' | |
512 if not (num1 >= num2): | |
513 return False | |
514 | |
515 # Otherwise, this node pair is syntactically feasible! | |
516 return True | |
517 | |
518 | |
519 class DiGraphMatcher(GraphMatcher): | |
520 """Implementation of VF2 algorithm for matching directed graphs. | |
521 | |
522 Suitable for DiGraph and MultiDiGraph instances. | |
523 """ | |
524 | |
525 def __init__(self, G1, G2): | |
526 """Initialize DiGraphMatcher. | |
527 | |
528 G1 and G2 should be nx.Graph or nx.MultiGraph instances. | |
529 | |
530 Examples | |
531 -------- | |
532 To create a GraphMatcher which checks for syntactic feasibility: | |
533 | |
534 >>> from networkx.algorithms import isomorphism | |
535 >>> G1 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph())) | |
536 >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph())) | |
537 >>> DiGM = isomorphism.DiGraphMatcher(G1, G2) | |
538 """ | |
539 super().__init__(G1, G2) | |
540 | |
541 def candidate_pairs_iter(self): | |
542 """Iterator over candidate pairs of nodes in G1 and G2.""" | |
543 | |
544 # All computations are done using the current state! | |
545 | |
546 G1_nodes = self.G1_nodes | |
547 G2_nodes = self.G2_nodes | |
548 min_key = self.G2_node_order.__getitem__ | |
549 | |
550 # First we compute the out-terminal sets. | |
551 T1_out = [node for node in self.out_1 if node not in self.core_1] | |
552 T2_out = [node for node in self.out_2 if node not in self.core_2] | |
553 | |
554 # If T1_out and T2_out are both nonempty. | |
555 # P(s) = T1_out x {min T2_out} | |
556 if T1_out and T2_out: | |
557 node_2 = min(T2_out, key=min_key) | |
558 for node_1 in T1_out: | |
559 yield node_1, node_2 | |
560 | |
561 # If T1_out and T2_out were both empty.... | |
562 # We compute the in-terminal sets. | |
563 | |
564 # elif not (T1_out or T2_out): # as suggested by [2], incorrect | |
565 else: # as suggested by [1], correct | |
566 T1_in = [node for node in self.in_1 if node not in self.core_1] | |
567 T2_in = [node for node in self.in_2 if node not in self.core_2] | |
568 | |
569 # If T1_in and T2_in are both nonempty. | |
570 # P(s) = T1_out x {min T2_out} | |
571 if T1_in and T2_in: | |
572 node_2 = min(T2_in, key=min_key) | |
573 for node_1 in T1_in: | |
574 yield node_1, node_2 | |
575 | |
576 # If all terminal sets are empty... | |
577 # P(s) = (N_1 - M_1) x {min (N_2 - M_2)} | |
578 | |
579 # elif not (T1_in or T2_in): # as suggested by [2], incorrect | |
580 else: # as inferred from [1], correct | |
581 node_2 = min(G2_nodes - set(self.core_2), key=min_key) | |
582 for node_1 in G1_nodes: | |
583 if node_1 not in self.core_1: | |
584 yield node_1, node_2 | |
585 | |
586 # For all other cases, we don't have any candidate pairs. | |
587 | |
588 def initialize(self): | |
589 """Reinitializes the state of the algorithm. | |
590 | |
591 This method should be redefined if using something other than DiGMState. | |
592 If only subclassing GraphMatcher, a redefinition is not necessary. | |
593 """ | |
594 | |
595 # core_1[n] contains the index of the node paired with n, which is m, | |
596 # provided n is in the mapping. | |
597 # core_2[m] contains the index of the node paired with m, which is n, | |
598 # provided m is in the mapping. | |
599 self.core_1 = {} | |
600 self.core_2 = {} | |
601 | |
602 # See the paper for definitions of M_x and T_x^{y} | |
603 | |
604 # in_1[n] is non-zero if n is in M_1 or in T_1^{in} | |
605 # out_1[n] is non-zero if n is in M_1 or in T_1^{out} | |
606 # | |
607 # in_2[m] is non-zero if m is in M_2 or in T_2^{in} | |
608 # out_2[m] is non-zero if m is in M_2 or in T_2^{out} | |
609 # | |
610 # The value stored is the depth of the search tree when the node became | |
611 # part of the corresponding set. | |
612 self.in_1 = {} | |
613 self.in_2 = {} | |
614 self.out_1 = {} | |
615 self.out_2 = {} | |
616 | |
617 self.state = DiGMState(self) | |
618 | |
619 # Provide a convenient way to access the isomorphism mapping. | |
620 self.mapping = self.core_1.copy() | |
621 | |
622 def syntactic_feasibility(self, G1_node, G2_node): | |
623 """Returns True if adding (G1_node, G2_node) is syntactically feasible. | |
624 | |
625 This function returns True if it is adding the candidate pair | |
626 to the current partial isomorphism/monomorphism mapping is allowable. | |
627 The addition is allowable if the inclusion of the candidate pair does | |
628 not make it impossible for an isomorphism/monomorphism to be found. | |
629 """ | |
630 | |
631 # The VF2 algorithm was designed to work with graphs having, at most, | |
632 # one edge connecting any two nodes. This is not the case when | |
633 # dealing with an MultiGraphs. | |
634 # | |
635 # Basically, when we test the look-ahead rules R_pred and R_succ, we | |
636 # will make sure that the number of edges are checked. We also add | |
637 # a R_self check to verify that the number of selfloops is acceptable. | |
638 | |
639 # Users might be comparing DiGraph instances with MultiDiGraph | |
640 # instances. So the generic DiGraphMatcher class must work with | |
641 # MultiDiGraphs. Care must be taken since the value in the innermost | |
642 # dictionary is a singlet for DiGraph instances. For MultiDiGraphs, | |
643 # the value in the innermost dictionary is a list. | |
644 | |
645 ### | |
646 # Test at each step to get a return value as soon as possible. | |
647 ### | |
648 | |
649 # Look ahead 0 | |
650 | |
651 # R_self | |
652 | |
653 # The number of selfloops for G1_node must equal the number of | |
654 # self-loops for G2_node. Without this check, we would fail on R_pred | |
655 # at the next recursion level. This should prune the tree even further. | |
656 if self.test == "mono": | |
657 if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges( | |
658 G2_node, G2_node | |
659 ): | |
660 return False | |
661 else: | |
662 if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges( | |
663 G2_node, G2_node | |
664 ): | |
665 return False | |
666 | |
667 # R_pred | |
668 | |
669 # For each predecessor n' of n in the partial mapping, the | |
670 # corresponding node m' is a predecessor of m, and vice versa. Also, | |
671 # the number of edges must be equal | |
672 if self.test != "mono": | |
673 for predecessor in self.G1.pred[G1_node]: | |
674 if predecessor in self.core_1: | |
675 if not (self.core_1[predecessor] in self.G2.pred[G2_node]): | |
676 return False | |
677 elif self.G1.number_of_edges( | |
678 predecessor, G1_node | |
679 ) != self.G2.number_of_edges(self.core_1[predecessor], G2_node): | |
680 return False | |
681 | |
682 for predecessor in self.G2.pred[G2_node]: | |
683 if predecessor in self.core_2: | |
684 if not (self.core_2[predecessor] in self.G1.pred[G1_node]): | |
685 return False | |
686 elif self.test == "mono": | |
687 if self.G1.number_of_edges( | |
688 self.core_2[predecessor], G1_node | |
689 ) < self.G2.number_of_edges(predecessor, G2_node): | |
690 return False | |
691 else: | |
692 if self.G1.number_of_edges( | |
693 self.core_2[predecessor], G1_node | |
694 ) != self.G2.number_of_edges(predecessor, G2_node): | |
695 return False | |
696 | |
697 # R_succ | |
698 | |
699 # For each successor n' of n in the partial mapping, the corresponding | |
700 # node m' is a successor of m, and vice versa. Also, the number of | |
701 # edges must be equal. | |
702 if self.test != "mono": | |
703 for successor in self.G1[G1_node]: | |
704 if successor in self.core_1: | |
705 if not (self.core_1[successor] in self.G2[G2_node]): | |
706 return False | |
707 elif self.G1.number_of_edges( | |
708 G1_node, successor | |
709 ) != self.G2.number_of_edges(G2_node, self.core_1[successor]): | |
710 return False | |
711 | |
712 for successor in self.G2[G2_node]: | |
713 if successor in self.core_2: | |
714 if not (self.core_2[successor] in self.G1[G1_node]): | |
715 return False | |
716 elif self.test == "mono": | |
717 if self.G1.number_of_edges( | |
718 G1_node, self.core_2[successor] | |
719 ) < self.G2.number_of_edges(G2_node, successor): | |
720 return False | |
721 else: | |
722 if self.G1.number_of_edges( | |
723 G1_node, self.core_2[successor] | |
724 ) != self.G2.number_of_edges(G2_node, successor): | |
725 return False | |
726 | |
727 if self.test != "mono": | |
728 | |
729 # Look ahead 1 | |
730 | |
731 # R_termin | |
732 # The number of predecessors of n that are in T_1^{in} is equal to the | |
733 # number of predecessors of m that are in T_2^{in}. | |
734 num1 = 0 | |
735 for predecessor in self.G1.pred[G1_node]: | |
736 if (predecessor in self.in_1) and (predecessor not in self.core_1): | |
737 num1 += 1 | |
738 num2 = 0 | |
739 for predecessor in self.G2.pred[G2_node]: | |
740 if (predecessor in self.in_2) and (predecessor not in self.core_2): | |
741 num2 += 1 | |
742 if self.test == "graph": | |
743 if not (num1 == num2): | |
744 return False | |
745 else: # self.test == 'subgraph' | |
746 if not (num1 >= num2): | |
747 return False | |
748 | |
749 # The number of successors of n that are in T_1^{in} is equal to the | |
750 # number of successors of m that are in T_2^{in}. | |
751 num1 = 0 | |
752 for successor in self.G1[G1_node]: | |
753 if (successor in self.in_1) and (successor not in self.core_1): | |
754 num1 += 1 | |
755 num2 = 0 | |
756 for successor in self.G2[G2_node]: | |
757 if (successor in self.in_2) and (successor not in self.core_2): | |
758 num2 += 1 | |
759 if self.test == "graph": | |
760 if not (num1 == num2): | |
761 return False | |
762 else: # self.test == 'subgraph' | |
763 if not (num1 >= num2): | |
764 return False | |
765 | |
766 # R_termout | |
767 | |
768 # The number of predecessors of n that are in T_1^{out} is equal to the | |
769 # number of predecessors of m that are in T_2^{out}. | |
770 num1 = 0 | |
771 for predecessor in self.G1.pred[G1_node]: | |
772 if (predecessor in self.out_1) and (predecessor not in self.core_1): | |
773 num1 += 1 | |
774 num2 = 0 | |
775 for predecessor in self.G2.pred[G2_node]: | |
776 if (predecessor in self.out_2) and (predecessor not in self.core_2): | |
777 num2 += 1 | |
778 if self.test == "graph": | |
779 if not (num1 == num2): | |
780 return False | |
781 else: # self.test == 'subgraph' | |
782 if not (num1 >= num2): | |
783 return False | |
784 | |
785 # The number of successors of n that are in T_1^{out} is equal to the | |
786 # number of successors of m that are in T_2^{out}. | |
787 num1 = 0 | |
788 for successor in self.G1[G1_node]: | |
789 if (successor in self.out_1) and (successor not in self.core_1): | |
790 num1 += 1 | |
791 num2 = 0 | |
792 for successor in self.G2[G2_node]: | |
793 if (successor in self.out_2) and (successor not in self.core_2): | |
794 num2 += 1 | |
795 if self.test == "graph": | |
796 if not (num1 == num2): | |
797 return False | |
798 else: # self.test == 'subgraph' | |
799 if not (num1 >= num2): | |
800 return False | |
801 | |
802 # Look ahead 2 | |
803 | |
804 # R_new | |
805 | |
806 # The number of predecessors of n that are neither in the core_1 nor | |
807 # T_1^{in} nor T_1^{out} is equal to the number of predecessors of m | |
808 # that are neither in core_2 nor T_2^{in} nor T_2^{out}. | |
809 num1 = 0 | |
810 for predecessor in self.G1.pred[G1_node]: | |
811 if (predecessor not in self.in_1) and (predecessor not in self.out_1): | |
812 num1 += 1 | |
813 num2 = 0 | |
814 for predecessor in self.G2.pred[G2_node]: | |
815 if (predecessor not in self.in_2) and (predecessor not in self.out_2): | |
816 num2 += 1 | |
817 if self.test == "graph": | |
818 if not (num1 == num2): | |
819 return False | |
820 else: # self.test == 'subgraph' | |
821 if not (num1 >= num2): | |
822 return False | |
823 | |
824 # The number of successors of n that are neither in the core_1 nor | |
825 # T_1^{in} nor T_1^{out} is equal to the number of successors of m | |
826 # that are neither in core_2 nor T_2^{in} nor T_2^{out}. | |
827 num1 = 0 | |
828 for successor in self.G1[G1_node]: | |
829 if (successor not in self.in_1) and (successor not in self.out_1): | |
830 num1 += 1 | |
831 num2 = 0 | |
832 for successor in self.G2[G2_node]: | |
833 if (successor not in self.in_2) and (successor not in self.out_2): | |
834 num2 += 1 | |
835 if self.test == "graph": | |
836 if not (num1 == num2): | |
837 return False | |
838 else: # self.test == 'subgraph' | |
839 if not (num1 >= num2): | |
840 return False | |
841 | |
842 # Otherwise, this node pair is syntactically feasible! | |
843 return True | |
844 | |
845 | |
846 class GMState: | |
847 """Internal representation of state for the GraphMatcher class. | |
848 | |
849 This class is used internally by the GraphMatcher class. It is used | |
850 only to store state specific data. There will be at most G2.order() of | |
851 these objects in memory at a time, due to the depth-first search | |
852 strategy employed by the VF2 algorithm. | |
853 """ | |
854 | |
855 def __init__(self, GM, G1_node=None, G2_node=None): | |
856 """Initializes GMState object. | |
857 | |
858 Pass in the GraphMatcher to which this GMState belongs and the | |
859 new node pair that will be added to the GraphMatcher's current | |
860 isomorphism mapping. | |
861 """ | |
862 self.GM = GM | |
863 | |
864 # Initialize the last stored node pair. | |
865 self.G1_node = None | |
866 self.G2_node = None | |
867 self.depth = len(GM.core_1) | |
868 | |
869 if G1_node is None or G2_node is None: | |
870 # Then we reset the class variables | |
871 GM.core_1 = {} | |
872 GM.core_2 = {} | |
873 GM.inout_1 = {} | |
874 GM.inout_2 = {} | |
875 | |
876 # Watch out! G1_node == 0 should evaluate to True. | |
877 if G1_node is not None and G2_node is not None: | |
878 # Add the node pair to the isomorphism mapping. | |
879 GM.core_1[G1_node] = G2_node | |
880 GM.core_2[G2_node] = G1_node | |
881 | |
882 # Store the node that was added last. | |
883 self.G1_node = G1_node | |
884 self.G2_node = G2_node | |
885 | |
886 # Now we must update the other two vectors. | |
887 # We will add only if it is not in there already! | |
888 self.depth = len(GM.core_1) | |
889 | |
890 # First we add the new nodes... | |
891 if G1_node not in GM.inout_1: | |
892 GM.inout_1[G1_node] = self.depth | |
893 if G2_node not in GM.inout_2: | |
894 GM.inout_2[G2_node] = self.depth | |
895 | |
896 # Now we add every other node... | |
897 | |
898 # Updates for T_1^{inout} | |
899 new_nodes = set() | |
900 for node in GM.core_1: | |
901 new_nodes.update( | |
902 [neighbor for neighbor in GM.G1[node] if neighbor not in GM.core_1] | |
903 ) | |
904 for node in new_nodes: | |
905 if node not in GM.inout_1: | |
906 GM.inout_1[node] = self.depth | |
907 | |
908 # Updates for T_2^{inout} | |
909 new_nodes = set() | |
910 for node in GM.core_2: | |
911 new_nodes.update( | |
912 [neighbor for neighbor in GM.G2[node] if neighbor not in GM.core_2] | |
913 ) | |
914 for node in new_nodes: | |
915 if node not in GM.inout_2: | |
916 GM.inout_2[node] = self.depth | |
917 | |
918 def restore(self): | |
919 """Deletes the GMState object and restores the class variables.""" | |
920 # First we remove the node that was added from the core vectors. | |
921 # Watch out! G1_node == 0 should evaluate to True. | |
922 if self.G1_node is not None and self.G2_node is not None: | |
923 del self.GM.core_1[self.G1_node] | |
924 del self.GM.core_2[self.G2_node] | |
925 | |
926 # Now we revert the other two vectors. | |
927 # Thus, we delete all entries which have this depth level. | |
928 for vector in (self.GM.inout_1, self.GM.inout_2): | |
929 for node in list(vector.keys()): | |
930 if vector[node] == self.depth: | |
931 del vector[node] | |
932 | |
933 | |
934 class DiGMState: | |
935 """Internal representation of state for the DiGraphMatcher class. | |
936 | |
937 This class is used internally by the DiGraphMatcher class. It is used | |
938 only to store state specific data. There will be at most G2.order() of | |
939 these objects in memory at a time, due to the depth-first search | |
940 strategy employed by the VF2 algorithm. | |
941 | |
942 """ | |
943 | |
944 def __init__(self, GM, G1_node=None, G2_node=None): | |
945 """Initializes DiGMState object. | |
946 | |
947 Pass in the DiGraphMatcher to which this DiGMState belongs and the | |
948 new node pair that will be added to the GraphMatcher's current | |
949 isomorphism mapping. | |
950 """ | |
951 self.GM = GM | |
952 | |
953 # Initialize the last stored node pair. | |
954 self.G1_node = None | |
955 self.G2_node = None | |
956 self.depth = len(GM.core_1) | |
957 | |
958 if G1_node is None or G2_node is None: | |
959 # Then we reset the class variables | |
960 GM.core_1 = {} | |
961 GM.core_2 = {} | |
962 GM.in_1 = {} | |
963 GM.in_2 = {} | |
964 GM.out_1 = {} | |
965 GM.out_2 = {} | |
966 | |
967 # Watch out! G1_node == 0 should evaluate to True. | |
968 if G1_node is not None and G2_node is not None: | |
969 # Add the node pair to the isomorphism mapping. | |
970 GM.core_1[G1_node] = G2_node | |
971 GM.core_2[G2_node] = G1_node | |
972 | |
973 # Store the node that was added last. | |
974 self.G1_node = G1_node | |
975 self.G2_node = G2_node | |
976 | |
977 # Now we must update the other four vectors. | |
978 # We will add only if it is not in there already! | |
979 self.depth = len(GM.core_1) | |
980 | |
981 # First we add the new nodes... | |
982 for vector in (GM.in_1, GM.out_1): | |
983 if G1_node not in vector: | |
984 vector[G1_node] = self.depth | |
985 for vector in (GM.in_2, GM.out_2): | |
986 if G2_node not in vector: | |
987 vector[G2_node] = self.depth | |
988 | |
989 # Now we add every other node... | |
990 | |
991 # Updates for T_1^{in} | |
992 new_nodes = set() | |
993 for node in GM.core_1: | |
994 new_nodes.update( | |
995 [ | |
996 predecessor | |
997 for predecessor in GM.G1.predecessors(node) | |
998 if predecessor not in GM.core_1 | |
999 ] | |
1000 ) | |
1001 for node in new_nodes: | |
1002 if node not in GM.in_1: | |
1003 GM.in_1[node] = self.depth | |
1004 | |
1005 # Updates for T_2^{in} | |
1006 new_nodes = set() | |
1007 for node in GM.core_2: | |
1008 new_nodes.update( | |
1009 [ | |
1010 predecessor | |
1011 for predecessor in GM.G2.predecessors(node) | |
1012 if predecessor not in GM.core_2 | |
1013 ] | |
1014 ) | |
1015 for node in new_nodes: | |
1016 if node not in GM.in_2: | |
1017 GM.in_2[node] = self.depth | |
1018 | |
1019 # Updates for T_1^{out} | |
1020 new_nodes = set() | |
1021 for node in GM.core_1: | |
1022 new_nodes.update( | |
1023 [ | |
1024 successor | |
1025 for successor in GM.G1.successors(node) | |
1026 if successor not in GM.core_1 | |
1027 ] | |
1028 ) | |
1029 for node in new_nodes: | |
1030 if node not in GM.out_1: | |
1031 GM.out_1[node] = self.depth | |
1032 | |
1033 # Updates for T_2^{out} | |
1034 new_nodes = set() | |
1035 for node in GM.core_2: | |
1036 new_nodes.update( | |
1037 [ | |
1038 successor | |
1039 for successor in GM.G2.successors(node) | |
1040 if successor not in GM.core_2 | |
1041 ] | |
1042 ) | |
1043 for node in new_nodes: | |
1044 if node not in GM.out_2: | |
1045 GM.out_2[node] = self.depth | |
1046 | |
1047 def restore(self): | |
1048 """Deletes the DiGMState object and restores the class variables.""" | |
1049 | |
1050 # First we remove the node that was added from the core vectors. | |
1051 # Watch out! G1_node == 0 should evaluate to True. | |
1052 if self.G1_node is not None and self.G2_node is not None: | |
1053 del self.GM.core_1[self.G1_node] | |
1054 del self.GM.core_2[self.G2_node] | |
1055 | |
1056 # Now we revert the other four vectors. | |
1057 # Thus, we delete all entries which have this depth level. | |
1058 for vector in (self.GM.in_1, self.GM.in_2, self.GM.out_1, self.GM.out_2): | |
1059 for node in list(vector.keys()): | |
1060 if vector[node] == self.depth: | |
1061 del vector[node] |