Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/isomorphism/isomorphvf2.py: 7%

1""" 

2************* 

3VF2 Algorithm 

4************* 

5 

6An implementation of VF2 algorithm for graph isomorphism testing. 

7 

8The simplest interface to use this module is to call networkx.is_isomorphic(). 

9 

10Introduction 

11------------ 

12 

13The GraphMatcher and DiGraphMatcher are responsible for matching 

14graphs or directed graphs in a predetermined manner. This 

15usually means a check for an isomorphism, though other checks 

16are also possible. For example, a subgraph of one graph 

17can be checked for isomorphism to a second graph. 

18 

19Matching is done via syntactic feasibility. It is also possible 

20to check for semantic feasibility. Feasibility, then, is defined 

21as the logical AND of the two functions. 

22 

23To include a semantic check, the (Di)GraphMatcher class should be 

24subclassed, and the semantic_feasibility() function should be 

25redefined. By default, the semantic feasibility function always 

26returns True. The effect of this is that semantics are not 

27considered in the matching of G1 and G2. 

28 

29Examples 

30-------- 

31 

32Suppose G1 and G2 are isomorphic graphs. Verification is as follows: 

33 

34>>> from networkx.algorithms import isomorphism 

35>>> G1 = nx.path_graph(4) 

36>>> G2 = nx.path_graph(4) 

37>>> GM = isomorphism.GraphMatcher(G1, G2) 

38>>> GM.is_isomorphic() 

39True 

40 

41GM.mapping stores the isomorphism mapping from G1 to G2. 

42 

43>>> GM.mapping 

44{0: 0, 1: 1, 2: 2, 3: 3} 

45 

46 

47Suppose G1 and G2 are isomorphic directed graphs. 

48Verification is as follows: 

49 

50>>> G1 = nx.path_graph(4, create_using=nx.DiGraph()) 

51>>> G2 = nx.path_graph(4, create_using=nx.DiGraph()) 

52>>> DiGM = isomorphism.DiGraphMatcher(G1, G2) 

53>>> DiGM.is_isomorphic() 

54True 

55 

56DiGM.mapping stores the isomorphism mapping from G1 to G2. 

57 

58>>> DiGM.mapping 

59{0: 0, 1: 1, 2: 2, 3: 3} 

60 

61 

62 

63Subgraph Isomorphism 

64-------------------- 

65Graph theory literature can be ambiguous about the meaning of the 

66above statement, and we seek to clarify it now. 

67 

68In the VF2 literature, a mapping M is said to be a graph-subgraph 

69isomorphism iff M is an isomorphism between G2 and a subgraph of G1. 

70Thus, to say that G1 and G2 are graph-subgraph isomorphic is to say 

71that a subgraph of G1 is isomorphic to G2. 

72 

73Other literature uses the phrase 'subgraph isomorphic' as in 'G1 does 

74not have a subgraph isomorphic to G2'. Another use is as an in adverb 

75for isomorphic. Thus, to say that G1 and G2 are subgraph isomorphic 

76is to say that a subgraph of G1 is isomorphic to G2. 

77 

78Finally, the term 'subgraph' can have multiple meanings. In this 

79context, 'subgraph' always means a 'node-induced subgraph'. Edge-induced 

80subgraph isomorphisms are not directly supported, but one should be 

81able to perform the check by making use of nx.line_graph(). For 

82subgraphs which are not induced, the term 'monomorphism' is preferred 

83over 'isomorphism'. 

84 

85Let G=(N,E) be a graph with a set of nodes N and set of edges E. 

86 

87If G'=(N',E') is a subgraph, then: 

88 N' is a subset of N 

89 E' is a subset of E 

90 

91If G'=(N',E') is a node-induced subgraph, then: 

92 N' is a subset of N 

93 E' is the subset of edges in E relating nodes in N' 

94 

95If G'=(N',E') is an edge-induced subgraph, then: 

96 N' is the subset of nodes in N related by edges in E' 

97 E' is a subset of E 

98 

99If G'=(N',E') is a monomorphism, then: 

100 N' is a subset of N 

101 E' is a subset of the set of edges in E relating nodes in N' 

102 

103Note that if G' is a node-induced subgraph of G, then it is always a 

104subgraph monomorphism of G, but the opposite is not always true, as a 

105monomorphism can have fewer edges. 

106 

107References 

108---------- 

109[1] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento, 

110 "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs", 

111 IEEE Transactions on Pattern Analysis and Machine Intelligence, 

112 vol. 26, no. 10, pp. 1367-1372, Oct., 2004. 

113 http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf 

114 

115[2] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, "An Improved 

116 Algorithm for Matching Large Graphs", 3rd IAPR-TC15 Workshop 

117 on Graph-based Representations in Pattern Recognition, Cuen, 

118 pp. 149-159, 2001. 

119 https://www.researchgate.net/publication/200034365_An_Improved_Algorithm_for_Matching_Large_Graphs 

120 

121See Also 

122-------- 

123syntactic_feasibility(), semantic_feasibility() 

124 

125Notes 

126----- 

127 

128The implementation handles both directed and undirected graphs as well 

129as multigraphs. 

130 

131In general, the subgraph isomorphism problem is NP-complete whereas the 

132graph isomorphism problem is most likely not NP-complete (although no 

133polynomial-time algorithm is known to exist). 

134 

135""" 

