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

1""" 

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

3VF2++ Algorithm 

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

5 

6An implementation of the VF2++ algorithm [1]_ for Graph Isomorphism testing. 

7 

8The simplest interface to use this module is to call: 

9 

10`vf2pp_is_isomorphic`: to check whether two graphs are isomorphic. 

11`vf2pp_isomorphism`: to obtain the node mapping between two graphs, 

12in case they are isomorphic. 

13`vf2pp_all_isomorphisms`: to generate all possible mappings between two graphs, 

14if isomorphic. 

15 

16Introduction 

17------------ 

18The VF2++ algorithm, follows a similar logic to that of VF2, while also 

19introducing new easy-to-check cutting rules and determining the optimal access 

20order of nodes. It is also implemented in a non-recursive manner, which saves 

21both time and space, when compared to its previous counterpart. 

22 

23The optimal node ordering is obtained after taking into consideration both the 

24degree but also the label rarity of each node. 

25This way we place the nodes that are more likely to match, first in the order, 

26thus examining the most promising branches in the beginning. 

27The rules also consider node labels, making it easier to prune unfruitful 

28branches early in the process. 

29 

30Examples 

31-------- 

32 

33Suppose G1 and G2 are Isomorphic Graphs. Verification is as follows: 

34 

35Without node labels: 

36 

37>>> import networkx as nx 

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

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

40>>> nx.vf2pp_is_isomorphic(G1, G2, node_label=None) 

41True 

42>>> nx.vf2pp_isomorphism(G1, G2, node_label=None) 

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

44 

45With node labels: 

46 

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

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

49>>> mapped = {1: 1, 2: 2, 3: 3, 0: 0} 

50>>> nx.set_node_attributes(G1, dict(zip(G1, ["blue", "red", "green", "yellow"])), "label") 

51>>> nx.set_node_attributes(G2, dict(zip([mapped[u] for u in G1], ["blue", "red", "green", "yellow"])), "label") 

52>>> nx.vf2pp_is_isomorphic(G1, G2, node_label="label") 

53True 

54>>> nx.vf2pp_isomorphism(G1, G2, node_label="label") 

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

56 

57References 

58---------- 

59.. [1] Jüttner, Alpár & Madarasi, Péter. (2018). "VF2++—An improved subgraph 

60 isomorphism algorithm". Discrete Applied Mathematics. 242. 

61 https://doi.org/10.1016/j.dam.2018.02.018 

62 

63""" 

64import collections 

65 

66import networkx as nx 

67 

68__all__ = ["vf2pp_isomorphism", "vf2pp_is_isomorphic", "vf2pp_all_isomorphisms"] 

69 

70_GraphParameters = collections.namedtuple( 

71 "_GraphParameters", 

72 [ 

73 "G1", 

74 "G2", 

75 "G1_labels", 

76 "G2_labels", 

77 "nodes_of_G1Labels", 

78 "nodes_of_G2Labels", 

79 "G2_nodes_of_degree", 

80 ], 

81) 

82 

83_StateParameters = collections.namedtuple( 

84 "_StateParameters", 

85 [ 

86 "mapping", 

87 "reverse_mapping", 

88 "T1", 

89 "T1_in", 

90 "T1_tilde", 

91 "T1_tilde_in", 

92 "T2", 

93 "T2_in", 

94 "T2_tilde", 

95 "T2_tilde_in", 

96 ], 

97) 

98 

99 

100@nx._dispatch(graphs={"G1": 0, "G2": 1}, node_attrs={"node_label": "default_label"}) 

101def vf2pp_isomorphism(G1, G2, node_label=None, default_label=None): 

102 """Return an isomorphic mapping between `G1` and `G2` if it exists. 

103 

104 Parameters 

105 ---------- 

106 G1, G2 : NetworkX Graph or MultiGraph instances. 

107 The two graphs to check for isomorphism. 

108 

109 node_label : str, optional 

110 The name of the node attribute to be used when comparing nodes. 

111 The default is `None`, meaning node attributes are not considered 

112 in the comparison. Any node that doesn't have the `node_label` 

113 attribute uses `default_label` instead. 

114 

115 default_label : scalar 

116 Default value to use when a node doesn't have an attribute 

117 named `node_label`. Default is `None`. 

118 

119 Returns 

120 ------- 

121 dict or None 

122 Node mapping if the two graphs are isomorphic. None otherwise. 

123 """ 

