networkx.isomorphvf2

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 # 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 21 # 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, 26 # UC Davis. 27 28 import sys 29 from sets import Set 30

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. 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 """

61 - def __init__(self, G1, G2):

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 # 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)) 79 80 # Declare that we will be searching for a graph-graph isomorphism. 81 self.test = 'graph' 82 83 # Initialize the isomorphism mapping. 84 self.state = GMState(self)

85

86 - def __del__(self):

87 # Restore the recursion limit 88 sys.setrecursionlimit(self.old_recursion_limit)

89

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.""" 93 94 # All computations are done using the current state! 95 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)] 99 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) 105 106 else: 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)) 112 for node in self.G1: 113 if node not in GMState.core_1: 114 yield node, other_node

115 116 # For all other cases, we don't have any candidate pairs. 117

118 - def is_isomorphic(self):

119 """Returns True if G1 and G2 are isomorphic graphs. Otherwise, it 120 returns False.""" 121 122 # Declare that we are looking for a graph-graph isomorphism. 123 self.test = 'graph' 124 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. 128 129 # Check global properties 130 if self.G1.order() != self.G2.order(): return False 131 132 # Check local properties 133 d1=self.G1.degree() 134 d1.sort() 135 d2=self.G2.degree() 136 d2.sort() 137 if d1 != d2: return False 138 139 # Recall, self.match() will not return False. 140 # It raises an exception or returns None 141 try: 142 self.match(self.state) 143 return False 144 except StopIteration: 145 return True

146

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. 152 """ 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. 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 # Recursive call, adding the feasible state. 163 self.match(GMState(self, G1_node, G2_node))

164 # Garbage collection for GMState() will 'restore data structures'. 165

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. 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

204 - def subgraph_is_isomorphic(self):

205 """Returns True if a subgraph of G1 is isomorphic to G2. Otherwise, 206 it returns False.""" 207 208 # Declare that we are looking for graph-subgraph isomorphism. 209 self.test = 'subgraph' 210 211 # Recall, self.match() will not return False. 212 # It raises an exception or returns None 213 try: 214 self.match(self.state) 215 return False 216 except StopIteration: 217 return True

218

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. 224 """ 225 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. 229 # 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. 232 # 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. 238 239 240 241 ### 242 ### Test at each step to get a return value as soon as possible. 243 ### 244 245 246 247 ### Look ahead 0 248 249 # R_self 250 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 254 # search tree now. 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 # R_neighbor 260 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]): 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 ### Look ahead 1 278 279 # R_terminout 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. 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: # self.test == 'subgraph' 294 if not (num1 >= num2): 295 return False 296 297 298 ### Look ahead 2 299 300 # R_new 301 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}. 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: # self.test == 'subgraph' 317 if not (num1 >= num2): 318 return False 319 320 # Otherwise, this node pair is syntactically feasible! 321 return True

322 323

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. 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

357 - def __init__(self, G1, G2):

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 # 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)) 376 377 # Declare that we will be searching for a graph-graph isomorphism. 378 self.test = 'graph' 379 380 # Initialize the isomorphism mapping. 381 self.state = DiGMState(self) 382 383 # Provide a convienient was to access the isomorphism mapping. 384 self.mapping = DiGMState.core_1

385

386 - def __del__(self):

387 # Restore the recursion limit 388 sys.setrecursionlimit(self.old_recursion_limit)

389

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.""" 393 394 # All computations are done using the current state! 395 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)] 399 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: 403 node_2 = min(T2_out) 404 for node_1 in T1_out: 405 yield node_1, node_2 406 407 else: 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)] 413 414 # If T1_in and T2_in are both nonempty. 415 # P(s) = T1_out x {min T2_out} 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 # 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: 428 yield node_1, node_2

429 430 # For all other cases, we don't have any candidate pairs. 431

432 - def is_isomorphic(self):

433 """Returns True if G1 and G2 are isomorphic graphs. Otherwise, it 434 returns False.""" 435 436 # Declare that we are looking for a graph-graph isomorphism. 437 self.test = 'graph' 438 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. 442 443 # Check global properties 444 if self.G1.order() != self.G2.order(): return False 445 446 # Check local properties 447 d1=self.G1.degree() 448 d1.sort() 449 d2=self.G2.degree() 450 d2.sort() 451 if d1 != d2: return False 452 453 # Recall, self.match() will not return False. 454 # It raises an exception or returns None 455 try: 456 self.match(self.state) 457 return False 458 except StopIteration: 459 return True

460

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 467 return nothing. 468 469 """ 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. 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 # Recursive call, adding the feasible state. 480 self.match(DiGMState(self, G1_node,G2_node))