136 

137# This work was originally coded by Christopher Ellison 

138# as part of the Computational Mechanics Python (CMPy) project. 

139# James P. Crutchfield, principal investigator. 

140# Complexity Sciences Center and Physics Department, UC Davis. 

141 

142import sys 

143 

144__all__ = ["GraphMatcher", "DiGraphMatcher"] 

145 

146 

147class GraphMatcher: 

148 """Implementation of VF2 algorithm for matching undirected graphs. 

149 

150 Suitable for Graph and MultiGraph instances. 

151 """ 

152 

153 def __init__(self, G1, G2): 

154 """Initialize GraphMatcher. 

155 

156 Parameters 

157 ---------- 

158 G1,G2: NetworkX Graph or MultiGraph instances. 

159 The two graphs to check for isomorphism or monomorphism. 

160 

161 Examples 

162 -------- 

163 To create a GraphMatcher which checks for syntactic feasibility: 

164 

165 >>> from networkx.algorithms import isomorphism 

166 >>> G1 = nx.path_graph(4) 

167 >>> G2 = nx.path_graph(4) 

168 >>> GM = isomorphism.GraphMatcher(G1, G2) 

169 """ 

170 self.G1 = G1 

171 self.G2 = G2 

172 self.G1_nodes = set(G1.nodes()) 

173 self.G2_nodes = set(G2.nodes()) 

174 self.G2_node_order = {n: i for i, n in enumerate(G2)} 

175 

176 # Set recursion limit. 

177 self.old_recursion_limit = sys.getrecursionlimit() 

178 expected_max_recursion_level = len(self.G2) 

179 if self.old_recursion_limit < 1.5 * expected_max_recursion_level: 

180 # Give some breathing room. 

181 sys.setrecursionlimit(int(1.5 * expected_max_recursion_level)) 

182 

183 # Declare that we will be searching for a graph-graph isomorphism. 

184 self.test = "graph" 

185 

186 # Initialize state 

187 self.initialize() 

188 

189 def reset_recursion_limit(self): 

190 """Restores the recursion limit.""" 

191 # TODO: 

192 # Currently, we use recursion and set the recursion level higher. 

193 # It would be nice to restore the level, but because the 

194 # (Di)GraphMatcher classes make use of cyclic references, garbage 

195 # collection will never happen when we define __del__() to 

196 # restore the recursion level. The result is a memory leak. 

197 # So for now, we do not automatically restore the recursion level, 

198 # and instead provide a method to do this manually. Eventually, 

199 # we should turn this into a non-recursive implementation. 

200 sys.setrecursionlimit(self.old_recursion_limit) 

201 

202 def candidate_pairs_iter(self): 

203 """Iterator over candidate pairs of nodes in G1 and G2.""" 

204 

205 # All computations are done using the current state! 

206 

207 G1_nodes = self.G1_nodes 

208 G2_nodes = self.G2_nodes 

209 min_key = self.G2_node_order.__getitem__ 

210 

211 # First we compute the inout-terminal sets. 

212 T1_inout = [node for node in self.inout_1 if node not in self.core_1] 

213 T2_inout = [node for node in self.inout_2 if node not in self.core_2] 

214 

215 # If T1_inout and T2_inout are both nonempty. 

216 # P(s) = T1_inout x {min T2_inout} 

217 if T1_inout and T2_inout: 

218 node_2 = min(T2_inout, key=min_key) 

219 for node_1 in T1_inout: 

220 yield node_1, node_2 

221 

222 else: 

223 # If T1_inout and T2_inout were both empty.... 

224 # P(s) = (N_1 - M_1) x {min (N_2 - M_2)} 

225 # if not (T1_inout or T2_inout): # as suggested by [2], incorrect 

226 if 1: # as inferred from [1], correct 

227 # First we determine the candidate node for G2 

228 other_node = min(G2_nodes - set(self.core_2), key=min_key) 

229 for node in self.G1: 

230 if node not in self.core_1: 

231 yield node, other_node 

232 