124 try: 

125 mapping = next(vf2pp_all_isomorphisms(G1, G2, node_label, default_label)) 

126 return mapping 

127 except StopIteration: 

128 return None 

129 

130 

131@nx._dispatch(graphs={"G1": 0, "G2": 1}, node_attrs={"node_label": "default_label"}) 

132def vf2pp_is_isomorphic(G1, G2, node_label=None, default_label=None): 

133 """Examines whether G1 and G2 are isomorphic. 

134 

135 Parameters 

136 ---------- 

137 G1, G2 : NetworkX Graph or MultiGraph instances. 

138 The two graphs to check for isomorphism. 

139 

140 node_label : str, optional 

141 The name of the node attribute to be used when comparing nodes. 

142 The default is `None`, meaning node attributes are not considered 

143 in the comparison. Any node that doesn't have the `node_label` 

144 attribute uses `default_label` instead. 

145 

146 default_label : scalar 

147 Default value to use when a node doesn't have an attribute 

148 named `node_label`. Default is `None`. 

149 

150 Returns 

151 ------- 

152 bool 

153 True if the two graphs are isomorphic, False otherwise. 

154 """ 

155 if vf2pp_isomorphism(G1, G2, node_label, default_label) is not None: 

156 return True 

157 return False 

158 

159 

160@nx._dispatch(graphs={"G1": 0, "G2": 1}, node_attrs={"node_label": "default_label"}) 

161def vf2pp_all_isomorphisms(G1, G2, node_label=None, default_label=None): 

162 """Yields all the possible mappings between G1 and G2. 

163 

164 Parameters 

165 ---------- 

166 G1, G2 : NetworkX Graph or MultiGraph instances. 

167 The two graphs to check for isomorphism. 

168 

169 node_label : str, optional 

170 The name of the node attribute to be used when comparing nodes. 

171 The default is `None`, meaning node attributes are not considered 

172 in the comparison. Any node that doesn't have the `node_label` 

173 attribute uses `default_label` instead. 

174 

175 default_label : scalar 

176 Default value to use when a node doesn't have an attribute 

177 named `node_label`. Default is `None`. 

178 

179 Yields 

180 ------ 

181 dict 

182 Isomorphic mapping between the nodes in `G1` and `G2`. 

183 """ 

184 if G1.number_of_nodes() == 0 or G2.number_of_nodes() == 0: 

185 return False 

186 

187 # Create the degree dicts based on graph type 

188 if G1.is_directed(): 

189 G1_degree = { 

190 n: (in_degree, out_degree) 

191 for (n, in_degree), (_, out_degree) in zip(G1.in_degree, G1.out_degree) 

192 } 

193 G2_degree = { 

194 n: (in_degree, out_degree) 

195 for (n, in_degree), (_, out_degree) in zip(G2.in_degree, G2.out_degree) 

196 } 

197 else: 

198 G1_degree = dict(G1.degree) 

199 G2_degree = dict(G2.degree) 

200 

201 if not G1.is_directed(): 

202 find_candidates = _find_candidates 

203 restore_Tinout = _restore_Tinout 

204 else: 

205 find_candidates = _find_candidates_Di 

206 restore_Tinout = _restore_Tinout_Di 

207 

208 # Check that both graphs have the same number of nodes and degree sequence 

209 if G1.order() != G2.order(): 

210 return False 

211 if sorted(G1_degree.values()) != sorted(G2_degree.values()): 

212 return False 

213 

214 # Initialize parameters and cache necessary information about degree and labels 

215 graph_params, state_params = _initialize_parameters( 

216 G1, G2, G2_degree, node_label, default_label 

217 ) 

218 

219 # Check if G1 and G2 have the same labels, and that number of nodes per label is equal between the two graphs 

220 if not _precheck_label_properties(graph_params): 

221 return False 

222 

223 # Calculate the optimal node ordering 

224 node_order = _matching_order(graph_params) 

225 

226 # Initialize the stack 

227 stack = [] 

228 candidates = iter( 

229 find_candidates(node_order[0], graph_params, state_params, G1_degree) 

230 ) 

231 stack.append((node_order[0], candidates)) 

232 

233 mapping = state_params.mapping 

234 reverse_mapping = state_params.reverse_mapping 

235 

236 # Index of the node from the order, currently being examined 

237 matching_node = 1 

238 

239 while stack: 

