2
An implementation of VF2 algorithm for graph ismorphism testing, as seen here:
4
Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento,
5
"A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs,"
6
IEEE Transactions on Pattern Analysis and Machine Intelligence,
7
vol. 26, no. 10, pp. 1367-1372, Oct., 2004.
9
Modified to handle undirected graphs.
10
Modified to handle multiple edges.
13
__date__ = "$Date: 2007-08-21 16:49:09 -0600 (Tue, 21 Aug 2007) $"
14
__credits__ = "$Credits:$"
15
__revision__ = "$Revision: 680 $"
17
# Copyright (C) 2007 by
18
# Christopher Ellison <cellison@cse.ucdavis.edu>
19
# Distributed under the terms of the GNU Lesser General Public License
20
# http://www.gnu.org/copyleft/lesser.html
22
# This work was completed as part of the
23
# Computational Mechanics Python (CMPy) project.
24
# James P. Crutchfield, principal investigator.
25
# Center for Computational Science and Engineering and Physics Department,
31
class GraphMatcher(object):
32
"""A GraphMatcher is responsible for matching undirected graphs (Graph or
33
XGraph) in a predetermined manner. For graphs G1 and G2, this typically
34
means a check for an isomorphism between them, though other checks are also
35
possible. For example, the GraphMatcher class can check if a subgraph
36
of G1 is isomorphic to G2.
38
Matching is done via syntactic feasibility. It is also possible to check
39
for semantic feasibility. Feasibility, then, is defined as the logical AND
42
To include a semantic check, the GraphMatcher class should be subclassed,
43
and the semantic_feasibility() function should be redefined. By default,
44
the semantic feasibility function always returns True. The effect of this
45
is that semantics are not considered in the matching of G1 and G2.
47
For more information, see the docmentation for:
48
syntactic_feasibliity()
49
semantic_feasibility()
51
Suppose G1 and G2 are isomorphic graphs. Verification is as follows:
53
>>> GM = GraphMatcher(G1,G2)
54
>>> GM.is_isomorphic()
58
GM.mapping stores the isomorphism mapping.
61
def __init__(self, G1, G2):
62
"""Initialize GraphMatcher.
64
Suppose G1 and G2 are undirected graphs.
66
>>> GM = GraphMatcher(G1,G2)
68
creates a GraphMatcher which only checks for syntactic feasibility.
73
# Set recursion limit.
74
self.old_recursion_limit = sys.getrecursionlimit()
75
expected_max_recursion_level = len(self.G2)
76
if self.old_recursion_limit < 1.5 * expected_max_recursion_level:
77
# Give some breathing room.
78
sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
80
# Declare that we will be searching for a graph-graph isomorphism.
83
# Initialize the isomorphism mapping.
84
self.state = GMState(self)
87
# Restore the recursion limit
88
sys.setrecursionlimit(self.old_recursion_limit)
90
def candidate_pairs_iter(self):
91
"""This function returns an iterator over pairs to be considered
92
for inclusion in the current partial isomorphism mapping."""
94
# All computations are done using the current state!
96
# First we compute the inout-terminal sets.
97
T1_inout = [node for node in self.G1.nodes_iter() if (node in GMState.inout_1) and (node not in GMState.core_1)]
98
T2_inout = [node for node in self.G2.nodes_iter() if (node in GMState.inout_2) and (node not in GMState.core_2)]
100
# If T1_inout and T2_inout are both nonempty.
101
# P(s) = T1_inout x {min T2_inout}
102
if T1_inout and T2_inout:
103
for node in T1_inout:
104
yield node, min(T2_inout)
107
# If T1_inout and T2_inout were both empty....
108
# P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
109
if not (T1_inout or T2_inout):
110
# First we determine the candidate node for G2
111
other_node = min(Set(self.G2.nodes()) - Set(GMState.core_2))
113
if node not in GMState.core_1:
114
yield node, other_node
116
# For all other cases, we don't have any candidate pairs.
118
def is_isomorphic(self):
119
"""Returns True if G1 and G2 are isomorphic graphs. Otherwise, it
122
# Declare that we are looking for a graph-graph isomorphism.
125
# Let's do two very quick checks!
126
# QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)?
127
# For now, I just copy the code.
129
# Check global properties
130
if self.G1.order() != self.G2.order(): return False
132
# Check local properties
137
if d1 != d2: return False
139
# Recall, self.match() will not return False.
140
# It raises an exception or returns None
142
self.match(self.state)
144
except StopIteration:
147
def match(self, state):
148
"""This function is called recursively to determine if a complete
149
isomorphism can be found between G1 and G2. It cleans up the class
150
variables after each recursive call. If an isomorphism is found,
151
we raise a StopIteration and jump immediately out of the recursion.
153
if len(GMState.core_1) == len(self.G2):
154
# Save the final mapping, otherwise garbage collection deletes it.
155
self.mapping = GMState.core_1.copy()
156
# The mapping is complete.
159
for G1_node, G2_node in self.candidate_pairs_iter():
160
if self.syntactic_feasibility(G1_node, G2_node):
161
if self.semantic_feasibility(G1_node, G2_node):
162
# Recursive call, adding the feasible state.
163
self.match(GMState(self, G1_node, G2_node))
164
# Garbage collection for GMState() will 'restore data structures'.
166
def semantic_feasibility(self, G1_node, G2_node):
167
"""The semantic feasibility function should return True if it is
168
acceptable to add the candidate pair (G1_node, G2_node) to the current
169
partial isomorphism mapping. The logic should focus on semantic
170
information contained in the edge data or a formalized node class.
172
By acceptable, we mean that the subsequent mapping can still become a
173
complete isomorphism mapping. Thus, if adding the candidate pair
174
definitely makes it so that the subsequent mapping cannot become a
175
complete isomorphism mapping, then this function must return False.
177
The default semantic feasibility function always returns True. The
178
effect is that semantics are not considered in the matching of G1
181
The semantic checks might differ based on the what type of test is
182
being performed. A keyword description of the test is stored in
183
self.test. Here is a quick description of the currently implemented
187
Indicates that the graph matcher is looking for a graph-graph
190
Indicates that the graph matcher is looking for a subgraph-graph
191
isomorphism such that a subgraph of G1 is isomorphic to G2.
193
Any subclass of GraphMatcher which redefines semantic_feasibility()
194
must maintain the above form to keep the match() method functional.
195
Implementation considerations should include directed and undirected
196
graphs, as well as graphs with multiple edges.
198
As an example, if edges have weights, one feasibility function would be
199
to demand that the weight values/relationships are preserved in the
204
def subgraph_is_isomorphic(self):
205
"""Returns True if a subgraph of G1 is isomorphic to G2. Otherwise,
208
# Declare that we are looking for graph-subgraph isomorphism.
209
self.test = 'subgraph'
211
# Recall, self.match() will not return False.
212
# It raises an exception or returns None
214
self.match(self.state)
216
except StopIteration:
219
def syntactic_feasibility(self, G1_node, G2_node):
220
"""This function returns True if it is adding the candidate pair
221
to the current partial isomorphism mapping is allowable. The addition
222
is allowable if the inclusion of the candidate pair does not make it
223
impossible for an isomorphism to be found.
226
# The VF2 algorithm was designed to work with graphs having, at most,
227
# only one edge connecting any two nodes. This is not the case when
228
# dealing with an XGraph or XDiGraph that has multiedges=True.
230
# Basically, when we test the look-ahead rules R_pred and R_succ, we
231
# will make sure that the number of edges are also taken into account.
233
# When multiedges=False, the value in the innermost dictionary is a
234
# singlet. When multiedges=True, the value in the innermost dictionary
235
# is a list. However strange it may be, it is certainly possible to
236
# have graphs which are isomorphic but with only one of them having
237
# multiedges=True. Thus, we must ALWAYS perform this check.
242
### Test at each step to get a return value as soon as possible.
251
# The number of selfloops for G1_node must equal the number of
252
# self-loops for G2_node. Without this check, we would fail on
253
# R_pred at the next recursion level. But it is good to prune the
255
if self.G1.number_of_edges(G1_node,G1_node) != self.G2.number_of_edges(G2_node,G2_node):
261
# For each neighbor n' of n in the partial mapping, the corresponding
262
# node m' is a neighbor of m, and vice versa. Also, the number of
263
# edges must be equal.
264
for neighbor in self.G1.adj[G1_node]:
265
if neighbor in GMState.core_1:
266
if not (GMState.core_1[neighbor] in self.G2.adj[G2_node]):
268
elif self.G1.number_of_edges(neighbor, G1_node) != self.G2.number_of_edges(GMState.core_1[neighbor], G2_node):
270
for neighbor in self.G2.adj[G2_node]:
271
if neighbor in GMState.core_2:
272
if not (GMState.core_2[neighbor] in self.G1.adj[G1_node]):
274
elif self.G1.number_of_edges(GMState.core_2[neighbor], G1_node) != self.G2.number_of_edges(neighbor, G2_node):
280
# The number of neighbors of n that are in T_1^{inout} is equal to the
281
# number of neighbors of m that are in T_2^{inout}, and vice versa.
283
for neighbor in self.G1.adj[G1_node]:
284
if (neighbor in GMState.inout_1) and (neighbor not in GMState.core_1):
287
for neighbor in self.G2.adj[G2_node]:
288
if (neighbor in GMState.inout_2) and (neighbor not in GMState.core_2):
290
if self.test == 'graph':
291
if not (num1 == num2):
293
else: # self.test == 'subgraph'
294
if not (num1 >= num2):
302
# The number of neighbors of n that are neither in the core_1 nor
303
# T_1^{inout} is equal to the number of neighbors of m
304
# that are neither in core_2 nor T_2^{inout}.
306
for neighbor in self.G1.adj[G1_node]:
307
if neighbor not in GMState.inout_1:
310
for neighbor in self.G2.adj[G2_node]:
311
if neighbor not in GMState.inout_2:
313
if self.test == 'graph':
314
if not (num1 == num2):
316
else: # self.test == 'subgraph'
317
if not (num1 >= num2):
320
# Otherwise, this node pair is syntactically feasible!
324
class DiGraphMatcher(object):
325
"""A DiGraphMatcher is responsible for matching directed graphs (DiGraph or
326
XDiGraph) in a predetermined manner. For graphs G1 and G2, this typically
327
means a check for an isomorphism between them, though other checks are also
328
possible. For example, the DiGraphMatcher class can check if a subgraph
329
of G1 is isomorphic to G2.
331
Matching is done via syntactic feasibility. It is also possible to check
332
for semantic feasibility. Feasibility, then, is defined as the logical AND
333
of the two functions.
335
To include a semantic check, you should subclass the GraphMatcher class and
336
redefine semantic_feasibility(). By default, the semantic feasibility
337
function always returns True. The effect of this is that semantics are not
338
considered in the matching of G1 and G2.
340
For more information, see the docmentation for:
341
syntactic_feasibliity()
342
semantic_feasibility()
346
Suppose G1 and G2 are isomorphic graphs. Verfication is as follows:
348
>>> GM = GraphMatcher(G1,G2)
349
>>> GM.is_isomorphic()
353
GM.mapping stores the isomorphism mapping.
357
def __init__(self, G1, G2):
358
"""Initialize DiGraphMatcher.
360
Suppose G1 and G2 are graphs.
362
>>> GM = DiGraphMatcher(G1,G2)
364
creates a DiGraphMatcher which only checks for syntactic feasibility.
370
# Set recursion limit.
371
self.old_recursion_limit = sys.getrecursionlimit()
372
expected_max_recursion_level = len(self.G2)
373
if self.old_recursion_limit < 1.5 * expected_max_recursion_level:
374
# Give some breathing room.
375
sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
377
# Declare that we will be searching for a graph-graph isomorphism.
380
# Initialize the isomorphism mapping.
381
self.state = DiGMState(self)
383
# Provide a convienient was to access the isomorphism mapping.
384
self.mapping = DiGMState.core_1
387
# Restore the recursion limit
388
sys.setrecursionlimit(self.old_recursion_limit)
390
def candidate_pairs_iter(self):
391
"""This function returns an iterator over pairs to be considered
392
for inclusion in the current partial isomorphism mapping."""
394
# All computations are done using the current state!
396
# First we compute the out-terminal sets.
397
T1_out = [node for node in self.G1.nodes_iter() if (node in DiGMState.out_1) and (node not in DiGMState.core_1)]
398
T2_out = [node for node in self.G2.nodes_iter() if (node in DiGMState.out_2) and (node not in DiGMState.core_2)]
400
# If T1_out and T2_out are both nonempty.
401
# P(s) = T1_out x {min T2_out}
402
if T1_out and T2_out:
404
for node_1 in T1_out:
408
# If T1_out and T2_out were both empty....
409
# We compute the in-terminal sets.
410
if not (T1_out or T2_out):
411
T1_in = [node for node in self.G1.nodes_iter() if (node in DiGMState.in_1) and (node not in DiGMState.core_1)]
412
T2_in = [node for node in self.G2.nodes_iter() if (node in DiGMState.in_2) and (node not in DiGMState.core_2)]
414
# If T1_in and T2_in are both nonempty.
415
# P(s) = T1_out x {min T2_out}
421
# If all terminal sets are empty...
422
# P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
423
if not (T1_out or T2_out or T1_in or T2_in):
424
# First we determine the candidate node for G2
425
node_2 = min(Set(self.G2.nodes()) - Set(DiGMState.core_2))
426
for node_1 in self.G1:
427
if node_1 not in DiGMState.core_1:
430
# For all other cases, we don't have any candidate pairs.
432
def is_isomorphic(self):
433
"""Returns True if G1 and G2 are isomorphic graphs. Otherwise, it
436
# Declare that we are looking for a graph-graph isomorphism.
439
# Let's do two very quick checks!
440
# QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)?
441
# For now, I just copy the code.
443
# Check global properties
444
if self.G1.order() != self.G2.order(): return False
446
# Check local properties
451
if d1 != d2: return False
453
# Recall, self.match() will not return False.
454
# It raises an exception or returns None
456
self.match(self.state)
458
except StopIteration:
461
def match(self, state):
462
"""This function is called recursively to determine if a complete
463
isomorphism can be found between G1 and G2. It cleans up the class
464
variables after each recursive call. Because of this, this function
465
will not return True or False. If a mapping is found, we will jump
466
out of the recursion by throwing an exception. Otherwise, we will
470
if len(DiGMState.core_1) == len(self.G2):
471
# Save the final mapping, otherwise garbage collection deletes it.
472
self.mapping = DiGMState.core_1.copy()
473
# The mapping is complete.
476
for G1_node, G2_node in self.candidate_pairs_iter():
477
if self.syntactic_feasibility(G1_node, G2_node):
478
if self.semantic_feasibility(G1_node, G2_node):
479
# Recursive call, adding the feasible state.
480
self.match(DiGMState(self, G1_node,G2_node))
481
# Garbage collection for DiGMState() will 'restore data structures'.
484
def semantic_feasibility(self, G1_node, G2_node):
485
"""The semantic feasibility function should return True if it is
486
acceptable to add the candidate pair (G1_node, G2_node) to the current
487
partial isomorphism mapping. The logic should focus on semantic
488
information contained in the edge data or a formalized node class.
490
By acceptable, we mean that the subsequent mapping can still become a
491
complete isomorphism mapping. Thus, if adding the candidate pair
492
definitely makes it so that the subsequent mapping cannot become a
493
complete isomorphism mapping, then this function must return False.
495
The default semantic feasibility function always returns True. The
496
effect is that semantics are not considered in the matching of
499
The semantic checks might differ based on the what type of test is
500
being performed. A keyword description of the test is stored in
501
self.test. Here is a quick description of the currently implemented
505
Indicates that the graph matcher is looking for a graph-graph
508
Indicates that the graph matcher is looking for a subgraph-graph
509
isomorphism such that a subgraph of G1 is isomorphic to G2.
511
Any subclass of DiGraphMatcher which redefines semantic_feasibility()
512
must maintain the above form to keep the match() method functional.
513
Implementation considerations should include directed and undirected
514
graphs, as well as graphs with multiple edges.
516
As an example, if edges have weights, one feasibility function would be
517
to demand that the weight values/relationships are preserved in the
523
def subgraph_is_isomorphic(self):
524
"""Returns True if a subgraph of G1 is isomorphic to G2. Otherwise,
527
# Declare that we are looking for graph-subgraph isomorphism.
528
self.test = 'subgraph'
530
# Recall, self.match() will not return False.
531
# It raises an exception or returns None
533
self.match(self.state)
535
except StopIteration:
538
def syntactic_feasibility(self, G1_node, G2_node):
539
"""This function returns True if it is adding the candidate pair
540
to the current partial isomorphism mapping is allowable.
544
Checks for graph-graph isomorphism. This is the default value.
546
Checks for graph-subgraph isomorphism in such a way that
547
a subgraph of G1 might be isomorphic to G2.
551
# The VF2 algorithm was designed to work with graphs that have, at most
552
# only one edge connecting any two nodes. This is not the case when
553
# dealing with an XGraph or XDiGraph that has multiedges=True.
555
# Basically, when we test the look-ahead rules R_pred and R_succ,
556
# we will make sure that the number of edges are also considered.
558
# We also have R_self, a test that performs the edge count on the
559
# candidate nodes themselves.
561
# When multiedges=False, the value in the innermost dictionary is a
562
# singlet. When multiedges=True, the value in the innermost dictionary
563
# is a list. However strange it may be, it is certainly possible to
564
# have graphs which are isomorphic but with only one of them having
565
# multiedges=True. Thus, we must ALWAYS perform this check, and we
566
# must perform the check separately for each graph.
571
### Test at each step to get a return value as soon as possible.
580
# The number of selfloops for G1_node must equal the number of
581
# self-loops for G2_node. Without this check, we would fail on R_pred
582
# at the next recursion level. This should prune the tree even further.
584
if self.G1.number_of_edges(G1_node,G1_node) != self.G2.number_of_edges(G2_node,G2_node):
587
### predecessors_iter, successors_iter and neighbors_iter does not
588
### behave how we need it to. With multiedges, it returns the same
589
### node multiple times. The result is that we do the same check
590
### repeatedly. If NetworkX changes this behavior, we can go back to
591
### predecessors_iter (etc), but for now, we must access the underlying
592
### structure. For example,
593
### self.G1.pred[G1_node]
595
### self.G1.predecessors_iter(G1_node)
600
# For each predecessor n' of n in the partial mapping, the
601
# corresponding node m' is a predecessor of m, and vice versa. Also,
602
# the number of edges must be equal.
603
for predecessor in self.G1.pred[G1_node]:
604
if predecessor in DiGMState.core_1:
605
if not (DiGMState.core_1[predecessor] in self.G2.pred[G2_node]):
607
elif self.G1.number_of_edges(predecessor, G1_node) != self.G2.number_of_edges(DiGMState.core_1[predecessor], G2_node):
610
for predecessor in self.G2.pred[G2_node]:
611
if predecessor in DiGMState.core_2:
612
if not (DiGMState.core_2[predecessor] in self.G1.pred[G1_node]):
614
elif self.G1.number_of_edges(DiGMState.core_2[predecessor], G1_node) != self.G2.number_of_edges(predecessor, G2_node):
620
# For each successor n' of n in the partial mapping, the corresponding
621
# node m' is a successor of m, and vice versa. Also, the number of
622
# edges must be equal.
623
for successor in self.G1.succ[G1_node]:
624
if successor in DiGMState.core_1:
625
if not (DiGMState.core_1[successor] in self.G2.succ[G2_node]):
627
elif self.G1.number_of_edges(G1_node, successor) != self.G2.number_of_edges(G2_node, DiGMState.core_1[successor]):
630
for successor in self.G2.succ[G2_node]:
631
if successor in DiGMState.core_2:
632
if not (DiGMState.core_2[successor] in self.G1.succ[G1_node]):
634
elif self.G1.number_of_edges(G1_node, DiGMState.core_2[successor]) != self.G2.number_of_edges(G2_node, successor):
641
# The number of predecessors of n that are in T_1^{in} is equal to the
642
# number of predecessors of m that are in T_2^{in}.
644
for predecessor in self.G1.pred[G1_node]:
645
if (predecessor in DiGMState.in_1) and (predecessor not in DiGMState.core_1):
648
for predecessor in self.G2.pred[G2_node]:
649
if (predecessor in DiGMState.in_2) and (predecessor not in DiGMState.core_2):
651
if self.test == 'graph':
652
if not (num1 == num2):
654
else: # self.test == 'subgraph'
655
if not (num1 >= num2):
658
# The number of successors of n that are in T_1^{in} is equal to the
659
# number of successors of m that are in T_2^{in}.
661
for successor in self.G1.succ[G1_node]:
662
if (successor in DiGMState.in_1) and (successor not in DiGMState.core_1):
665
for successor in self.G2.succ[G2_node]:
666
if (successor in DiGMState.in_2) and (successor not in DiGMState.core_2):
668
if self.test == 'graph':
669
if not (num1 == num2):
671
else: # self.test == 'subgraph'
672
if not (num1 >= num2):
677
# The number of predecessors of n that are in T_1^{out} is equal to the
678
# number of predecessors of m that are in T_2^{out}.
680
for predecessor in self.G1.pred[G1_node]:
681
if (predecessor in DiGMState.out_1) and (predecessor not in DiGMState.core_1):
684
for predecessor in self.G2.pred[G2_node]:
685
if (predecessor in DiGMState.out_2) and (predecessor not in DiGMState.core_2):
687
if self.test == 'graph':
688
if not (num1 == num2):
690
else: # self.test == 'subgraph'
691
if not (num1 >= num2):
694
# The number of successors of n that are in T_1^{out} is equal to the
695
# number of successors of m that are in T_2^{out}.
697
for successor in self.G1.succ[G1_node]:
698
if (successor in DiGMState.out_1) and (successor not in DiGMState.core_1):
701
for successor in self.G2.succ[G2_node]:
702
if (successor in DiGMState.out_2) and (successor not in DiGMState.core_2):
704
if self.test == 'graph':
705
if not (num1 == num2):
707
else: # self.test == 'subgraph'
708
if not (num1 >= num2):
715
# The number of predecessors of n that are neither in the core_1 nor
716
# T_1^{in} nor T_1^{out} is equal to the number of predecessors of m
717
# that are neither in core_2 nor T_2^{in} nor T_2^{out}.
719
for predecessor in self.G1.pred[G1_node]:
720
if (predecessor not in DiGMState.in_1) and (predecessor not in DiGMState.out_1):
723
for predecessor in self.G2.pred[G2_node]:
724
if (predecessor not in DiGMState.in_2) and (predecessor not in DiGMState.out_2):
726
if self.test == 'graph':
727
if not (num1 == num2):
729
else: # self.test == 'subgraph'
730
if not (num1 >= num2):
733
# The number of successors of n that are neither in the core_1 nor
734
# T_1^{in} nor T_1^{out} is equal to the number of successors of m
735
# that are neither in core_2 nor T_2^{in} nor T_2^{out}.
737
for successor in self.G1.succ[G1_node]:
738
if (successor not in DiGMState.in_1) and (successor not in DiGMState.out_1):
741
for successor in self.G2.succ[G2_node]:
742
if (successor not in DiGMState.in_2) and (successor not in DiGMState.out_2):
744
if self.test == 'graph':
745
if not (num1 == num2):
747
else: # self.test == 'subgraph'
748
if not (num1 >= num2):
751
# Otherwise, this node pair is syntactically feasible!
755
class GMState(object):
756
"""This class is used internally by the GraphMatcher class. It is used
757
only to store state specific data. There will be at most G2.order() of
758
these objects in memory at a time, due to the depth-first search
759
strategy employed by the VF2 algorithm.
763
### The following variables are class variables.
764
### So they will be shared by all instances of the GMState class.
765
### This is the improvement of the VF2 algorithm over the VF algorithm.
768
# core_1[n] contains the index of the node paired with n, which is m,
769
# provided n is in the mapping.
770
# core_2[m] contains the index of the node paired with m, which is n,
771
# provided m is in the mapping.
775
# See the paper for definitions of M_x and T_x^{y}
777
# inout_1[n] is non-zero if n is in M_1 or in T_1^{inout}
778
# inout_2[m] is non-zero if m is in M_2 or in T_2^{inout}
780
# The value stored is the depth of the SSR tree when the node became
781
# part of the corresponding set.
784
# Practically, these sets simply store the nodes in the subgraph.
786
def __init__(self, GM, G1_node=None, G2_node=None):
787
"""Initializes GMState object.
789
Pass in the GraphMatcher to which this DiGMState belongs and the
790
new node pair that will be added to the GraphMatcher's current
793
# Initialize the last stored node pair.
796
self.depth = len(GMState.core_1)
798
# Watch out! G1_node == 0 should evaluate to True.
799
if G1_node is not None and G2_node is not None:
800
# Add the node pair to the isomorphism mapping.
801
GMState.core_1[G1_node] = G2_node
802
GMState.core_2[G2_node] = G1_node
804
# Store the node that was added last.
805
self.G1_node = G1_node
806
self.G2_node = G2_node
808
# Now we must update the other two vectors.
809
# We will add only if it is not in there already!
810
self.depth = len(GMState.core_1)
812
# First we add the new nodes...
813
if G1_node not in GMState.inout_1:
814
GMState.inout_1[G1_node] = self.depth
815
if G2_node not in GMState.inout_2:
816
GMState.inout_2[G2_node] = self.depth
818
# Now we add every other node...
820
# Updates for T_1^{inout}
822
for node in GMState.core_1:
823
new_nodes.update([neighbor for neighbor in GM.G1.neighbors(node) if neighbor not in GMState.core_1])
824
for node in new_nodes:
825
if node not in GMState.inout_1:
826
GMState.inout_1[node] = self.depth
828
# Updates for T_2^{inout}
830
for node in GMState.core_2:
831
new_nodes.update([neighbor for neighbor in GM.G2.neighbors(node) if neighbor not in GMState.core_2])
832
for node in new_nodes:
833
if node not in GMState.inout_2:
834
GMState.inout_2[node] = self.depth
837
"""Deletes the GMState object and restores the class variables."""
839
# First we remove the node that was added from the core vectors.
840
# Watch out! G1_node == 0 should evaluate to True.
841
if self.G1_node is not None and self.G2_node is not None:
842
del GMState.core_1[self.G1_node]
843
del GMState.core_2[self.G2_node]
845
# Now we revert the other two vectors.
846
# Thus, we delete all entries which have this depth level.
847
for vector in (GMState.inout_1, GMState.inout_2):
848
for node in vector.keys():
849
if vector[node] == self.depth:
854
class DiGMState(object):
855
"""This class is used internally by the DiGraphMatcher class. It is used
856
only to store state specific data. There will be at most G2.order() of
857
these objects in memory at a time, due to the depth-first search
858
strategy employed by the VF2 algorithm.
862
### The following variables are class variables.
863
### So they will be shared by all instances of the DiGMState class.
864
### This is the improvement of the VF2 algorithm over the VF algorithm.
867
# core_1[n] contains the index of the node paired with n, which is m,
868
# provided n is in the mapping.
869
# core_2[m] contains the index of the node paired with m, which is n,
870
# provided m is in the mapping.
874
# See the paper for definitions of M_x and T_x^{y}
876
# in_1[n] is non-zero if n is in M_1 or in T_1^{in}
877
# out_1[n] is non-zero if n is in M_1 or in T_1^{out}
879
# in_2[m] is non-zero if m is in M_2 or in T_2^{in}
880
# out_2[m] is non-zero if m is in M_2 or in T_2^{out}
882
# The value stored is the depth of the search tree when the node became
883
# part of the corresponding set.
889
def __init__(self, DiGM, G1_node=None, G2_node=None):
890
"""Initializes DiGMState object.
892
Pass in the DiGraphMatcher to which this DiGMState belongs and the
893
new node pair that will be added to the GraphMatcher's current
896
# Initialize the last stored node pair.
899
self.depth = len(DiGMState.core_1)
901
# Watch out! G1_node == 0 should evaluate to True.
902
if G1_node is not None and G2_node is not None:
903
# Add the node pair to the isomorphism mapping.
904
DiGMState.core_1[G1_node] = G2_node
905
DiGMState.core_2[G2_node] = G1_node
907
# Store the node that was added last.
908
self.G1_node = G1_node
909
self.G2_node = G2_node
911
# Now we must update the other four vectors.
912
# We will add only if it is not in there already!
913
self.depth = len(DiGMState.core_1)
915
# First we add the new nodes...
916
for vector in (DiGMState.in_1, DiGMState.out_1):
917
if G1_node not in vector:
918
vector[G1_node] = self.depth
919
for vector in (DiGMState.in_2, DiGMState.out_2):
920
if G2_node not in vector:
921
vector[G2_node] = self.depth
923
# Now we add every other node...
925
# Updates for T_1^{in}
927
for node in DiGMState.core_1:
928
new_nodes.update([predecessor for predecessor in DiGM.G1.predecessors(node) if predecessor not in DiGMState.core_1])
929
for node in new_nodes:
930
if node not in DiGMState.in_1:
931
DiGMState.in_1[node] = self.depth
933
# Updates for T_2^{in}
935
for node in DiGMState.core_2:
936
new_nodes.update([predecessor for predecessor in DiGM.G2.predecessors(node) if predecessor not in DiGMState.core_2])
937
for node in new_nodes:
938
if node not in DiGMState.in_2:
939
DiGMState.in_2[node] = self.depth
941
# Updates for T_1^{out}
943
for node in DiGMState.core_1:
944
new_nodes.update([successor for successor in DiGM.G1.successors(node) if successor not in DiGMState.core_1])
945
for node in new_nodes:
946
if node not in DiGMState.out_1:
947
DiGMState.out_1[node] = self.depth
949
# Updates for T_2^{out}
951
for node in DiGMState.core_2:
952
new_nodes.update([successor for successor in DiGM.G2.successors(node) if successor not in DiGMState.core_2])
953
for node in new_nodes:
954
if node not in DiGMState.out_2:
955
DiGMState.out_2[node] = self.depth
958
"""Deletes the DiGMState object and restores the class variables."""
960
# First we remove the node that was added from the core vectors.
961
# Watch out! G1_node == 0 should evaluate to True.
962
if self.G1_node is not None and self.G2_node is not None:
963
del DiGMState.core_1[self.G1_node]
964
del DiGMState.core_2[self.G2_node]
966
# Now we revert the other four vectors.
967
# Thus, we delete all entries which have this depth level.
968
for vector in (DiGMState.in_1, DiGMState.in_2, DiGMState.out_1, DiGMState.out_2):
969
for node in vector.keys():
970
if vector[node] == self.depth:
976
suite = doctest.DocFileSuite('tests/isomorphvf2.txt',package='networkx')
979
if __name__ == "__main__":
983
if sys.version_info[:2] < (2, 4):
984
print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
986
# directory of networkx package (relative to this)
987
nxbase=sys.path[0]+os.sep+os.pardir
988
sys.path.insert(0,nxbase) # prepend to search path
989
unittest.TextTestRunner().run(_test_suite())
added
removed
networkx/isomorphvf2.py