233 # For all other cases, we don't have any candidate pairs. 

234 

235 def initialize(self): 

236 """Reinitializes the state of the algorithm. 

237 

238 This method should be redefined if using something other than GMState. 

239 If only subclassing GraphMatcher, a redefinition is not necessary. 

240 

241 """ 

242 

243 # core_1[n] contains the index of the node paired with n, which is m, 

244 # provided n is in the mapping. 

245 # core_2[m] contains the index of the node paired with m, which is n, 

246 # provided m is in the mapping. 

247 self.core_1 = {} 

248 self.core_2 = {} 

249 

250 # See the paper for definitions of M_x and T_x^{y} 

251 

252 # inout_1[n] is non-zero if n is in M_1 or in T_1^{inout} 

253 # inout_2[m] is non-zero if m is in M_2 or in T_2^{inout} 

254 # 

255 # The value stored is the depth of the SSR tree when the node became 

256 # part of the corresponding set. 

257 self.inout_1 = {} 

258 self.inout_2 = {} 

259 # Practically, these sets simply store the nodes in the subgraph. 

260 

261 self.state = GMState(self) 

262 

263 # Provide a convenient way to access the isomorphism mapping. 

264 self.mapping = self.core_1.copy() 

265 

266 def is_isomorphic(self): 

267 """Returns True if G1 and G2 are isomorphic graphs.""" 

268 

269 # Let's do two very quick checks! 

270 # QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)? 

271 # For now, I just copy the code. 

272 

273 # Check global properties 

274 if self.G1.order() != self.G2.order(): 

275 return False 

276 

277 # Check local properties 

278 d1 = sorted(d for n, d in self.G1.degree()) 

279 d2 = sorted(d for n, d in self.G2.degree()) 

280 if d1 != d2: 

281 return False 

282 

283 try: 

284 x = next(self.isomorphisms_iter()) 

285 return True 

286 except StopIteration: 

287 return False 

288 

289 def isomorphisms_iter(self): 

290 """Generator over isomorphisms between G1 and G2.""" 

291 # Declare that we are looking for a graph-graph isomorphism. 

292 self.test = "graph" 

293 self.initialize() 

294 yield from self.match() 

295 

296 def match(self): 

297 """Extends the isomorphism mapping. 

298 

299 This function is called recursively to determine if a complete 

300 isomorphism can be found between G1 and G2. It cleans up the class 

301 variables after each recursive call. If an isomorphism is found, 

302 we yield the mapping. 

303 

304 """ 

305 if len(self.core_1) == len(self.G2): 

306 # Save the final mapping, otherwise garbage collection deletes it. 

307 self.mapping = self.core_1.copy() 

308 # The mapping is complete. 

309 yield self.mapping 

310 else: 

311 for G1_node, G2_node in self.candidate_pairs_iter(): 

312 if self.syntactic_feasibility(G1_node, G2_node): 

313 if self.semantic_feasibility(G1_node, G2_node): 

314 # Recursive call, adding the feasible state. 

315 newstate = self.state.__class__(self, G1_node, G2_node) 

316 yield from self.match() 

317 

318 # restore data structures 

319 newstate.restore() 

320 

321 def semantic_feasibility(self, G1_node, G2_node): 

322 """Returns True if adding (G1_node, G2_node) is semantically feasible. 

323 

324 The semantic feasibility function should return True if it is 

325 acceptable to add the candidate pair (G1_node, G2_node) to the current 

326 partial isomorphism mapping. The logic should focus on semantic 

327 information contained in the edge data or a formalized node class. 

328 

329 By acceptable, we mean that the subsequent mapping can still become a 

330 complete isomorphism mapping. Thus, if adding the candidate pair 

331 definitely makes it so that the subsequent mapping cannot become a 

332 complete isomorphism mapping, then this function must return False. 

333 

334 The default semantic feasibility function always returns True. The 

335 effect is that semantics are not considered in the matching of G1 

336 and G2. 

337 

338 The semantic checks might differ based on the what type of test is 

339 being performed. A keyword description of the test is stored in 

340 self.test. Here is a quick description of the currently implemented 

341 tests:: 

342 

343 test='graph' 

344 Indicates that the graph matcher is looking for a graph-graph 

345 isomorphism. 

346 

347 test='subgraph' 

348 Indicates that the graph matcher is looking for a subgraph-graph 

349 isomorphism such that a subgraph of G1 is isomorphic to G2. 

350 

351 test='mono' 

352 Indicates that the graph matcher is looking for a subgraph-graph 

353 monomorphism such that a subgraph of G1 is monomorphic to G2. 

354 

355 Any subclass which redefines semantic_feasibility() must maintain 

356 the above form to keep the match() method functional. Implementations 

357 should consider multigraphs. 

358 """ 