240 current_node, candidate_nodes = stack[-1] 

241 

242 try: 

243 candidate = next(candidate_nodes) 

244 except StopIteration: 

245 # If no remaining candidates, return to a previous state, and follow another branch 

246 stack.pop() 

247 matching_node -= 1 

248 if stack: 

249 # Pop the previously added u-v pair, and look for a different candidate _v for u 

250 popped_node1, _ = stack[-1] 

251 popped_node2 = mapping[popped_node1] 

252 mapping.pop(popped_node1) 

253 reverse_mapping.pop(popped_node2) 

254 restore_Tinout(popped_node1, popped_node2, graph_params, state_params) 

255 continue 

256 

257 if _feasibility(current_node, candidate, graph_params, state_params): 

258 # Terminate if mapping is extended to its full 

259 if len(mapping) == G2.number_of_nodes() - 1: 

260 cp_mapping = mapping.copy() 

261 cp_mapping[current_node] = candidate 

262 yield cp_mapping 

263 continue 

264 

265 # Feasibility rules pass, so extend the mapping and update the parameters 

266 mapping[current_node] = candidate 

267 reverse_mapping[candidate] = current_node 

268 _update_Tinout(current_node, candidate, graph_params, state_params) 

269 # Append the next node and its candidates to the stack 

270 candidates = iter( 

271 find_candidates( 

272 node_order[matching_node], graph_params, state_params, G1_degree 

273 ) 

274 ) 

275 stack.append((node_order[matching_node], candidates)) 

276 matching_node += 1 

277 

278 

279def _precheck_label_properties(graph_params): 

280 G1, G2, G1_labels, G2_labels, nodes_of_G1Labels, nodes_of_G2Labels, _ = graph_params 

281 if any( 

282 label not in nodes_of_G1Labels or len(nodes_of_G1Labels[label]) != len(nodes) 

283 for label, nodes in nodes_of_G2Labels.items() 

284 ): 

285 return False 

286 return True 

287 

288 

289def _initialize_parameters(G1, G2, G2_degree, node_label=None, default_label=-1): 

290 """Initializes all the necessary parameters for VF2++ 

291 

292 Parameters 

293 ---------- 

294 G1,G2: NetworkX Graph or MultiGraph instances. 

295 The two graphs to check for isomorphism or monomorphism 

296 

297 G1_labels,G2_labels: dict 

298 The label of every node in G1 and G2 respectively 

299 

300 Returns 

301 ------- 

302 graph_params: namedtuple 

303 Contains all the Graph-related parameters: 

304 

305 G1,G2 

306 G1_labels,G2_labels: dict 

307 

308 state_params: namedtuple 

309 Contains all the State-related parameters: 

310 

311 mapping: dict 

312 The mapping as extended so far. Maps nodes of G1 to nodes of G2 

313 

314 reverse_mapping: dict 

315 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1. It's basically "mapping" reversed 

316 

317 T1, T2: set 

318 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are 

319 neighbors of nodes that are. 

320 

321 T1_out, T2_out: set 

322 Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti 

323 """ 

324 G1_labels = dict(G1.nodes(data=node_label, default=default_label)) 

325 G2_labels = dict(G2.nodes(data=node_label, default=default_label)) 

326 

327 graph_params = _GraphParameters( 

328 G1, 

329 G2, 

330 G1_labels, 

331 G2_labels, 

332 nx.utils.groups(G1_labels), 

333 nx.utils.groups(G2_labels), 

334 nx.utils.groups(G2_degree), 

335 ) 

336 

337 T1, T1_in = set(), set() 

338 T2, T2_in = set(), set() 

339 if G1.is_directed(): 

340 T1_tilde, T1_tilde_in = ( 

341 set(G1.nodes()), 

342 set(), 

343 ) # todo: do we need Ti_tilde_in? What nodes does it have? 

344 T2_tilde, T2_tilde_in = set(G2.nodes()), set() 

345 else: 

346 T1_tilde, T1_tilde_in = set(G1.nodes()), set() 

347 T2_tilde, T2_tilde_in = set(G2.nodes()), set() 

348 

349 state_params = _StateParameters( 

350 {}, 

351 {}, 

352 T1, 

353 T1_in, 

354 T1_tilde, 

355 T1_tilde_in, 

356 T2, 

357 T2_in, 

358 T2_tilde, 

359 T2_tilde_in, 

360 ) 

361 

