1 """
2 An implementation of VF2 algorithm for graph ismorphism testing, as seen here:
3
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.
8
9 Modified to handle undirected graphs.
10 Modified to handle multiple edges.
11 """
12
13 __date__ = "$Date: 2007-08-21 16:49:09 -0600 (Tue, 21 Aug 2007) $"
14 __credits__ = "$Credits:$"
15 __revision__ = "$Revision: 680 $"
16
17
18
19
20
21
22
23
24
25
26
27
28 import sys
29 from sets import Set
30
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.
37
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
40 of the two functions.
41
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.
46
47 For more information, see the docmentation for:
48 syntactic_feasibliity()
49 semantic_feasibility()
50
51 Suppose G1 and G2 are isomorphic graphs. Verification is as follows:
52
53 >>> GM = GraphMatcher(G1,G2)
54 >>> GM.is_isomorphic()
55 True
56 >>> GM.mapping
57
58 GM.mapping stores the isomorphism mapping.
59
60 """
62 """Initialize GraphMatcher.
63
64 Suppose G1 and G2 are undirected graphs.
65
66 >>> GM = GraphMatcher(G1,G2)
67
68 creates a GraphMatcher which only checks for syntactic feasibility.
69 """
70 self.G1 = G1
71 self.G2 = G2
72
73
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
78 sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
79
80
81 self.test = 'graph'
82
83
84 self.state = GMState(self)
85
87
88 sys.setrecursionlimit(self.old_recursion_limit)
89
91 """This function returns an iterator over pairs to be considered
92 for inclusion in the current partial isomorphism mapping."""
93
94
95
96
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)]
99
100
101
102 if T1_inout and T2_inout:
103 for node in T1_inout:
104 yield node, min(T2_inout)
105
106 else:
107
108
109 if not (T1_inout or T2_inout):
110
111 other_node = min(Set(self.G2.nodes()) - Set(GMState.core_2))
112 for node in self.G1:
113 if node not in GMState.core_1:
114 yield node, other_node
115
116
117
119 """Returns True if G1 and G2 are isomorphic graphs. Otherwise, it
120 returns False."""
121
122
123 self.test = 'graph'
124
125
126
127
128
129
130 if self.G1.order() != self.G2.order(): return False
131
132
133 d1=self.G1.degree()
134 d1.sort()
135 d2=self.G2.degree()
136 d2.sort()
137 if d1 != d2: return False
138
139
140
141 try:
142 self.match(self.state)
143 return False
144 except StopIteration:
145 return True
146
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.
152 """
153 if len(GMState.core_1) == len(self.G2):
154
155 self.mapping = GMState.core_1.copy()
156
157 raise StopIteration
158 else:
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
163 self.match(GMState(self, G1_node, G2_node))
164
165
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.
171
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.
176
177 The default semantic feasibility function always returns True. The
178 effect is that semantics are not considered in the matching of G1
179 and G2.
180
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
184 tests:
185
186 test='graph'
187 Indicates that the graph matcher is looking for a graph-graph
188 isomorphism.
189 test='subgraph'
190 Indicates that the graph matcher is looking for a subgraph-graph
191 isomorphism such that a subgraph of G1 is isomorphic to G2.
192
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.
197
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
200 isomorphism mapping.
201 """
202 return True
203
205 """Returns True if a subgraph of G1 is isomorphic to G2. Otherwise,
206 it returns False."""
207
208
209 self.test = 'subgraph'
210
211
212
213 try:
214 self.match(self.state)
215 return False
216 except StopIteration:
217 return True
218
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.
224 """
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255 if self.G1.number_of_edges(G1_node,G1_node) != self.G2.number_of_edges(G2_node,G2_node):
256 return False
257
258
259
260
261
262
263
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]):
267 return False
268 elif self.G1.number_of_edges(neighbor, G1_node) != self.G2.number_of_edges(GMState.core_1[neighbor], G2_node):
269 return False
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]):
273 return False
274 elif self.G1.number_of_edges(GMState.core_2[neighbor], G1_node) != self.G2.number_of_edges(neighbor, G2_node):
275 return False
276
277
278
279
280
281
282 num1 = 0
283 for neighbor in self.G1.adj[G1_node]:
284 if (neighbor in GMState.inout_1) and (neighbor not in GMState.core_1):
285 num1 += 1
286 num2 = 0
287 for neighbor in self.G2.adj[G2_node]:
288 if (neighbor in GMState.inout_2) and (neighbor not in GMState.core_2):
289 num2 += 1
290 if self.test == 'graph':
291 if not (num1 == num2):
292 return False
293 else:
294 if not (num1 >= num2):
295 return False
296
297
298
299
300
301
302
303
304
305 num1 = 0
306 for neighbor in self.G1.adj[G1_node]:
307 if neighbor not in GMState.inout_1:
308 num1 += 1
309 num2 = 0
310 for neighbor in self.G2.adj[G2_node]:
311 if neighbor not in GMState.inout_2:
312 num2 += 1
313 if self.test == 'graph':
314 if not (num1 == num2):
315 return False
316 else:
317 if not (num1 >= num2):
318 return False
319
320
321 return True
322
323
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.
330
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.
334
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.
339
340 For more information, see the docmentation for:
341 syntactic_feasibliity()
342 semantic_feasibility()
343
344
345
346 Suppose G1 and G2 are isomorphic graphs. Verfication is as follows:
347
348 >>> GM = GraphMatcher(G1,G2)
349 >>> GM.is_isomorphic()
350 True
351 >>> GM.mapping
352
353 GM.mapping stores the isomorphism mapping.
354
355 """
356
358 """Initialize DiGraphMatcher.
359
360 Suppose G1 and G2 are graphs.
361
362 >>> GM = DiGraphMatcher(G1,G2)
363
364 creates a DiGraphMatcher which only checks for syntactic feasibility.
365
366 """
367 self.G1 = G1
368 self.G2 = G2
369
370
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
375 sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
376
377
378 self.test = 'graph'
379
380
381 self.state = DiGMState(self)
382
383
384 self.mapping = DiGMState.core_1
385
387
388 sys.setrecursionlimit(self.old_recursion_limit)
389
391 """This function returns an iterator over pairs to be considered
392 for inclusion in the current partial isomorphism mapping."""
393
394
395
396
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)]
399
400
401
402 if T1_out and T2_out:
403 node_2 = min(T2_out)
404 for node_1 in T1_out:
405 yield node_1, node_2
406
407 else:
408
409
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)]
413
414
415
416 if T1_in and T2_in:
417 node_2 = min(T2_in)
418 for node_1 in T1_in:
419 yield node_1, node_2
420 else:
421
422
423 if not (T1_out or T2_out or T1_in or T2_in):
424
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:
428 yield node_1, node_2
429
430
431
433 """Returns True if G1 and G2 are isomorphic graphs. Otherwise, it
434 returns False."""
435
436
437 self.test = 'graph'
438
439
440
441
442
443
444 if self.G1.order() != self.G2.order(): return False
445
446
447 d1=self.G1.degree()
448 d1.sort()
449 d2=self.G2.degree()
450 d2.sort()
451 if d1 != d2: return False
452
453
454
455 try:
456 self.match(self.state)
457 return False
458 except StopIteration:
459 return True
460
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
467 return nothing.
468
469 """
470 if len(DiGMState.core_1) == len(self.G2):
471
472 self.mapping = DiGMState.core_1.copy()
473
474 raise StopIteration
475 else:
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
480 self.match(DiGMState(self, G1_node,G2_node))
481
482
483
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.
489
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.
494
495 The default semantic feasibility function always returns True. The
496 effect is that semantics are not considered in the matching of
497 G1 and G2.
498
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
502 tests:
503
504 test='graph'
505 Indicates that the graph matcher is looking for a graph-graph
506 isomorphism.
507 test='subgraph'
508 Indicates that the graph matcher is looking for a subgraph-graph
509 isomorphism such that a subgraph of G1 is isomorphic to G2.
510
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.
515
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
518 isomorphism mapping.
519
520 """
521 return True
522
524 """Returns True if a subgraph of G1 is isomorphic to G2. Otherwise,
525 it returns False."""
526
527
528 self.test = 'subgraph'
529
530
531
532 try:
533 self.match(self.state)
534 return False
535 except StopIteration:
536 return True
537
539 """This function returns True if it is adding the candidate pair
540 to the current partial isomorphism mapping is allowable.
541
542 Keywords:
543 test='graph'
544 Checks for graph-graph isomorphism. This is the default value.
545 test='subgraph'
546 Checks for graph-subgraph isomorphism in such a way that
547 a subgraph of G1 might be isomorphic to G2.
548
549 """
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584 if self.G1.number_of_edges(G1_node,G1_node) != self.G2.number_of_edges(G2_node,G2_node):
585 return False
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
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]):
606 return False
607 elif self.G1.number_of_edges(predecessor, G1_node) != self.G2.number_of_edges(DiGMState.core_1[predecessor], G2_node):
608 return False
609
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]):
613 return False
614 elif self.G1.number_of_edges(DiGMState.core_2[predecessor], G1_node) != self.G2.number_of_edges(predecessor, G2_node):
615 return False
616
617
618
619
620
621
622
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]):
626 return False
627 elif self.G1.number_of_edges(G1_node, successor) != self.G2.number_of_edges(G2_node, DiGMState.core_1[successor]):
628 return False
629
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]):
633 return False
634 elif self.G1.number_of_edges(G1_node, DiGMState.core_2[successor]) != self.G2.number_of_edges(G2_node, successor):
635 return False
636
637
638
639
640
641
642
643 num1 = 0
644 for predecessor in self.G1.pred[G1_node]:
645 if (predecessor in DiGMState.in_1) and (predecessor not in DiGMState.core_1):
646 num1 += 1
647 num2 = 0
648 for predecessor in self.G2.pred[G2_node]:
649 if (predecessor in DiGMState.in_2) and (predecessor not in DiGMState.core_2):
650 num2 += 1
651 if self.test == 'graph':
652 if not (num1 == num2):
653 return False
654 else:
655 if not (num1 >= num2):
656 return False
657
658
659
660 num1 = 0
661 for successor in self.G1.succ[G1_node]:
662 if (successor in DiGMState.in_1) and (successor not in DiGMState.core_1):
663 num1 += 1
664 num2 = 0
665 for successor in self.G2.succ[G2_node]:
666 if (successor in DiGMState.in_2) and (successor not in DiGMState.core_2):
667 num2 += 1
668 if self.test == 'graph':
669 if not (num1 == num2):
670 return False
671 else:
672 if not (num1 >= num2):
673 return False
674
675
676
677
678
679 num1 = 0
680 for predecessor in self.G1.pred[G1_node]:
681 if (predecessor in DiGMState.out_1) and (predecessor not in DiGMState.core_1):
682 num1 += 1
683 num2 = 0
684 for predecessor in self.G2.pred[G2_node]:
685 if (predecessor in DiGMState.out_2) and (predecessor not in DiGMState.core_2):
686 num2 += 1
687 if self.test == 'graph':
688 if not (num1 == num2):
689 return False
690 else:
691 if not (num1 >= num2):
692 return False
693
694
695
696 num1 = 0
697 for successor in self.G1.succ[G1_node]:
698 if (successor in DiGMState.out_1) and (successor not in DiGMState.core_1):
699 num1 += 1
700 num2 = 0
701 for successor in self.G2.succ[G2_node]:
702 if (successor in DiGMState.out_2) and (successor not in DiGMState.core_2):
703 num2 += 1
704 if self.test == 'graph':
705 if not (num1 == num2):
706 return False
707 else:
708 if not (num1 >= num2):
709 return False
710
711
712
713
714
715
716
717
718 num1 = 0
719 for predecessor in self.G1.pred[G1_node]:
720 if (predecessor not in DiGMState.in_1) and (predecessor not in DiGMState.out_1):
721 num1 += 1
722 num2 = 0
723 for predecessor in self.G2.pred[G2_node]:
724 if (predecessor not in DiGMState.in_2) and (predecessor not in DiGMState.out_2):
725 num2 += 1
726 if self.test == 'graph':
727 if not (num1 == num2):
728 return False
729 else:
730 if not (num1 >= num2):
731 return False
732
733
734
735
736 num1 = 0
737 for successor in self.G1.succ[G1_node]:
738 if (successor not in DiGMState.in_1) and (successor not in DiGMState.out_1):
739 num1 += 1
740 num2 = 0
741 for successor in self.G2.succ[G2_node]:
742 if (successor not in DiGMState.in_2) and (successor not in DiGMState.out_2):
743 num2 += 1
744 if self.test == 'graph':
745 if not (num1 == num2):
746 return False
747 else:
748 if not (num1 >= num2):
749 return False
750
751
752 return True
753
754
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.
760 """
761
762
763
764
765
766
767
768
769
770
771
772 core_1 = {}
773 core_2 = {}
774
775
776
777
778
779
780
781
782 inout_1 = {}
783 inout_2 = {}
784
785
786 - def __init__(self, GM, G1_node=None, G2_node=None):
787 """Initializes GMState object.
788
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
791 isomorphism mapping.
792 """
793
794 self.G1_node = None
795 self.G2_node = None
796 self.depth = len(GMState.core_1)
797
798
799 if G1_node is not None and G2_node is not None:
800
801 GMState.core_1[G1_node] = G2_node
802 GMState.core_2[G2_node] = G1_node
803
804
805 self.G1_node = G1_node
806 self.G2_node = G2_node
807
808
809
810 self.depth = len(GMState.core_1)
811
812
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
817
818
819
820
821 new_nodes = Set([])
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
827
828
829 new_nodes = Set([])
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
835
837 """Deletes the GMState object and restores the class variables."""
838
839
840
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]
844
845
846
847 for vector in (GMState.inout_1, GMState.inout_2):
848 for node in vector.keys():
849 if vector[node] == self.depth:
850 del vector[node]
851
852
853
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.
859 """
860
861
862
863
864
865
866
867
868
869
870
871 core_1 = {}
872 core_2 = {}
873
874
875
876
877
878
879
880
881
882
883
884 in_1 = {}
885 in_2 = {}
886 out_1 = {}
887 out_2 = {}
888
889 - def __init__(self, DiGM, G1_node=None, G2_node=None):
956
972
973
975 import doctest
976 suite = doctest.DocFileSuite('tests/isomorphvf2.txt',package='networkx')
977 return suite
978
979 if __name__ == "__main__":
980 import os
981 import sys
982 import unittest
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]
985 sys.exit(-1)
986
987 nxbase=sys.path[0]+os.sep+os.pardir
988 sys.path.insert(0,nxbase)
989 unittest.TextTestRunner().run(_test_suite())
990