359 return True 

360 

361 def subgraph_is_isomorphic(self): 

362 """Returns True if a subgraph of G1 is isomorphic to G2.""" 

363 try: 

364 x = next(self.subgraph_isomorphisms_iter()) 

365 return True 

366 except StopIteration: 

367 return False 

368 

369 def subgraph_is_monomorphic(self): 

370 """Returns True if a subgraph of G1 is monomorphic to G2.""" 

371 try: 

372 x = next(self.subgraph_monomorphisms_iter()) 

373 return True 

374 except StopIteration: 

375 return False 

376 

377 # subgraph_is_isomorphic.__doc__ += "\n" + subgraph.replace('\n','\n'+indent) 

378 

379 def subgraph_isomorphisms_iter(self): 

380 """Generator over isomorphisms between a subgraph of G1 and G2.""" 

381 # Declare that we are looking for graph-subgraph isomorphism. 

382 self.test = "subgraph" 

383 self.initialize() 

384 yield from self.match() 

385 

386 def subgraph_monomorphisms_iter(self): 

387 """Generator over monomorphisms between a subgraph of G1 and G2.""" 

388 # Declare that we are looking for graph-subgraph monomorphism. 

389 self.test = "mono" 

390 self.initialize() 

391 yield from self.match() 

392 

393 # subgraph_isomorphisms_iter.__doc__ += "\n" + subgraph.replace('\n','\n'+indent) 

394 

395 def syntactic_feasibility(self, G1_node, G2_node): 

396 """Returns True if adding (G1_node, G2_node) is syntactically feasible. 

397 

398 This function returns True if it is adding the candidate pair 

399 to the current partial isomorphism/monomorphism mapping is allowable. 

400 The addition is allowable if the inclusion of the candidate pair does 

401 not make it impossible for an isomorphism/monomorphism to be found. 

402 """ 

403 

404 # The VF2 algorithm was designed to work with graphs having, at most, 

405 # one edge connecting any two nodes. This is not the case when 

406 # dealing with an MultiGraphs. 

407 # 

408 # Basically, when we test the look-ahead rules R_neighbor, we will 

409 # make sure that the number of edges are checked. We also add 

410 # a R_self check to verify that the number of selfloops is acceptable. 

411 # 

412 # Users might be comparing Graph instances with MultiGraph instances. 

413 # So the generic GraphMatcher class must work with MultiGraphs. 

414 # Care must be taken since the value in the innermost dictionary is a 

415 # singlet for Graph instances. For MultiGraphs, the value in the 

416 # innermost dictionary is a list. 

417 

418 ### 

419 # Test at each step to get a return value as soon as possible. 

420 ### 

421 

422 # Look ahead 0 

423 

424 # R_self 

425 

426 # The number of selfloops for G1_node must equal the number of 

427 # self-loops for G2_node. Without this check, we would fail on 

428 # R_neighbor at the next recursion level. But it is good to prune the 

429 # search tree now. 

430 

431 if self.test == "mono": 

432 if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges( 

433 G2_node, G2_node 

434 ): 

435 return False 

436 else: 

437 if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges( 

438 G2_node, G2_node 

439 ): 

440 return False 

441 

442 # R_neighbor 

443 

444 # For each neighbor n' of n in the partial mapping, the corresponding 

445 # node m' is a neighbor of m, and vice versa. Also, the number of 

446 # edges must be equal. 

447 if self.test != "mono": 

448 for neighbor in self.G1[G1_node]: 

449 if neighbor in self.core_1: 

450 if self.core_1[neighbor] not in self.G2[G2_node]: 

451 return False 

452 elif self.G1.number_of_edges( 

453 neighbor, G1_node 

454 ) != self.G2.number_of_edges(self.core_1[neighbor], G2_node): 

455 return False 

456 

457 for neighbor in self.G2[G2_node]: 

458 if neighbor in self.core_2: 

459 if self.core_2[neighbor] not in self.G1[G1_node]: 

460 return False 

461 elif self.test == "mono": 

462 if self.G1.number_of_edges( 

463 self.core_2[neighbor], G1_node 

464 ) < self.G2.number_of_edges(neighbor, G2_node): 

465 return False 

466 else: 

467 if self.G1.number_of_edges( 

468 self.core_2[neighbor], G1_node 

469 ) != self.G2.number_of_edges(neighbor, G2_node): 

470 return False 

471 

472 if self.test != "mono": 

473 # Look ahead 1 

474 

475 # R_terminout 

476 # The number of neighbors of n in T_1^{inout} is equal to the 

477 # number of neighbors of m that are in T_2^{inout}, and vice versa. 