362 return graph_params, state_params 

363 

364 

365def _matching_order(graph_params): 

366 """The node ordering as introduced in VF2++. 

367 

368 Notes 

369 ----- 

370 Taking into account the structure of the Graph and the node labeling, the nodes are placed in an order such that, 

371 most of the unfruitful/infeasible branches of the search space can be pruned on high levels, significantly 

372 decreasing the number of visited states. The premise is that, the algorithm will be able to recognize 

373 inconsistencies early, proceeding to go deep into the search tree only if it's needed. 

374 

375 Parameters 

376 ---------- 

377 graph_params: namedtuple 

378 Contains: 

379 

380 G1,G2: NetworkX Graph or MultiGraph instances. 

381 The two graphs to check for isomorphism or monomorphism. 

382 

383 G1_labels,G2_labels: dict 

384 The label of every node in G1 and G2 respectively. 

385 

386 Returns 

387 ------- 

388 node_order: list 

389 The ordering of the nodes. 

390 """ 

391 G1, G2, G1_labels, _, _, nodes_of_G2Labels, _ = graph_params 

392 if not G1 and not G2: 

393 return {} 

394 

395 if G1.is_directed(): 

396 G1 = G1.to_undirected(as_view=True) 

397 

398 V1_unordered = set(G1.nodes()) 

399 label_rarity = {label: len(nodes) for label, nodes in nodes_of_G2Labels.items()} 

400 used_degrees = {node: 0 for node in G1} 

401 node_order = [] 

402 

403 while V1_unordered: 

404 max_rarity = min(label_rarity[G1_labels[x]] for x in V1_unordered) 

405 rarest_nodes = [ 

406 n for n in V1_unordered if label_rarity[G1_labels[n]] == max_rarity 

407 ] 

408 max_node = max(rarest_nodes, key=G1.degree) 

409 

410 for dlevel_nodes in nx.bfs_layers(G1, max_node): 

411 nodes_to_add = dlevel_nodes.copy() 

412 while nodes_to_add: 

413 max_used_degree = max(used_degrees[n] for n in nodes_to_add) 

414 max_used_degree_nodes = [ 

415 n for n in nodes_to_add if used_degrees[n] == max_used_degree 

416 ] 

417 max_degree = max(G1.degree[n] for n in max_used_degree_nodes) 

418 max_degree_nodes = [ 

419 n for n in max_used_degree_nodes if G1.degree[n] == max_degree 

420 ] 

421 next_node = min( 

422 max_degree_nodes, key=lambda x: label_rarity[G1_labels[x]] 

423 ) 

424 

425 node_order.append(next_node) 

426 for node in G1.neighbors(next_node): 

427 used_degrees[node] += 1 

428 

429 nodes_to_add.remove(next_node) 

430 label_rarity[G1_labels[next_node]] -= 1 

431 V1_unordered.discard(next_node) 

432 

433 return node_order 

434 

435 

436def _find_candidates( 

437 u, graph_params, state_params, G1_degree 

438): # todo: make the 4th argument the degree of u 

439 """Given node u of G1, finds the candidates of u from G2. 

440 

441 Parameters 

442 ---------- 

443 u: Graph node 

444 The node from G1 for which to find the candidates from G2. 

445 

446 graph_params: namedtuple 

447 Contains all the Graph-related parameters: 

448 

449 G1,G2: NetworkX Graph or MultiGraph instances. 

450 The two graphs to check for isomorphism or monomorphism 

451 

452 G1_labels,G2_labels: dict 

453 The label of every node in G1 and G2 respectively 

454 

455 state_params: namedtuple 

456 Contains all the State-related parameters: 

457 

458 mapping: dict 

459 The mapping as extended so far. Maps nodes of G1 to nodes of G2 

460 

461 reverse_mapping: dict 

462 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1. It's basically "mapping" reversed 

463 

464 T1, T2: set 

465 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are 

466 neighbors of nodes that are. 

467 

468 T1_tilde, T2_tilde: set 

469 Ti_tilde contains all the nodes from Gi, that are neither in the mapping nor in Ti 

470 

471 Returns 

472 ------- 

473 candidates: set 

474 The nodes from G2 which are candidates for u. 

475 """ 

476 G1, G2, G1_labels, _, _, nodes_of_G2Labels, G2_nodes_of_degree = graph_params 

477 mapping, reverse_mapping, _, _, _, _, _, _, T2_tilde, _ = state_params 