481 # Garbage collection for DiGMState() will 'restore data structures'. 482 483

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. 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

523 - def subgraph_is_isomorphic(self):

524 """Returns True if a subgraph of G1 is isomorphic to G2. Otherwise, 525 it returns False.""" 526 527 # Declare that we are looking for graph-subgraph isomorphism. 528 self.test = 'subgraph' 529 530 # Recall, self.match() will not return False. 531 # It raises an exception or returns None 532 try: 533 self.match(self.state) 534 return False 535 except StopIteration: 536 return True

537

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. 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 # 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. 554 # 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. 557 # 558 # We also have R_self, a test that performs the edge count on the 559 # candidate nodes themselves. 560 # 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. 567 568 569 570 ### 571 ### Test at each step to get a return value as soon as possible. 572 ### 573 574 575 576 ### Look ahead 0 577 578 # R_self 579 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. 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 ### 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] 594 ### vs 595 ### self.G1.predecessors_iter(G1_node) 596 597 598 # R_pred 599 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]): 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 # R_succ 619 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]): 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 ### Look ahead 1 639 640 # R_termin 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}. 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: # self.test == 'subgraph' 655 if not (num1 >= num2): 656 return False 657 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}. 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: # self.test == 'subgraph' 672 if not (num1 >= num2): 673 return False 674 675 # R_termout 676 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}. 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: # self.test == 'subgraph' 691 if not (num1 >= num2): 692 return False 693 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}. 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: # self.test == 'subgraph' 708 if not (num1 >= num2): 709 return False 710 711 ### Look ahead 2 712 713 # R_new 714 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}. 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: # self.test == 'subgraph' 730 if not (num1 >= num2): 731 return False 732 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}. 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: # self.test == 'subgraph' 748 if not (num1 >= num2): 749 return False 750 751 # Otherwise, this node pair is syntactically feasible! 752 return True

753 754

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. 760 """ 761 762 ### 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. 766 ### 767 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. 772 core_1 = {} 773 core_2 = {} 774 775 # See the paper for definitions of M_x and T_x^{y} 776 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} 779 # 780 # The value stored is the depth of the SSR tree when the node became 781 # part of the corresponding set. 782 inout_1 = {} 783 inout_2 = {} 784 # Practically, these sets simply store the nodes in the subgraph. 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 # Initialize the last stored node pair. 794 self.G1_node = None 795 self.G2_node = None 796 self.depth = len(GMState.core_1) 797 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 803 804 # Store the node that was added last. 805 self.G1_node = G1_node 806 self.G2_node = G2_node 807 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) 811 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 817 818 # Now we add every other node... 819 820 # Updates for T_1^{inout} 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 # Updates for T_2^{inout} 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

836 - def __del__(self):

837 """Deletes the GMState object and restores the class variables.""" 838 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] 844 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: 850 del vector[node]

851 852 853

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. 859 """ 860 861 ### 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. 865 ### 866 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. 871 core_1 = {} 872 core_2 = {} 873 874 # See the paper for definitions of M_x and T_x^{y} 875 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} 878 # 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} 881 # 882 # The value stored is the depth of the search tree when the node became 883 # part of the corresponding set. 884 in_1 = {} 885 in_2 = {} 886 out_1 = {} 887 out_2 = {} 888

889 - def __init__(self, DiGM, G1_node=None, G2_node=None):

890 """Initializes DiGMState object. 891 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 894 isomorphism mapping. 895 """ 896 # Initialize the last stored node pair. 897 self.G1_node = None 898 self.G2_node = None 899 self.depth = len(DiGMState.core_1) 900 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 906 907 # Store the node that was added last. 908 self.G1_node = G1_node 909 self.G2_node = G2_node 910 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) 914 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 922 923 # Now we add every other node... 924 925 # Updates for T_1^{in} 926 new_nodes = Set([]) 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 932 933 # Updates for T_2^{in} 934 new_nodes = Set([]) 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 940 941 # Updates for T_1^{out} 942 new_nodes = Set([]) 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 948 949 # Updates for T_2^{out} 950 new_nodes = Set([]) 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

956

957 - def __del__(self):

958 """Deletes the DiGMState object and restores the class variables.""" 959 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] 965 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: 971 del vector[node]

972 973

974 -def _test_suite():

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 # 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()) 990

Source Code for Module networkx.isomorphvf2