478 num1 = 0 

479 for neighbor in self.G1[G1_node]: 

480 if (neighbor in self.inout_1) and (neighbor not in self.core_1): 

481 num1 += 1 

482 num2 = 0 

483 for neighbor in self.G2[G2_node]: 

484 if (neighbor in self.inout_2) and (neighbor not in self.core_2): 

485 num2 += 1 

486 if self.test == "graph": 

487 if num1 != num2: 

488 return False 

489 else: # self.test == 'subgraph' 

490 if not (num1 >= num2): 

491 return False 

492 

493 # Look ahead 2 

494 

495 # R_new 

496 

497 # The number of neighbors of n that are neither in the core_1 nor 

498 # T_1^{inout} is equal to the number of neighbors of m 

499 # that are neither in core_2 nor T_2^{inout}. 

500 num1 = 0 

501 for neighbor in self.G1[G1_node]: 

502 if neighbor not in self.inout_1: 

503 num1 += 1 

504 num2 = 0 

505 for neighbor in self.G2[G2_node]: 

506 if neighbor not in self.inout_2: 

507 num2 += 1 

508 if self.test == "graph": 

509 if num1 != num2: 

510 return False 

511 else: # self.test == 'subgraph' 

512 if not (num1 >= num2): 

513 return False 

514 

515 # Otherwise, this node pair is syntactically feasible! 

516 return True 

517 

518 

519class DiGraphMatcher(GraphMatcher): 

520 """Implementation of VF2 algorithm for matching directed graphs. 

521 

522 Suitable for DiGraph and MultiDiGraph instances. 

523 """ 

524 

525 def __init__(self, G1, G2): 

526 """Initialize DiGraphMatcher. 

527 

528 G1 and G2 should be nx.Graph or nx.MultiGraph instances. 

529 

530 Examples 

531 -------- 

532 To create a GraphMatcher which checks for syntactic feasibility: 

533 

534 >>> from networkx.algorithms import isomorphism 

535 >>> G1 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph())) 

536 >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph())) 

537 >>> DiGM = isomorphism.DiGraphMatcher(G1, G2) 

538 """ 

539 super().__init__(G1, G2) 

540 

541 def candidate_pairs_iter(self): 

542 """Iterator over candidate pairs of nodes in G1 and G2.""" 

543 

544 # All computations are done using the current state! 

545 

546 G1_nodes = self.G1_nodes 

547 G2_nodes = self.G2_nodes 

548 min_key = self.G2_node_order.__getitem__ 

549 

550 # First we compute the out-terminal sets. 

551 T1_out = [node for node in self.out_1 if node not in self.core_1] 

552 T2_out = [node for node in self.out_2 if node not in self.core_2] 

553 

554 # If T1_out and T2_out are both nonempty. 

555 # P(s) = T1_out x {min T2_out} 

556 if T1_out and T2_out: 

557 node_2 = min(T2_out, key=min_key) 

558 for node_1 in T1_out: 

559 yield node_1, node_2 

560 

561 # If T1_out and T2_out were both empty.... 

562 # We compute the in-terminal sets. 

563 

564 # elif not (T1_out or T2_out): # as suggested by [2], incorrect 

565 else: # as suggested by [1], correct 

566 T1_in = [node for node in self.in_1 if node not in self.core_1] 

567 T2_in = [node for node in self.in_2 if node not in self.core_2] 

568 

569 # If T1_in and T2_in are both nonempty. 

570 # P(s) = T1_out x {min T2_out} 

571 if T1_in and T2_in: 

572 node_2 = min(T2_in, key=min_key) 

573 for node_1 in T1_in: 

574 yield node_1, node_2 

575 

576 # If all terminal sets are empty... 

577 # P(s) = (N_1 - M_1) x {min (N_2 - M_2)} 

578 

579 # elif not (T1_in or T2_in): # as suggested by [2], incorrect 

580 else: # as inferred from [1], correct 

581 node_2 = min(G2_nodes - set(self.core_2), key=min_key) 

582 for node_1 in G1_nodes: 

583 if node_1 not in self.core_1: 

584 yield node_1, node_2 

585 

586 # For all other cases, we don't have any candidate pairs. 

587 

588 def initialize(self): 

589 """Reinitializes the state of the algorithm. 

590 

591 This method should be redefined if using something other than DiGMState. 

592 If only subclassing GraphMatcher, a redefinition is not necessary. 

593 """ 

594 

595 # core_1[n] contains the index of the node paired with n, which is m, 

596 # provided n is in the mapping. 

597 # core_2[m] contains the index of the node paired with m, which is n, 

598 # provided m is in the mapping. 

599 self.core_1 = {} 