478 

479 covered_neighbors = [nbr for nbr in G1[u] if nbr in mapping] 

480 if not covered_neighbors: 

481 candidates = set(nodes_of_G2Labels[G1_labels[u]]) 

482 candidates.intersection_update(G2_nodes_of_degree[G1_degree[u]]) 

483 candidates.intersection_update(T2_tilde) 

484 candidates.difference_update(reverse_mapping) 

485 if G1.is_multigraph(): 

486 candidates.difference_update( 

487 { 

488 node 

489 for node in candidates 

490 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node) 

491 } 

492 ) 

493 return candidates 

494 

495 nbr1 = covered_neighbors[0] 

496 common_nodes = set(G2[mapping[nbr1]]) 

497 

498 for nbr1 in covered_neighbors[1:]: 

499 common_nodes.intersection_update(G2[mapping[nbr1]]) 

500 

501 common_nodes.difference_update(reverse_mapping) 

502 common_nodes.intersection_update(G2_nodes_of_degree[G1_degree[u]]) 

503 common_nodes.intersection_update(nodes_of_G2Labels[G1_labels[u]]) 

504 if G1.is_multigraph(): 

505 common_nodes.difference_update( 

506 { 

507 node 

508 for node in common_nodes 

509 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node) 

510 } 

511 ) 

512 return common_nodes 

513 

514 

515def _find_candidates_Di(u, graph_params, state_params, G1_degree): 

516 G1, G2, G1_labels, _, _, nodes_of_G2Labels, G2_nodes_of_degree = graph_params 

517 mapping, reverse_mapping, _, _, _, _, _, _, T2_tilde, _ = state_params 

518 

519 covered_successors = [succ for succ in G1[u] if succ in mapping] 

520 covered_predecessors = [pred for pred in G1.pred[u] if pred in mapping] 

521 

522 if not (covered_successors or covered_predecessors): 

523 candidates = set(nodes_of_G2Labels[G1_labels[u]]) 

524 candidates.intersection_update(G2_nodes_of_degree[G1_degree[u]]) 

525 candidates.intersection_update(T2_tilde) 

526 candidates.difference_update(reverse_mapping) 

527 if G1.is_multigraph(): 

528 candidates.difference_update( 

529 { 

530 node 

531 for node in candidates 

532 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node) 

533 } 

534 ) 

535 return candidates 

536 

537 if covered_successors: 

538 succ1 = covered_successors[0] 

539 common_nodes = set(G2.pred[mapping[succ1]]) 

540 

541 for succ1 in covered_successors[1:]: 

542 common_nodes.intersection_update(G2.pred[mapping[succ1]]) 

543 else: 

544 pred1 = covered_predecessors.pop() 

545 common_nodes = set(G2[mapping[pred1]]) 

546 

547 for pred1 in covered_predecessors: 

548 common_nodes.intersection_update(G2[mapping[pred1]]) 

549 

550 common_nodes.difference_update(reverse_mapping) 

551 common_nodes.intersection_update(G2_nodes_of_degree[G1_degree[u]]) 

552 common_nodes.intersection_update(nodes_of_G2Labels[G1_labels[u]]) 

553 if G1.is_multigraph(): 

554 common_nodes.difference_update( 

555 { 

556 node 

557 for node in common_nodes 

558 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node) 

559 } 

560 ) 

561 return common_nodes 

562 

563 

564def _feasibility(node1, node2, graph_params, state_params): 

565 """Given a candidate pair of nodes u and v from G1 and G2 respectively, checks if it's feasible to extend the 

566 mapping, i.e. if u and v can be matched. 

567 

568 Notes 

569 ----- 

570 This function performs all the necessary checking by applying both consistency and cutting rules. 

571 

572 Parameters 

573 ---------- 

574 node1, node2: Graph node 

575 The candidate pair of nodes being checked for matching 

576 

577 graph_params: namedtuple 

578 Contains all the Graph-related parameters: 

579 

580 G1,G2: NetworkX Graph or MultiGraph instances. 

581 The two graphs to check for isomorphism or monomorphism 

582 

583 G1_labels,G2_labels: dict 

584 The label of every node in G1 and G2 respectively 

585 

586 state_params: namedtuple 

587 Contains all the State-related parameters: 

588 

589 mapping: dict 

590 The mapping as extended so far. Maps nodes of G1 to nodes of G2 

591 

592 reverse_mapping: dict 

593 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1. It's basically "mapping" reversed 

594 

595 T1, T2: set 

596 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are 

597 neighbors of nodes that are. 

598 

599 T1_out, T2_out: set 

600 Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti 

601 

602 Returns 

603 ------- 

604 True if all checks are successful, False otherwise. 

605 """ 

