Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2*************
3VF2 Algorithm
4*************
6An implementation of VF2 algorithm for graph isomorphism testing.
8The simplest interface to use this module is to call the
9:func:`is_isomorphic <networkx.algorithms.isomorphism.is_isomorphic>`
10function.
12Introduction
13------------
15The GraphMatcher and DiGraphMatcher are responsible for matching
16graphs or directed graphs in a predetermined manner. This
17usually means a check for an isomorphism, though other checks
18are also possible. For example, a subgraph of one graph
19can be checked for isomorphism to a second graph.
21Matching is done via syntactic feasibility. It is also possible
22to check for semantic feasibility. Feasibility, then, is defined
23as the logical AND of the two functions.
25To include a semantic check, the (Di)GraphMatcher class should be
26subclassed, and the
27:meth:`semantic_feasibility <networkx.algorithms.isomorphism.GraphMatcher.semantic_feasibility>`
28function should be redefined. By default, the semantic feasibility function always
29returns ``True``. The effect of this is that semantics are not
30considered in the matching of G1 and G2.
32Examples
33--------
35Suppose G1 and G2 are isomorphic graphs. Verification is as follows:
37>>> from networkx.algorithms import isomorphism
38>>> G1 = nx.path_graph(4)
39>>> G2 = nx.path_graph(4)
40>>> GM = isomorphism.GraphMatcher(G1, G2)
41>>> GM.is_isomorphic()
42True
44GM.mapping stores the isomorphism mapping from G1 to G2.
46>>> GM.mapping
47{0: 0, 1: 1, 2: 2, 3: 3}
50Suppose G1 and G2 are isomorphic directed graphs.
51Verification is as follows:
53>>> G1 = nx.path_graph(4, create_using=nx.DiGraph)
54>>> G2 = nx.path_graph(4, create_using=nx.DiGraph)
55>>> DiGM = isomorphism.DiGraphMatcher(G1, G2)
56>>> DiGM.is_isomorphic()
57True
59DiGM.mapping stores the isomorphism mapping from G1 to G2.
61>>> DiGM.mapping
62{0: 0, 1: 1, 2: 2, 3: 3}
66Subgraph Isomorphism
67--------------------
68Graph theory literature can be ambiguous about the meaning of the
69above statement, and we seek to clarify it now.
71In the VF2 literature, a mapping ``M`` is said to be a graph-subgraph
72isomorphism iff ``M`` is an isomorphism between ``G2`` and a subgraph of ``G1``.
73Thus, to say that ``G1`` and ``G2`` are graph-subgraph isomorphic is to say
74that a subgraph of ``G1`` is isomorphic to ``G2``.
76Other literature uses the phrase 'subgraph isomorphic' as in '``G1`` does
77not have a subgraph isomorphic to ``G2``'. Another use is as an in adverb
78for isomorphic. Thus, to say that ``G1`` and ``G2`` are subgraph isomorphic
79is to say that a subgraph of ``G1`` is isomorphic to ``G2``.
81Finally, the term 'subgraph' can have multiple meanings. In this
82context, 'subgraph' always means a 'node-induced subgraph'. Edge-induced
83subgraph isomorphisms are not directly supported, but one should be
84able to perform the check by making use of
85:func:`line_graph <networkx.generators.line.line_graph>`. For
86subgraphs which are not induced, the term 'monomorphism' is preferred
87over 'isomorphism'.
89Let ``G = (N, E)`` be a graph with a set of nodes ``N`` and set of edges ``E``.
91If ``G' = (N', E')`` is a subgraph, then:
92 ``N'`` is a subset of ``N`` and
93 ``E'`` is a subset of ``E``.
95If ``G' = (N', E')`` is a node-induced subgraph, then:
96 ``N'`` is a subset of ``N`` and
97 ``E'`` is the subset of edges in ``E`` relating nodes in ``N'``.
99If ``G' = (N', E')`` is an edge-induced subgraph, then:
100 ``N'`` is the subset of nodes in ``N`` related by edges in ``E'`` and
101 ``E'`` is a subset of ``E``.
103If ``G' = (N', E')`` is a monomorphism, then:
104 ``N'`` is a subset of ``N`` and
105 ``E'`` is a subset of the set of edges in ``E`` relating nodes in ``N'``.
107Note that if ``G'`` is a node-induced subgraph of ``G``, then it is always a
108subgraph monomorphism of ``G``, but the opposite is not always true, as a
109monomorphism can have fewer edges.
111References
112----------
113[1] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento,
114 "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs",
115 IEEE Transactions on Pattern Analysis and Machine Intelligence,
116 vol. 26, no. 10, pp. 1367-1372, Oct., 2004.
117 http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf
119[2] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, "An Improved
120 Algorithm for Matching Large Graphs", 3rd IAPR-TC15 Workshop
121 on Graph-based Representations in Pattern Recognition, Cuen,
122 pp. 149-159, 2001.
123 https://www.researchgate.net/publication/200034365_An_Improved_Algorithm_for_Matching_Large_Graphs
125See Also
126--------
127:meth:`semantic_feasibility <networkx.algorithms.isomorphism.GraphMatcher.semantic_feasibility>`
128:meth:`syntactic_feasibility <networkx.algorithms.isomorphism.GraphMatcher.syntactic_feasibility>`
130Notes
131-----
133The implementation handles both directed and undirected graphs as well
134as multigraphs.
136In general, the subgraph isomorphism problem is NP-complete whereas the
137graph isomorphism problem is most likely not NP-complete (although no
138polynomial-time algorithm is known to exist).
140"""
142# This work was originally coded by Christopher Ellison
143# as part of the Computational Mechanics Python (CMPy) project.
144# James P. Crutchfield, principal investigator.
145# Complexity Sciences Center and Physics Department, UC Davis.
147import sys
149import networkx as nx
151__all__ = ["GraphMatcher", "DiGraphMatcher"]
154class GraphMatcher:
155 """Implementation of VF2 algorithm for matching undirected graphs.
157 Suitable for Graph and MultiGraph instances.
158 """
160 def __init__(self, G1, G2):
161 """Initialize GraphMatcher.
163 Parameters
164 ----------
165 G1,G2: NetworkX Graph or MultiGraph instances.
166 The two graphs to check for isomorphism or monomorphism.
168 Examples
169 --------
170 To create a GraphMatcher which checks for syntactic feasibility:
172 >>> from networkx.algorithms import isomorphism
173 >>> G1 = nx.path_graph(4)
174 >>> G2 = nx.path_graph(4)
175 >>> GM = isomorphism.GraphMatcher(G1, G2)
176 """
177 if G1.is_directed() != G2.is_directed():
178 raise nx.NetworkXError("G1 and G2 must have the same directedness")
180 is_directed_matcher = self._is_directed_matcher()
181 if not is_directed_matcher and (G1.is_directed() or G2.is_directed()):
182 raise nx.NetworkXError(
183 "(Multi-)GraphMatcher() not defined for directed graphs. "
184 "Use (Multi-)DiGraphMatcher() instead."
185 )
187 if is_directed_matcher and not (G1.is_directed() and G2.is_directed()):
188 raise nx.NetworkXError(
189 "(Multi-)DiGraphMatcher() not defined for undirected graphs. "
190 "Use (Multi-)GraphMatcher() instead."
191 )
193 self.G1 = G1
194 self.G2 = G2
195 self.G1_nodes = set(G1.nodes())
196 self.G2_nodes = set(G2.nodes())
197 self.G2_node_order = {n: i for i, n in enumerate(G2)}
199 # Set recursion limit.
200 self.old_recursion_limit = sys.getrecursionlimit()
201 expected_max_recursion_level = len(self.G2)
202 if self.old_recursion_limit < 1.5 * expected_max_recursion_level:
203 # Give some breathing room.
204 sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
206 # Declare that we will be searching for a graph-graph isomorphism.
207 self.test = "graph"
209 # Initialize state
210 self.initialize()
212 def _is_directed_matcher(self):
213 return False
215 def reset_recursion_limit(self):
216 """Restores the recursion limit."""
217 # TODO:
218 # Currently, we use recursion and set the recursion level higher.
219 # It would be nice to restore the level, but because the
220 # (Di)GraphMatcher classes make use of cyclic references, garbage
221 # collection will never happen when we define __del__() to
222 # restore the recursion level. The result is a memory leak.
223 # So for now, we do not automatically restore the recursion level,
224 # and instead provide a method to do this manually. Eventually,
225 # we should turn this into a non-recursive implementation.
226 sys.setrecursionlimit(self.old_recursion_limit)
228 def candidate_pairs_iter(self):
229 """Iterator over candidate pairs of nodes in G1 and G2."""
231 # All computations are done using the current state!
233 G1_nodes = self.G1_nodes
234 G2_nodes = self.G2_nodes
235 min_key = self.G2_node_order.__getitem__
237 # First we compute the inout-terminal sets.
238 T1_inout = [node for node in self.inout_1 if node not in self.core_1]
239 T2_inout = [node for node in self.inout_2 if node not in self.core_2]
241 # If T1_inout and T2_inout are both nonempty.
242 # P(s) = T1_inout x {min T2_inout}
243 if T1_inout and T2_inout:
244 node_2 = min(T2_inout, key=min_key)
245 for node_1 in T1_inout:
246 yield node_1, node_2
248 else:
249 # If T1_inout and T2_inout were both empty....
250 # P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
251 # if not (T1_inout or T2_inout): # as suggested by [2], incorrect
252 if 1: # as inferred from [1], correct
253 # First we determine the candidate node for G2
254 other_node = min(G2_nodes - set(self.core_2), key=min_key)
255 for node in self.G1:
256 if node not in self.core_1:
257 yield node, other_node
259 # For all other cases, we don't have any candidate pairs.
261 def initialize(self):
262 """Reinitializes the state of the algorithm.
264 This method should be redefined if using something other than GMState.
265 If only subclassing GraphMatcher, a redefinition is not necessary.
267 """
269 # core_1[n] contains the index of the node paired with n, which is m,
270 # provided n is in the mapping.
271 # core_2[m] contains the index of the node paired with m, which is n,
272 # provided m is in the mapping.
273 self.core_1 = {}
274 self.core_2 = {}
276 # See the paper for definitions of M_x and T_x^{y}
278 # inout_1[n] is non-zero if n is in M_1 or in T_1^{inout}
279 # inout_2[m] is non-zero if m is in M_2 or in T_2^{inout}
280 #
281 # The value stored is the depth of the SSR tree when the node became
282 # part of the corresponding set.
283 self.inout_1 = {}
284 self.inout_2 = {}
285 # Practically, these sets simply store the nodes in the subgraph.
287 self.state = GMState(self)
289 # Provide a convenient way to access the isomorphism mapping.
290 self.mapping = self.core_1.copy()
292 def is_isomorphic(self):
293 """Returns True if G1 and G2 are isomorphic graphs."""
295 # Let's do two very quick checks!
296 # QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)?
297 # For now, I just copy the code.
299 # Check global properties
300 if self.G1.order() != self.G2.order():
301 return False
303 # Check local properties
304 d1 = sorted(d for n, d in self.G1.degree())
305 d2 = sorted(d for n, d in self.G2.degree())
306 if d1 != d2:
307 return False
309 try:
310 x = next(self.isomorphisms_iter())
311 return True
312 except StopIteration:
313 return False
315 def isomorphisms_iter(self):
316 """Generator over isomorphisms between G1 and G2."""
317 # Declare that we are looking for a graph-graph isomorphism.
318 self.test = "graph"
319 self.initialize()
320 yield from self.match()
322 def match(self):
323 """Extends the isomorphism mapping.
325 This function is called recursively to determine if a complete
326 isomorphism can be found between G1 and G2. It cleans up the class
327 variables after each recursive call. If an isomorphism is found,
328 we yield the mapping.
330 """
331 if len(self.core_1) == len(self.G2):
332 # Save the final mapping, otherwise garbage collection deletes it.
333 self.mapping = self.core_1.copy()
334 # The mapping is complete.
335 yield self.mapping
336 else:
337 for G1_node, G2_node in self.candidate_pairs_iter():
338 if self.syntactic_feasibility(G1_node, G2_node):
339 if self.semantic_feasibility(G1_node, G2_node):
340 # Recursive call, adding the feasible state.
341 newstate = self.state.__class__(self, G1_node, G2_node)
342 yield from self.match()
344 # restore data structures
345 newstate.restore()
347 def semantic_feasibility(self, G1_node, G2_node):
348 """Returns True if adding (G1_node, G2_node) is semantically feasible.
350 The semantic feasibility function should return True if it is
351 acceptable to add the candidate pair (G1_node, G2_node) to the current
352 partial isomorphism mapping. The logic should focus on semantic
353 information contained in the edge data or a formalized node class.
355 By acceptable, we mean that the subsequent mapping can still become a
356 complete isomorphism mapping. Thus, if adding the candidate pair
357 definitely makes it so that the subsequent mapping cannot become a
358 complete isomorphism mapping, then this function must return False.
360 The default semantic feasibility function always returns True. The
361 effect is that semantics are not considered in the matching of G1
362 and G2.
364 The semantic checks might differ based on the what type of test is
365 being performed. A keyword description of the test is stored in
366 self.test. Here is a quick description of the currently implemented
367 tests::
369 test='graph'
370 Indicates that the graph matcher is looking for a graph-graph
371 isomorphism.
373 test='subgraph'
374 Indicates that the graph matcher is looking for a subgraph-graph
375 isomorphism such that a subgraph of G1 is isomorphic to G2.
377 test='mono'
378 Indicates that the graph matcher is looking for a subgraph-graph
379 monomorphism such that a subgraph of G1 is monomorphic to G2.
381 Any subclass which redefines semantic_feasibility() must maintain
382 the above form to keep the match() method functional. Implementations
383 should consider multigraphs.
384 """
385 return True
387 def subgraph_is_isomorphic(self):
388 """Returns `True` if a subgraph of ``G1`` is isomorphic to ``G2``.
390 Examples
391 --------
392 When creating the `GraphMatcher`, the order of the arguments is important
394 >>> G = nx.Graph([("A", "B"), ("B", "C"), ("A", "C")])
395 >>> H = nx.Graph([(0, 1), (1, 2), (0, 2), (1, 3), (0, 4)])
397 Check whether a subgraph of G is isomorphic to H:
399 >>> isomatcher = nx.isomorphism.GraphMatcher(G, H)
400 >>> isomatcher.subgraph_is_isomorphic()
401 False
403 Check whether a subgraph of H is isomorphic to G:
405 >>> isomatcher = nx.isomorphism.GraphMatcher(H, G)
406 >>> isomatcher.subgraph_is_isomorphic()
407 True
408 """
409 try:
410 x = next(self.subgraph_isomorphisms_iter())
411 return True
412 except StopIteration:
413 return False
415 def subgraph_is_monomorphic(self):
416 """Returns `True` if a subgraph of ``G1`` is monomorphic to ``G2``.
418 Examples
419 --------
420 When creating the `GraphMatcher`, the order of the arguments is important.
422 >>> G = nx.Graph([("A", "B"), ("B", "C")])
423 >>> H = nx.Graph([(0, 1), (1, 2), (0, 2)])
425 Check whether a subgraph of G is monomorphic to H:
427 >>> isomatcher = nx.isomorphism.GraphMatcher(G, H)
428 >>> isomatcher.subgraph_is_monomorphic()
429 False
431 Check whether a subgraph of H is monomorphic to G:
433 >>> isomatcher = nx.isomorphism.GraphMatcher(H, G)
434 >>> isomatcher.subgraph_is_monomorphic()
435 True
436 """
437 try:
438 x = next(self.subgraph_monomorphisms_iter())
439 return True
440 except StopIteration:
441 return False
443 def subgraph_isomorphisms_iter(self):
444 """Generator over isomorphisms between a subgraph of ``G1`` and ``G2``.
446 Examples
447 --------
448 When creating the `GraphMatcher`, the order of the arguments is important
450 >>> G = nx.Graph([("A", "B"), ("B", "C"), ("A", "C")])
451 >>> H = nx.Graph([(0, 1), (1, 2), (0, 2), (1, 3), (0, 4)])
453 Yield isomorphic mappings between ``H`` and subgraphs of ``G``:
455 >>> isomatcher = nx.isomorphism.GraphMatcher(G, H)
456 >>> list(isomatcher.subgraph_isomorphisms_iter())
457 []
459 Yield isomorphic mappings between ``G`` and subgraphs of ``H``:
461 >>> isomatcher = nx.isomorphism.GraphMatcher(H, G)
462 >>> next(isomatcher.subgraph_isomorphisms_iter())
463 {0: 'A', 1: 'B', 2: 'C'}
465 """
466 # Declare that we are looking for graph-subgraph isomorphism.
467 self.test = "subgraph"
468 self.initialize()
469 yield from self.match()
471 def subgraph_monomorphisms_iter(self):
472 """Generator over monomorphisms between a subgraph of ``G1`` and ``G2``.
474 Examples
475 --------
476 When creating the `GraphMatcher`, the order of the arguments is important.
478 >>> G = nx.Graph([("A", "B"), ("B", "C")])
479 >>> H = nx.Graph([(0, 1), (1, 2), (0, 2)])
481 Yield monomorphic mappings between ``H`` and subgraphs of ``G``:
483 >>> isomatcher = nx.isomorphism.GraphMatcher(G, H)
484 >>> list(isomatcher.subgraph_monomorphisms_iter())
485 []
487 Yield monomorphic mappings between ``G`` and subgraphs of ``H``:
489 >>> isomatcher = nx.isomorphism.GraphMatcher(H, G)
490 >>> next(isomatcher.subgraph_monomorphisms_iter())
491 {0: 'A', 1: 'B', 2: 'C'}
492 """
493 # Declare that we are looking for graph-subgraph monomorphism.
494 self.test = "mono"
495 self.initialize()
496 yield from self.match()
498 def syntactic_feasibility(self, G1_node, G2_node):
499 """Returns True if adding (G1_node, G2_node) is syntactically feasible.
501 This function returns True if it is adding the candidate pair
502 to the current partial isomorphism/monomorphism mapping is allowable.
503 The addition is allowable if the inclusion of the candidate pair does
504 not make it impossible for an isomorphism/monomorphism to be found.
505 """
507 # The VF2 algorithm was designed to work with graphs having, at most,
508 # one edge connecting any two nodes. This is not the case when
509 # dealing with an MultiGraphs.
510 #
511 # Basically, when we test the look-ahead rules R_neighbor, we will
512 # make sure that the number of edges are checked. We also add
513 # a R_self check to verify that the number of selfloops is acceptable.
514 #
515 # Users might be comparing Graph instances with MultiGraph instances.
516 # So the generic GraphMatcher class must work with MultiGraphs.
517 # Care must be taken since the value in the innermost dictionary is a
518 # singlet for Graph instances. For MultiGraphs, the value in the
519 # innermost dictionary is a list.
521 ###
522 # Test at each step to get a return value as soon as possible.
523 ###
525 # Look ahead 0
527 # R_self
529 # The number of selfloops for G1_node must equal the number of
530 # self-loops for G2_node. Without this check, we would fail on
531 # R_neighbor at the next recursion level. But it is good to prune the
532 # search tree now.
534 if self.test == "mono":
535 if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges(
536 G2_node, G2_node
537 ):
538 return False
539 else:
540 if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges(
541 G2_node, G2_node
542 ):
543 return False
545 # R_neighbor
547 # For each neighbor n' of n in the partial mapping, the corresponding
548 # node m' is a neighbor of m, and vice versa. Also, the number of
549 # edges must be equal.
550 if self.test != "mono":
551 for neighbor in self.G1[G1_node]:
552 if neighbor in self.core_1:
553 if self.core_1[neighbor] not in self.G2[G2_node]:
554 return False
555 elif self.G1.number_of_edges(
556 neighbor, G1_node
557 ) != self.G2.number_of_edges(self.core_1[neighbor], G2_node):
558 return False
560 for neighbor in self.G2[G2_node]:
561 if neighbor in self.core_2:
562 if self.core_2[neighbor] not in self.G1[G1_node]:
563 return False
564 elif self.test == "mono":
565 if self.G1.number_of_edges(
566 self.core_2[neighbor], G1_node
567 ) < self.G2.number_of_edges(neighbor, G2_node):
568 return False
569 else:
570 if self.G1.number_of_edges(
571 self.core_2[neighbor], G1_node
572 ) != self.G2.number_of_edges(neighbor, G2_node):
573 return False
575 if self.test != "mono":
576 # Look ahead 1
578 # R_terminout
579 # The number of neighbors of n in T_1^{inout} is equal to the
580 # number of neighbors of m that are in T_2^{inout}, and vice versa.
581 num1 = 0
582 for neighbor in self.G1[G1_node]:
583 if (neighbor in self.inout_1) and (neighbor not in self.core_1):
584 num1 += 1
585 num2 = 0
586 for neighbor in self.G2[G2_node]:
587 if (neighbor in self.inout_2) and (neighbor not in self.core_2):
588 num2 += 1
589 if self.test == "graph":
590 if num1 != num2:
591 return False
592 else: # self.test == 'subgraph'
593 if not (num1 >= num2):
594 return False
596 # Look ahead 2
598 # R_new
600 # The number of neighbors of n that are neither in the core_1 nor
601 # T_1^{inout} is equal to the number of neighbors of m
602 # that are neither in core_2 nor T_2^{inout}.
603 num1 = 0
604 for neighbor in self.G1[G1_node]:
605 if neighbor not in self.inout_1:
606 num1 += 1
607 num2 = 0
608 for neighbor in self.G2[G2_node]:
609 if neighbor not in self.inout_2:
610 num2 += 1
611 if self.test == "graph":
612 if num1 != num2:
613 return False
614 else: # self.test == 'subgraph'
615 if not (num1 >= num2):
616 return False
618 # Otherwise, this node pair is syntactically feasible!
619 return True
622class DiGraphMatcher(GraphMatcher):
623 """Implementation of VF2 algorithm for matching directed graphs.
625 Suitable for DiGraph and MultiDiGraph instances.
626 """
628 def __init__(self, G1, G2):
629 """Initialize DiGraphMatcher.
631 G1 and G2 should be nx.Graph or nx.MultiGraph instances.
633 Examples
634 --------
635 To create a GraphMatcher which checks for syntactic feasibility:
637 >>> from networkx.algorithms import isomorphism
638 >>> G1 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
639 >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
640 >>> DiGM = isomorphism.DiGraphMatcher(G1, G2)
641 """
642 super().__init__(G1, G2)
644 def _is_directed_matcher(self):
645 return True
647 def candidate_pairs_iter(self):
648 """Iterator over candidate pairs of nodes in G1 and G2."""
650 # All computations are done using the current state!
652 G1_nodes = self.G1_nodes
653 G2_nodes = self.G2_nodes
654 min_key = self.G2_node_order.__getitem__
656 # First we compute the out-terminal sets.
657 T1_out = [node for node in self.out_1 if node not in self.core_1]
658 T2_out = [node for node in self.out_2 if node not in self.core_2]
660 # If T1_out and T2_out are both nonempty.
661 # P(s) = T1_out x {min T2_out}
662 if T1_out and T2_out:
663 node_2 = min(T2_out, key=min_key)
664 for node_1 in T1_out:
665 yield node_1, node_2
667 # If T1_out and T2_out were both empty....
668 # We compute the in-terminal sets.
670 # elif not (T1_out or T2_out): # as suggested by [2], incorrect
671 else: # as suggested by [1], correct
672 T1_in = [node for node in self.in_1 if node not in self.core_1]
673 T2_in = [node for node in self.in_2 if node not in self.core_2]
675 # If T1_in and T2_in are both nonempty.
676 # P(s) = T1_out x {min T2_out}
677 if T1_in and T2_in:
678 node_2 = min(T2_in, key=min_key)
679 for node_1 in T1_in:
680 yield node_1, node_2
682 # If all terminal sets are empty...
683 # P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
685 # elif not (T1_in or T2_in): # as suggested by [2], incorrect
686 else: # as inferred from [1], correct
687 node_2 = min(G2_nodes - set(self.core_2), key=min_key)
688 for node_1 in G1_nodes:
689 if node_1 not in self.core_1:
690 yield node_1, node_2
692 # For all other cases, we don't have any candidate pairs.
694 def initialize(self):
695 """Reinitializes the state of the algorithm.
697 This method should be redefined if using something other than DiGMState.
698 If only subclassing GraphMatcher, a redefinition is not necessary.
699 """
701 # core_1[n] contains the index of the node paired with n, which is m,
702 # provided n is in the mapping.
703 # core_2[m] contains the index of the node paired with m, which is n,
704 # provided m is in the mapping.
705 self.core_1 = {}
706 self.core_2 = {}
708 # See the paper for definitions of M_x and T_x^{y}
710 # in_1[n] is non-zero if n is in M_1 or in T_1^{in}
711 # out_1[n] is non-zero if n is in M_1 or in T_1^{out}
712 #
713 # in_2[m] is non-zero if m is in M_2 or in T_2^{in}
714 # out_2[m] is non-zero if m is in M_2 or in T_2^{out}
715 #
716 # The value stored is the depth of the search tree when the node became
717 # part of the corresponding set.
718 self.in_1 = {}
719 self.in_2 = {}
720 self.out_1 = {}
721 self.out_2 = {}
723 self.state = DiGMState(self)
725 # Provide a convenient way to access the isomorphism mapping.
726 self.mapping = self.core_1.copy()
728 def syntactic_feasibility(self, G1_node, G2_node):
729 """Returns True if adding (G1_node, G2_node) is syntactically feasible.
731 This function returns True if it is adding the candidate pair
732 to the current partial isomorphism/monomorphism mapping is allowable.
733 The addition is allowable if the inclusion of the candidate pair does
734 not make it impossible for an isomorphism/monomorphism to be found.
735 """
737 # The VF2 algorithm was designed to work with graphs having, at most,
738 # one edge connecting any two nodes. This is not the case when
739 # dealing with an MultiGraphs.
740 #
741 # Basically, when we test the look-ahead rules R_pred and R_succ, we
742 # will make sure that the number of edges are checked. We also add
743 # a R_self check to verify that the number of selfloops is acceptable.
745 # Users might be comparing DiGraph instances with MultiDiGraph
746 # instances. So the generic DiGraphMatcher class must work with
747 # MultiDiGraphs. Care must be taken since the value in the innermost
748 # dictionary is a singlet for DiGraph instances. For MultiDiGraphs,
749 # the value in the innermost dictionary is a list.
751 ###
752 # Test at each step to get a return value as soon as possible.
753 ###
755 # Look ahead 0
757 # R_self
759 # The number of selfloops for G1_node must equal the number of
760 # self-loops for G2_node. Without this check, we would fail on R_pred
761 # at the next recursion level. This should prune the tree even further.
762 if self.test == "mono":
763 if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges(
764 G2_node, G2_node
765 ):
766 return False
767 else:
768 if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges(
769 G2_node, G2_node
770 ):
771 return False
773 # R_pred
775 # For each predecessor n' of n in the partial mapping, the
776 # corresponding node m' is a predecessor of m, and vice versa. Also,
777 # the number of edges must be equal
778 if self.test != "mono":
779 for predecessor in self.G1.pred[G1_node]:
780 if predecessor in self.core_1:
781 if self.core_1[predecessor] not in self.G2.pred[G2_node]:
782 return False
783 elif self.G1.number_of_edges(
784 predecessor, G1_node
785 ) != self.G2.number_of_edges(self.core_1[predecessor], G2_node):
786 return False
788 for predecessor in self.G2.pred[G2_node]:
789 if predecessor in self.core_2:
790 if self.core_2[predecessor] not in self.G1.pred[G1_node]:
791 return False
792 elif self.test == "mono":
793 if self.G1.number_of_edges(
794 self.core_2[predecessor], G1_node
795 ) < self.G2.number_of_edges(predecessor, G2_node):
796 return False
797 else:
798 if self.G1.number_of_edges(
799 self.core_2[predecessor], G1_node
800 ) != self.G2.number_of_edges(predecessor, G2_node):
801 return False
803 # R_succ
805 # For each successor n' of n in the partial mapping, the corresponding
806 # node m' is a successor of m, and vice versa. Also, the number of
807 # edges must be equal.
808 if self.test != "mono":
809 for successor in self.G1[G1_node]:
810 if successor in self.core_1:
811 if self.core_1[successor] not in self.G2[G2_node]:
812 return False
813 elif self.G1.number_of_edges(
814 G1_node, successor
815 ) != self.G2.number_of_edges(G2_node, self.core_1[successor]):
816 return False
818 for successor in self.G2[G2_node]:
819 if successor in self.core_2:
820 if self.core_2[successor] not in self.G1[G1_node]:
821 return False
822 elif self.test == "mono":
823 if self.G1.number_of_edges(
824 G1_node, self.core_2[successor]
825 ) < self.G2.number_of_edges(G2_node, successor):
826 return False
827 else:
828 if self.G1.number_of_edges(
829 G1_node, self.core_2[successor]
830 ) != self.G2.number_of_edges(G2_node, successor):
831 return False
833 if self.test != "mono":
834 # Look ahead 1
836 # R_termin
837 # The number of predecessors of n that are in T_1^{in} is equal to the
838 # number of predecessors of m that are in T_2^{in}.
839 num1 = 0
840 for predecessor in self.G1.pred[G1_node]:
841 if (predecessor in self.in_1) and (predecessor not in self.core_1):
842 num1 += 1
843 num2 = 0
844 for predecessor in self.G2.pred[G2_node]:
845 if (predecessor in self.in_2) and (predecessor not in self.core_2):
846 num2 += 1
847 if self.test == "graph":
848 if num1 != num2:
849 return False
850 else: # self.test == 'subgraph'
851 if not (num1 >= num2):
852 return False
854 # The number of successors of n that are in T_1^{in} is equal to the
855 # number of successors of m that are in T_2^{in}.
856 num1 = 0
857 for successor in self.G1[G1_node]:
858 if (successor in self.in_1) and (successor not in self.core_1):
859 num1 += 1
860 num2 = 0
861 for successor in self.G2[G2_node]:
862 if (successor in self.in_2) and (successor not in self.core_2):
863 num2 += 1
864 if self.test == "graph":
865 if num1 != num2:
866 return False
867 else: # self.test == 'subgraph'
868 if not (num1 >= num2):
869 return False
871 # R_termout
873 # The number of predecessors of n that are in T_1^{out} is equal to the
874 # number of predecessors of m that are in T_2^{out}.
875 num1 = 0
876 for predecessor in self.G1.pred[G1_node]:
877 if (predecessor in self.out_1) and (predecessor not in self.core_1):
878 num1 += 1
879 num2 = 0
880 for predecessor in self.G2.pred[G2_node]:
881 if (predecessor in self.out_2) and (predecessor not in self.core_2):
882 num2 += 1
883 if self.test == "graph":
884 if num1 != num2:
885 return False
886 else: # self.test == 'subgraph'
887 if not (num1 >= num2):
888 return False
890 # The number of successors of n that are in T_1^{out} is equal to the
891 # number of successors of m that are in T_2^{out}.
892 num1 = 0
893 for successor in self.G1[G1_node]:
894 if (successor in self.out_1) and (successor not in self.core_1):
895 num1 += 1
896 num2 = 0
897 for successor in self.G2[G2_node]:
898 if (successor in self.out_2) and (successor not in self.core_2):
899 num2 += 1
900 if self.test == "graph":
901 if num1 != num2:
902 return False
903 else: # self.test == 'subgraph'
904 if not (num1 >= num2):
905 return False
907 # Look ahead 2
909 # R_new
911 # The number of predecessors of n that are neither in the core_1 nor
912 # T_1^{in} nor T_1^{out} is equal to the number of predecessors of m
913 # that are neither in core_2 nor T_2^{in} nor T_2^{out}.
914 num1 = 0
915 for predecessor in self.G1.pred[G1_node]:
916 if (predecessor not in self.in_1) and (predecessor not in self.out_1):
917 num1 += 1
918 num2 = 0
919 for predecessor in self.G2.pred[G2_node]:
920 if (predecessor not in self.in_2) and (predecessor not in self.out_2):
921 num2 += 1
922 if self.test == "graph":
923 if num1 != num2:
924 return False
925 else: # self.test == 'subgraph'
926 if not (num1 >= num2):
927 return False
929 # The number of successors of n that are neither in the core_1 nor
930 # T_1^{in} nor T_1^{out} is equal to the number of successors of m
931 # that are neither in core_2 nor T_2^{in} nor T_2^{out}.
932 num1 = 0
933 for successor in self.G1[G1_node]:
934 if (successor not in self.in_1) and (successor not in self.out_1):
935 num1 += 1
936 num2 = 0
937 for successor in self.G2[G2_node]:
938 if (successor not in self.in_2) and (successor not in self.out_2):
939 num2 += 1
940 if self.test == "graph":
941 if num1 != num2:
942 return False
943 else: # self.test == 'subgraph'
944 if not (num1 >= num2):
945 return False
947 # Otherwise, this node pair is syntactically feasible!
948 return True
950 def subgraph_is_isomorphic(self):
951 """Returns `True` if a subgraph of ``G1`` is isomorphic to ``G2``.
953 Examples
954 --------
955 When creating the `DiGraphMatcher`, the order of the arguments is important
957 >>> G = nx.DiGraph([("A", "B"), ("B", "A"), ("B", "C"), ("C", "B")])
958 >>> H = nx.DiGraph(nx.path_graph(5))
960 Check whether a subgraph of G is isomorphic to H:
962 >>> isomatcher = nx.isomorphism.DiGraphMatcher(G, H)
963 >>> isomatcher.subgraph_is_isomorphic()
964 False
966 Check whether a subgraph of H is isomorphic to G:
968 >>> isomatcher = nx.isomorphism.DiGraphMatcher(H, G)
969 >>> isomatcher.subgraph_is_isomorphic()
970 True
971 """
972 return super().subgraph_is_isomorphic()
974 def subgraph_is_monomorphic(self):
975 """Returns `True` if a subgraph of ``G1`` is monomorphic to ``G2``.
977 Examples
978 --------
979 When creating the `DiGraphMatcher`, the order of the arguments is important.
981 >>> G = nx.DiGraph([("A", "B"), ("C", "B"), ("D", "C")])
982 >>> H = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 2)])
984 Check whether a subgraph of G is monomorphic to H:
986 >>> isomatcher = nx.isomorphism.DiGraphMatcher(G, H)
987 >>> isomatcher.subgraph_is_monomorphic()
988 False
990 Check whether a subgraph of H is isomorphic to G:
992 >>> isomatcher = nx.isomorphism.DiGraphMatcher(H, G)
993 >>> isomatcher.subgraph_is_monomorphic()
994 True
995 """
996 return super().subgraph_is_monomorphic()
998 def subgraph_isomorphisms_iter(self):
999 """Generator over isomorphisms between a subgraph of ``G1`` and ``G2``.
1001 Examples
1002 --------
1003 When creating the `DiGraphMatcher`, the order of the arguments is important
1005 >>> G = nx.DiGraph([("B", "C"), ("C", "B"), ("C", "D"), ("D", "C")])
1006 >>> H = nx.DiGraph(nx.path_graph(5))
1008 Yield isomorphic mappings between ``H`` and subgraphs of ``G``:
1010 >>> isomatcher = nx.isomorphism.DiGraphMatcher(G, H)
1011 >>> list(isomatcher.subgraph_isomorphisms_iter())
1012 []
1014 Yield isomorphic mappings between ``G`` and subgraphs of ``H``:
1016 >>> isomatcher = nx.isomorphism.DiGraphMatcher(H, G)
1017 >>> next(isomatcher.subgraph_isomorphisms_iter())
1018 {0: 'B', 1: 'C', 2: 'D'}
1019 """
1020 return super().subgraph_isomorphisms_iter()
1022 def subgraph_monomorphisms_iter(self):
1023 """Generator over monomorphisms between a subgraph of ``G1`` and ``G2``.
1025 Examples
1026 --------
1027 When creating the `DiGraphMatcher`, the order of the arguments is important.
1029 >>> G = nx.DiGraph([("A", "B"), ("C", "B"), ("D", "C")])
1030 >>> H = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 2)])
1032 Yield monomorphic mappings between ``H`` and subgraphs of ``G``:
1034 >>> isomatcher = nx.isomorphism.DiGraphMatcher(G, H)
1035 >>> list(isomatcher.subgraph_monomorphisms_iter())
1036 []
1038 Yield monomorphic mappings between ``G`` and subgraphs of ``H``:
1040 >>> isomatcher = nx.isomorphism.DiGraphMatcher(H, G)
1041 >>> next(isomatcher.subgraph_monomorphisms_iter())
1042 {3: 'A', 2: 'B', 1: 'C', 0: 'D'}
1043 """
1044 return super().subgraph_monomorphisms_iter()
1047class GMState:
1048 """Internal representation of state for the GraphMatcher class.
1050 This class is used internally by the GraphMatcher class. It is used
1051 only to store state specific data. There will be at most G2.order() of
1052 these objects in memory at a time, due to the depth-first search
1053 strategy employed by the VF2 algorithm.
1054 """
1056 def __init__(self, GM, G1_node=None, G2_node=None):
1057 """Initializes GMState object.
1059 Pass in the GraphMatcher to which this GMState belongs and the
1060 new node pair that will be added to the GraphMatcher's current
1061 isomorphism mapping.
1062 """
1063 self.GM = GM
1065 # Initialize the last stored node pair.
1066 self.G1_node = None
1067 self.G2_node = None
1068 self.depth = len(GM.core_1)
1070 if G1_node is None or G2_node is None:
1071 # Then we reset the class variables
1072 GM.core_1 = {}
1073 GM.core_2 = {}
1074 GM.inout_1 = {}
1075 GM.inout_2 = {}
1077 # Watch out! G1_node == 0 should evaluate to True.
1078 if G1_node is not None and G2_node is not None:
1079 # Add the node pair to the isomorphism mapping.
1080 GM.core_1[G1_node] = G2_node
1081 GM.core_2[G2_node] = G1_node
1083 # Store the node that was added last.
1084 self.G1_node = G1_node
1085 self.G2_node = G2_node
1087 # Now we must update the other two vectors.
1088 # We will add only if it is not in there already!
1089 self.depth = len(GM.core_1)
1091 # First we add the new nodes...
1092 if G1_node not in GM.inout_1:
1093 GM.inout_1[G1_node] = self.depth
1094 if G2_node not in GM.inout_2:
1095 GM.inout_2[G2_node] = self.depth
1097 # Now we add every other node...
1099 # Updates for T_1^{inout}
1100 new_nodes = set()
1101 for node in GM.core_1:
1102 new_nodes.update(
1103 [neighbor for neighbor in GM.G1[node] if neighbor not in GM.core_1]
1104 )
1105 for node in new_nodes:
1106 if node not in GM.inout_1:
1107 GM.inout_1[node] = self.depth
1109 # Updates for T_2^{inout}
1110 new_nodes = set()
1111 for node in GM.core_2:
1112 new_nodes.update(
1113 [neighbor for neighbor in GM.G2[node] if neighbor not in GM.core_2]
1114 )
1115 for node in new_nodes:
1116 if node not in GM.inout_2:
1117 GM.inout_2[node] = self.depth
1119 def restore(self):
1120 """Deletes the GMState object and restores the class variables."""
1121 # First we remove the node that was added from the core vectors.
1122 # Watch out! G1_node == 0 should evaluate to True.
1123 if self.G1_node is not None and self.G2_node is not None:
1124 del self.GM.core_1[self.G1_node]
1125 del self.GM.core_2[self.G2_node]
1127 # Now we revert the other two vectors.
1128 # Thus, we delete all entries which have this depth level.
1129 for vector in (self.GM.inout_1, self.GM.inout_2):
1130 for node in list(vector.keys()):
1131 if vector[node] == self.depth:
1132 del vector[node]
1135class DiGMState:
1136 """Internal representation of state for the DiGraphMatcher class.
1138 This class is used internally by the DiGraphMatcher class. It is used
1139 only to store state specific data. There will be at most G2.order() of
1140 these objects in memory at a time, due to the depth-first search
1141 strategy employed by the VF2 algorithm.
1143 """
1145 def __init__(self, GM, G1_node=None, G2_node=None):
1146 """Initializes DiGMState object.
1148 Pass in the DiGraphMatcher to which this DiGMState belongs and the
1149 new node pair that will be added to the GraphMatcher's current
1150 isomorphism mapping.
1151 """
1152 self.GM = GM
1154 # Initialize the last stored node pair.
1155 self.G1_node = None
1156 self.G2_node = None
1157 self.depth = len(GM.core_1)
1159 if G1_node is None or G2_node is None:
1160 # Then we reset the class variables
1161 GM.core_1 = {}
1162 GM.core_2 = {}
1163 GM.in_1 = {}
1164 GM.in_2 = {}
1165 GM.out_1 = {}
1166 GM.out_2 = {}
1168 # Watch out! G1_node == 0 should evaluate to True.
1169 if G1_node is not None and G2_node is not None:
1170 # Add the node pair to the isomorphism mapping.
1171 GM.core_1[G1_node] = G2_node
1172 GM.core_2[G2_node] = G1_node
1174 # Store the node that was added last.
1175 self.G1_node = G1_node
1176 self.G2_node = G2_node
1178 # Now we must update the other four vectors.
1179 # We will add only if it is not in there already!
1180 self.depth = len(GM.core_1)
1182 # First we add the new nodes...
1183 for vector in (GM.in_1, GM.out_1):
1184 if G1_node not in vector:
1185 vector[G1_node] = self.depth
1186 for vector in (GM.in_2, GM.out_2):
1187 if G2_node not in vector:
1188 vector[G2_node] = self.depth
1190 # Now we add every other node...
1192 # Updates for T_1^{in}
1193 new_nodes = set()
1194 for node in GM.core_1:
1195 new_nodes.update(
1196 [
1197 predecessor
1198 for predecessor in GM.G1.predecessors(node)
1199 if predecessor not in GM.core_1
1200 ]
1201 )
1202 for node in new_nodes:
1203 if node not in GM.in_1:
1204 GM.in_1[node] = self.depth
1206 # Updates for T_2^{in}
1207 new_nodes = set()
1208 for node in GM.core_2:
1209 new_nodes.update(
1210 [
1211 predecessor
1212 for predecessor in GM.G2.predecessors(node)
1213 if predecessor not in GM.core_2
1214 ]
1215 )
1216 for node in new_nodes:
1217 if node not in GM.in_2:
1218 GM.in_2[node] = self.depth
1220 # Updates for T_1^{out}
1221 new_nodes = set()
1222 for node in GM.core_1:
1223 new_nodes.update(
1224 [
1225 successor
1226 for successor in GM.G1.successors(node)
1227 if successor not in GM.core_1
1228 ]
1229 )
1230 for node in new_nodes:
1231 if node not in GM.out_1:
1232 GM.out_1[node] = self.depth
1234 # Updates for T_2^{out}
1235 new_nodes = set()
1236 for node in GM.core_2:
1237 new_nodes.update(
1238 [
1239 successor
1240 for successor in GM.G2.successors(node)
1241 if successor not in GM.core_2
1242 ]
1243 )
1244 for node in new_nodes:
1245 if node not in GM.out_2:
1246 GM.out_2[node] = self.depth
1248 def restore(self):
1249 """Deletes the DiGMState object and restores the class variables."""
1251 # First we remove the node that was added from the core vectors.
1252 # Watch out! G1_node == 0 should evaluate to True.
1253 if self.G1_node is not None and self.G2_node is not None:
1254 del self.GM.core_1[self.G1_node]
1255 del self.GM.core_2[self.G2_node]
1257 # Now we revert the other four vectors.
1258 # Thus, we delete all entries which have this depth level.
1259 for vector in (self.GM.in_1, self.GM.in_2, self.GM.out_1, self.GM.out_2):
1260 for node in list(vector.keys()):
1261 if vector[node] == self.depth:
1262 del vector[node]