600 self.core_2 = {} 

601 

602 # See the paper for definitions of M_x and T_x^{y} 

603 

604 # in_1[n] is non-zero if n is in M_1 or in T_1^{in} 

605 # out_1[n] is non-zero if n is in M_1 or in T_1^{out} 

606 # 

607 # in_2[m] is non-zero if m is in M_2 or in T_2^{in} 

608 # out_2[m] is non-zero if m is in M_2 or in T_2^{out} 

609 # 

610 # The value stored is the depth of the search tree when the node became 

611 # part of the corresponding set. 

612 self.in_1 = {} 

613 self.in_2 = {} 

614 self.out_1 = {} 

615 self.out_2 = {} 

616 

617 self.state = DiGMState(self) 

618 

619 # Provide a convenient way to access the isomorphism mapping. 

620 self.mapping = self.core_1.copy() 

621 

622 def syntactic_feasibility(self, G1_node, G2_node): 

623 """Returns True if adding (G1_node, G2_node) is syntactically feasible. 

624 

625 This function returns True if it is adding the candidate pair 

626 to the current partial isomorphism/monomorphism mapping is allowable. 

627 The addition is allowable if the inclusion of the candidate pair does 

628 not make it impossible for an isomorphism/monomorphism to be found. 

629 """ 

630 

631 # The VF2 algorithm was designed to work with graphs having, at most, 

632 # one edge connecting any two nodes. This is not the case when 

633 # dealing with an MultiGraphs. 

634 # 

635 # Basically, when we test the look-ahead rules R_pred and R_succ, we 

636 # will make sure that the number of edges are checked. We also add 

637 # a R_self check to verify that the number of selfloops is acceptable. 

638 

639 # Users might be comparing DiGraph instances with MultiDiGraph 

640 # instances. So the generic DiGraphMatcher class must work with 

641 # MultiDiGraphs. Care must be taken since the value in the innermost 

642 # dictionary is a singlet for DiGraph instances. For MultiDiGraphs, 

643 # the value in the innermost dictionary is a list. 

644 

645 ### 

646 # Test at each step to get a return value as soon as possible. 

647 ### 

648 

649 # Look ahead 0 

650 

651 # R_self 

652 

653 # The number of selfloops for G1_node must equal the number of 

654 # self-loops for G2_node. Without this check, we would fail on R_pred 

655 # at the next recursion level. This should prune the tree even further. 

656 if self.test == "mono": 

657 if self.G1.number_of_edges(G1_node, G1_node) < self.G2.number_of_edges( 

658 G2_node, G2_node 

659 ): 

660 return False 

661 else: 

662 if self.G1.number_of_edges(G1_node, G1_node) != self.G2.number_of_edges( 

663 G2_node, G2_node 

664 ): 

665 return False 

666 

667 # R_pred 

668 

669 # For each predecessor n' of n in the partial mapping, the 

670 # corresponding node m' is a predecessor of m, and vice versa. Also, 

671 # the number of edges must be equal 

672 if self.test != "mono": 

673 for predecessor in self.G1.pred[G1_node]: 

674 if predecessor in self.core_1: 

675 if self.core_1[predecessor] not in self.G2.pred[G2_node]: 

676 return False 

677 elif self.G1.number_of_edges( 

678 predecessor, G1_node 

679 ) != self.G2.number_of_edges(self.core_1[predecessor], G2_node): 

680 return False 

681 

682 for predecessor in self.G2.pred[G2_node]: 

683 if predecessor in self.core_2: 

684 if self.core_2[predecessor] not in self.G1.pred[G1_node]: 

685 return False 

686 elif self.test == "mono": 

687 if self.G1.number_of_edges( 

688 self.core_2[predecessor], G1_node 

689 ) < self.G2.number_of_edges(predecessor, G2_node): 

690 return False 

691 else: 

692 if self.G1.number_of_edges( 

693 self.core_2[predecessor], G1_node 

694 ) != self.G2.number_of_edges(predecessor, G2_node): 

695 return False 

696 

697 # R_succ 

698 

699 # For each successor n' of n in the partial mapping, the corresponding 

700 # node m' is a successor of m, and vice versa. Also, the number of 

701 # edges must be equal. 

702 if self.test != "mono": 

703 for successor in self.G1[G1_node]: 

704 if successor in self.core_1: 

705 if self.core_1[successor] not in self.G2[G2_node]: 

706 return False 

707 elif self.G1.number_of_edges( 

708 G1_node, successor 

709 ) != self.G2.number_of_edges(G2_node, self.core_1[successor]): 

710 return False 

711 

712 for successor in self.G2[G2_node]: 

713 if successor in self.core_2: 