606 G1 = graph_params.G1 

607 

608 if _cut_PT(node1, node2, graph_params, state_params): 

609 return False 

610 

611 if G1.is_multigraph(): 

612 if not _consistent_PT(node1, node2, graph_params, state_params): 

613 return False 

614 

615 return True 

616 

617 

618def _cut_PT(u, v, graph_params, state_params): 

619 """Implements the cutting rules for the ISO problem. 

620 

621 Parameters 

622 ---------- 

623 u, v: Graph node 

624 The two candidate nodes being examined. 

625 

626 graph_params: namedtuple 

627 Contains all the Graph-related parameters: 

628 

629 G1,G2: NetworkX Graph or MultiGraph instances. 

630 The two graphs to check for isomorphism or monomorphism 

631 

632 G1_labels,G2_labels: dict 

633 The label of every node in G1 and G2 respectively 

634 

635 state_params: namedtuple 

636 Contains all the State-related parameters: 

637 

638 mapping: dict 

639 The mapping as extended so far. Maps nodes of G1 to nodes of G2 

640 

641 reverse_mapping: dict 

642 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1. It's basically "mapping" reversed 

643 

644 T1, T2: set 

645 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are 

646 neighbors of nodes that are. 

647 

648 T1_tilde, T2_tilde: set 

649 Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti 

650 

651 Returns 

652 ------- 

653 True if we should prune this branch, i.e. the node pair failed the cutting checks. False otherwise. 

654 """ 

655 G1, G2, G1_labels, G2_labels, _, _, _ = graph_params 

656 ( 

657 _, 

658 _, 

659 T1, 

660 T1_in, 

661 T1_tilde, 

662 _, 

663 T2, 

664 T2_in, 

665 T2_tilde, 

666 _, 

667 ) = state_params 

668 

669 u_labels_predecessors, v_labels_predecessors = {}, {} 

670 if G1.is_directed(): 

671 u_labels_predecessors = nx.utils.groups( 

672 {n1: G1_labels[n1] for n1 in G1.pred[u]} 

673 ) 

674 v_labels_predecessors = nx.utils.groups( 

675 {n2: G2_labels[n2] for n2 in G2.pred[v]} 

676 ) 

677 

678 if set(u_labels_predecessors.keys()) != set(v_labels_predecessors.keys()): 

679 return True 

680 

681 u_labels_successors = nx.utils.groups({n1: G1_labels[n1] for n1 in G1[u]}) 

682 v_labels_successors = nx.utils.groups({n2: G2_labels[n2] for n2 in G2[v]}) 

683 

684 # if the neighbors of u, do not have the same labels as those of v, NOT feasible. 

685 if set(u_labels_successors.keys()) != set(v_labels_successors.keys()): 

686 return True 

687 

688 for label, G1_nbh in u_labels_successors.items(): 

689 G2_nbh = v_labels_successors[label] 

690 

691 if G1.is_multigraph(): 

692 # Check for every neighbor in the neighborhood, if u-nbr1 has same edges as v-nbr2 

693 u_nbrs_edges = sorted(G1.number_of_edges(u, x) for x in G1_nbh) 

694 v_nbrs_edges = sorted(G2.number_of_edges(v, x) for x in G2_nbh) 

695 if any( 

696 u_nbr_edges != v_nbr_edges 

697 for u_nbr_edges, v_nbr_edges in zip(u_nbrs_edges, v_nbrs_edges) 

698 ): 

699 return True 

700 

701 if len(T1.intersection(G1_nbh)) != len(T2.intersection(G2_nbh)): 

702 return True 

703 if len(T1_tilde.intersection(G1_nbh)) != len(T2_tilde.intersection(G2_nbh)): 

704 return True 

705 if G1.is_directed() and len(T1_in.intersection(G1_nbh)) != len( 

706 T2_in.intersection(G2_nbh) 

707 ): 

708 return True 

709 

710 if not G1.is_directed(): 

711 return False 

712 

713 for label, G1_pred in u_labels_predecessors.items(): 