714 if self.core_2[successor] not in self.G1[G1_node]: 

715 return False 

716 elif self.test == "mono": 

717 if self.G1.number_of_edges( 

718 G1_node, self.core_2[successor] 

719 ) < self.G2.number_of_edges(G2_node, successor): 

720 return False 

721 else: 

722 if self.G1.number_of_edges( 

723 G1_node, self.core_2[successor] 

724 ) != self.G2.number_of_edges(G2_node, successor): 

725 return False 

726 

727 if self.test != "mono": 

728 # Look ahead 1 

729 

730 # R_termin 

731 # The number of predecessors of n that are in T_1^{in} is equal to the 

732 # number of predecessors of m that are in T_2^{in}. 

733 num1 = 0 

734 for predecessor in self.G1.pred[G1_node]: 

735 if (predecessor in self.in_1) and (predecessor not in self.core_1): 

736 num1 += 1 

737 num2 = 0 

738 for predecessor in self.G2.pred[G2_node]: 

739 if (predecessor in self.in_2) and (predecessor not in self.core_2): 

740 num2 += 1 

741 if self.test == "graph": 

742 if num1 != num2: 

743 return False 

744 else: # self.test == 'subgraph' 

745 if not (num1 >= num2): 

746 return False 

747 

748 # The number of successors of n that are in T_1^{in} is equal to the 

749 # number of successors of m that are in T_2^{in}. 

750 num1 = 0 

751 for successor in self.G1[G1_node]: 

752 if (successor in self.in_1) and (successor not in self.core_1): 

753 num1 += 1 

754 num2 = 0 

755 for successor in self.G2[G2_node]: 

756 if (successor in self.in_2) and (successor not in self.core_2): 

757 num2 += 1 

758 if self.test == "graph": 

759 if num1 != num2: 

760 return False 

761 else: # self.test == 'subgraph' 

762 if not (num1 >= num2): 

763 return False 

764 

765 # R_termout 

766 

767 # The number of predecessors of n that are in T_1^{out} is equal to the 

768 # number of predecessors of m that are in T_2^{out}. 

769 num1 = 0 

770 for predecessor in self.G1.pred[G1_node]: 

771 if (predecessor in self.out_1) and (predecessor not in self.core_1): 

772 num1 += 1 

773 num2 = 0 

774 for predecessor in self.G2.pred[G2_node]: 

775 if (predecessor in self.out_2) and (predecessor not in self.core_2): 

776 num2 += 1 

777 if self.test == "graph": 

778 if num1 != num2: 

779 return False 

780 else: # self.test == 'subgraph' 

781 if not (num1 >= num2): 

782 return False 

783 

784 # The number of successors of n that are in T_1^{out} is equal to the 

785 # number of successors of m that are in T_2^{out}. 

786 num1 = 0 

787 for successor in self.G1[G1_node]: 

788 if (successor in self.out_1) and (successor not in self.core_1): 

789 num1 += 1 

790 num2 = 0 

791 for successor in self.G2[G2_node]: 

792 if (successor in self.out_2) and (successor not in self.core_2): 

793 num2 += 1 

794 if self.test == "graph": 

795 if num1 != num2: 

796 return False 

797 else: # self.test == 'subgraph' 

798 if not (num1 >= num2): 

799 return False 

800 

801 # Look ahead 2 

802 

803 # R_new 

804 

805 # The number of predecessors of n that are neither in the core_1 nor 

806 # T_1^{in} nor T_1^{out} is equal to the number of predecessors of m 

807 # that are neither in core_2 nor T_2^{in} nor T_2^{out}. 

808 num1 = 0 

809 for predecessor in self.G1.pred[G1_node]: 

810 if (predecessor not in self.in_1) and (predecessor not in self.out_1): 

811 num1 += 1 

812 num2 = 0 

813 for predecessor in self.G2.pred[G2_node]: 

814 if (predecessor not in self.in_2) and (predecessor not in self.out_2): 

815 num2 += 1 

816 if self.test == "graph": 

817 if num1 != num2: 

818 return False 

819 else: # self.test == 'subgraph' 

820 if not (num1 >= num2): 

821 return False 

822 

823 # The number of successors of n that are neither in the core_1 nor 

824 # T_1^{in} nor T_1^{out} is equal to the number of successors of m 

825 # that are neither in core_2 nor T_2^{in} nor T_2^{out}. 

826 num1 = 0 

827 for successor in self.G1[G1_node]: 

828 if (successor not in self.in_1) and (successor not in self.out_1): 

829 num1 += 1 

830 num2 = 0 

831 for successor in self.G2[G2_node]: 

832 if (successor not in self.in_2) and (successor not in self.out_2): 

833 num2 += 1 