714 G2_pred = v_labels_predecessors[label] 

715 

716 if G1.is_multigraph(): 

717 # Check for every neighbor in the neighborhood, if u-nbr1 has same edges as v-nbr2 

718 u_pred_edges = sorted(G1.number_of_edges(u, x) for x in G1_pred) 

719 v_pred_edges = sorted(G2.number_of_edges(v, x) for x in G2_pred) 

720 if any( 

721 u_nbr_edges != v_nbr_edges 

722 for u_nbr_edges, v_nbr_edges in zip(u_pred_edges, v_pred_edges) 

723 ): 

724 return True 

725 

726 if len(T1.intersection(G1_pred)) != len(T2.intersection(G2_pred)): 

727 return True 

728 if len(T1_tilde.intersection(G1_pred)) != len(T2_tilde.intersection(G2_pred)): 

729 return True 

730 if len(T1_in.intersection(G1_pred)) != len(T2_in.intersection(G2_pred)): 

731 return True 

732 

733 return False 

734 

735 

736def _consistent_PT(u, v, graph_params, state_params): 

737 """Checks the consistency of extending the mapping using the current node pair. 

738 

739 Parameters 

740 ---------- 

741 u, v: Graph node 

742 The two candidate nodes being examined. 

743 

744 graph_params: namedtuple 

745 Contains all the Graph-related parameters: 

746 

747 G1,G2: NetworkX Graph or MultiGraph instances. 

748 The two graphs to check for isomorphism or monomorphism 

749 

750 G1_labels,G2_labels: dict 

751 The label of every node in G1 and G2 respectively 

752 

753 state_params: namedtuple 

754 Contains all the State-related parameters: 

755 

756 mapping: dict 

757 The mapping as extended so far. Maps nodes of G1 to nodes of G2 

758 

759 reverse_mapping: dict 

760 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1. It's basically "mapping" reversed 

761 

762 T1, T2: set 

763 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are 

764 neighbors of nodes that are. 

765 

766 T1_out, T2_out: set 

767 Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti 

768 

769 Returns 

770 ------- 

771 True if the pair passes all the consistency checks successfully. False otherwise. 

772 """ 

773 G1, G2 = graph_params.G1, graph_params.G2 

774 mapping, reverse_mapping = state_params.mapping, state_params.reverse_mapping 

775 

776 for neighbor in G1[u]: 

777 if neighbor in mapping: 

778 if G1.number_of_edges(u, neighbor) != G2.number_of_edges( 

779 v, mapping[neighbor] 

780 ): 

781 return False 

782 

783 for neighbor in G2[v]: 

784 if neighbor in reverse_mapping: 

785 if G1.number_of_edges(u, reverse_mapping[neighbor]) != G2.number_of_edges( 

786 v, neighbor 

787 ): 

788 return False 

789 

790 if not G1.is_directed(): 

791 return True 

792 

793 for predecessor in G1.pred[u]: 

794 if predecessor in mapping: 

795 if G1.number_of_edges(predecessor, u) != G2.number_of_edges( 

796 mapping[predecessor], v 

797 ): 

798 return False 

799 

800 for predecessor in G2.pred[v]: 

801 if predecessor in reverse_mapping: 

802 if G1.number_of_edges( 

803 reverse_mapping[predecessor], u 

804 ) != G2.number_of_edges(predecessor, v): 

805 return False 

806 

807 return True 

808 

809 

810def _update_Tinout(new_node1, new_node2, graph_params, state_params): 

811 """Updates the Ti/Ti_out (i=1,2) when a new node pair u-v is added to the mapping. 

812 

813 Notes 

814 ----- 

815 This function should be called right after the feasibility checks are passed, and node1 is mapped to node2. The 

816 purpose of this function is to avoid brute force computing of Ti/Ti_out by iterating over all nodes of the graph 

817 and checking which nodes satisfy the necessary conditions. Instead, in every step of the algorithm we focus 

818 exclusively on the two nodes that are being added to the mapping, incrementally updating Ti/Ti_out. 

819 

820 Parameters 

821 ---------- 

822 new_node1, new_node2: Graph node 

823 The two new nodes, added to the mapping. 

824 

825 graph_params: namedtuple 

826 Contains all the Graph-related parameters: 

827 

828 G1,G2: NetworkX Graph or MultiGraph instances. 

829 The two graphs to check for isomorphism or monomorphism 

830 

831 G1_labels,G2_labels: dict 

832 The label of every node in G1 and G2 respectively 

833 

834 state_params: namedtuple 

835 Contains all the State-related parameters: 

836 

837 mapping: dict 

838 The mapping as extended so far. Maps nodes of G1 to nodes of G2 

839 

840 reverse_mapping: dict 

841 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1. It's basically "mapping" reversed 

842 

843 T1, T2: set 

844 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are 

845 neighbors of nodes that are. 

846 

847 T1_tilde, T2_tilde: set 

848 Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti 

849 """ 