834 if self.test == "graph": 

835 if num1 != num2: 

836 return False 

837 else: # self.test == 'subgraph' 

838 if not (num1 >= num2): 

839 return False 

840 

841 # Otherwise, this node pair is syntactically feasible! 

842 return True 

843 

844 

845class GMState: 

846 """Internal representation of state for the GraphMatcher class. 

847 

848 This class is used internally by the GraphMatcher class. It is used 

849 only to store state specific data. There will be at most G2.order() of 

850 these objects in memory at a time, due to the depth-first search 

851 strategy employed by the VF2 algorithm. 

852 """ 

853 

854 def __init__(self, GM, G1_node=None, G2_node=None): 

855 """Initializes GMState object. 

856 

857 Pass in the GraphMatcher to which this GMState belongs and the 

858 new node pair that will be added to the GraphMatcher's current 

859 isomorphism mapping. 

860 """ 

861 self.GM = GM 

862 

863 # Initialize the last stored node pair. 

864 self.G1_node = None 

865 self.G2_node = None 

866 self.depth = len(GM.core_1) 

867 

868 if G1_node is None or G2_node is None: 

869 # Then we reset the class variables 

870 GM.core_1 = {} 

871 GM.core_2 = {} 

872 GM.inout_1 = {} 

873 GM.inout_2 = {} 

874 

875 # Watch out! G1_node == 0 should evaluate to True. 

876 if G1_node is not None and G2_node is not None: 

877 # Add the node pair to the isomorphism mapping. 

878 GM.core_1[G1_node] = G2_node 

879 GM.core_2[G2_node] = G1_node 

880 

881 # Store the node that was added last. 

882 self.G1_node = G1_node 

883 self.G2_node = G2_node 

884 

885 # Now we must update the other two vectors. 

886 # We will add only if it is not in there already! 

887 self.depth = len(GM.core_1) 

888 

889 # First we add the new nodes... 

890 if G1_node not in GM.inout_1: 

891 GM.inout_1[G1_node] = self.depth 

892 if G2_node not in GM.inout_2: 

893 GM.inout_2[G2_node] = self.depth 

894 

895 # Now we add every other node... 

896 

897 # Updates for T_1^{inout} 

898 new_nodes = set() 

899 for node in GM.core_1: 

900 new_nodes.update( 

901 [neighbor for neighbor in GM.G1[node] if neighbor not in GM.core_1] 

902 ) 

903 for node in new_nodes: 

904 if node not in GM.inout_1: 

905 GM.inout_1[node] = self.depth 

906 

907 # Updates for T_2^{inout} 

908 new_nodes = set() 

909 for node in GM.core_2: 

910 new_nodes.update( 

911 [neighbor for neighbor in GM.G2[node] if neighbor not in GM.core_2] 

912 ) 

913 for node in new_nodes: 

914 if node not in GM.inout_2: 

915 GM.inout_2[node] = self.depth 

916 

917 def restore(self): 

918 """Deletes the GMState object and restores the class variables.""" 

919 # First we remove the node that was added from the core vectors. 

920 # Watch out! G1_node == 0 should evaluate to True. 

921 if self.G1_node is not None and self.G2_node is not None: 

922 del self.GM.core_1[self.G1_node] 

923 del self.GM.core_2[self.G2_node] 

924 

925 # Now we revert the other two vectors. 

926 # Thus, we delete all entries which have this depth level. 

927 for vector in (self.GM.inout_1, self.GM.inout_2): 

928 for node in list(vector.keys()): 

929 if vector[node] == self.depth: 

930 del vector[node] 

931 

932 

933class DiGMState: 

934 """Internal representation of state for the DiGraphMatcher class. 

935 

936 This class is used internally by the DiGraphMatcher class. It is used 

937 only to store state specific data. There will be at most G2.order() of 

938 these objects in memory at a time, due to the depth-first search 

939 strategy employed by the VF2 algorithm. 

940 

941 """ 

942 

943 def __init__(self, GM, G1_node=None, G2_node=None): 

944 """Initializes DiGMState object. 

945 

946 Pass in the DiGraphMatcher to which this DiGMState belongs and the 

947 new node pair that will be added to the GraphMatcher's current 

948 isomorphism mapping. 

949 """ 

950 self.GM = GM 

951 

952 # Initialize the last stored node pair. 

953 self.G1_node = None 

954 self.G2_node = None 

955 self.depth = len(GM.core_1) 

956 

957 if G1_node is None or G2_node is None: 

958 # Then we reset the class variables 

959 GM.core_1 = {} 

960 GM.core_2 = {} 

961 GM.in_1 = {} 

962 GM.in_2 = {} 

963 GM.out_1 = {}