850 G1, G2, _, _, _, _, _ = graph_params 

851 ( 

852 mapping, 

853 reverse_mapping, 

854 T1, 

855 T1_in, 

856 T1_tilde, 

857 T1_tilde_in, 

858 T2, 

859 T2_in, 

860 T2_tilde, 

861 T2_tilde_in, 

862 ) = state_params 

863 

864 uncovered_successors_G1 = {succ for succ in G1[new_node1] if succ not in mapping} 

865 uncovered_successors_G2 = { 

866 succ for succ in G2[new_node2] if succ not in reverse_mapping 

867 } 

868 

869 # Add the uncovered neighbors of node1 and node2 in T1 and T2 respectively 

870 T1.update(uncovered_successors_G1) 

871 T2.update(uncovered_successors_G2) 

872 T1.discard(new_node1) 

873 T2.discard(new_node2) 

874 

875 T1_tilde.difference_update(uncovered_successors_G1) 

876 T2_tilde.difference_update(uncovered_successors_G2) 

877 T1_tilde.discard(new_node1) 

878 T2_tilde.discard(new_node2) 

879 

880 if not G1.is_directed(): 

881 return 

882 

883 uncovered_predecessors_G1 = { 

884 pred for pred in G1.pred[new_node1] if pred not in mapping 

885 } 

886 uncovered_predecessors_G2 = { 

887 pred for pred in G2.pred[new_node2] if pred not in reverse_mapping 

888 } 

889 

890 T1_in.update(uncovered_predecessors_G1) 

891 T2_in.update(uncovered_predecessors_G2) 

892 T1_in.discard(new_node1) 

893 T2_in.discard(new_node2) 

894 

895 T1_tilde.difference_update(uncovered_predecessors_G1) 

896 T2_tilde.difference_update(uncovered_predecessors_G2) 

897 T1_tilde.discard(new_node1) 

898 T2_tilde.discard(new_node2) 

899 

900 

901def _restore_Tinout(popped_node1, popped_node2, graph_params, state_params): 

902 """Restores the previous version of Ti/Ti_out when a node pair is deleted from the mapping. 

903 

904 Parameters 

905 ---------- 

906 popped_node1, popped_node2: Graph node 

907 The two nodes deleted from the mapping. 

908 

909 graph_params: namedtuple 

910 Contains all the Graph-related parameters: 

911 

912 G1,G2: NetworkX Graph or MultiGraph instances. 

913 The two graphs to check for isomorphism or monomorphism 

914 

915 G1_labels,G2_labels: dict 

916 The label of every node in G1 and G2 respectively 

917 

918 state_params: namedtuple 

919 Contains all the State-related parameters: 

920 

921 mapping: dict 

922 The mapping as extended so far. Maps nodes of G1 to nodes of G2 

923 

924 reverse_mapping: dict 

925 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1. It's basically "mapping" reversed 

926 

927 T1, T2: set 

928 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are 

929 neighbors of nodes that are. 

930 

931 T1_tilde, T2_tilde: set 

932 Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti 

933 """ 

934 # If the node we want to remove from the mapping, has at least one covered neighbor, add it to T1. 

935 G1, G2, _, _, _, _, _ = graph_params 

936 ( 

937 mapping, 

938 reverse_mapping, 

939 T1, 

940 T1_in, 

941 T1_tilde, 

942 T1_tilde_in, 

943 T2, 

944 T2_in, 

945 T2_tilde, 

946 T2_tilde_in, 

947 ) = state_params 

948 

949 is_added = False 

950 for neighbor in G1[popped_node1]: 

951 if neighbor in mapping: 

952 # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1 

953 is_added = True 

954 T1.add(popped_node1) 

955 else: 

956 # check if its neighbor has another connection with a covered node. If not, only then exclude it from T1 

957 if any(nbr in mapping for nbr in G1[neighbor]):