Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2***************
3VF2++ Algorithm
4***************
6An implementation of the VF2++ algorithm [1]_ for Graph Isomorphism testing.
8The simplest interface to use this module is to call:
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.
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.
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.
30Examples
31--------
33Suppose G1 and G2 are Isomorphic Graphs. Verification is as follows:
35Without node labels:
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}
45With node labels:
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(
51... G1, dict(zip(G1, ["blue", "red", "green", "yellow"])), "label"
52... )
53>>> nx.set_node_attributes(
54... G2,
55... dict(zip([mapped[u] for u in G1], ["blue", "red", "green", "yellow"])),
56... "label",
57... )
58>>> nx.vf2pp_is_isomorphic(G1, G2, node_label="label")
59True
60>>> nx.vf2pp_isomorphism(G1, G2, node_label="label")
61{1: 1, 2: 2, 0: 0, 3: 3}
63References
64----------
65.. [1] Jüttner, Alpár & Madarasi, Péter. (2018). "VF2++—An improved subgraph
66 isomorphism algorithm". Discrete Applied Mathematics. 242.
67 https://doi.org/10.1016/j.dam.2018.02.018
69"""
71import collections
73import networkx as nx
75__all__ = ["vf2pp_isomorphism", "vf2pp_is_isomorphic", "vf2pp_all_isomorphisms"]
77_GraphParameters = collections.namedtuple(
78 "_GraphParameters",
79 [
80 "G1",
81 "G2",
82 "G1_labels",
83 "G2_labels",
84 "nodes_of_G1Labels",
85 "nodes_of_G2Labels",
86 "G2_nodes_of_degree",
87 ],
88)
90_StateParameters = collections.namedtuple(
91 "_StateParameters",
92 [
93 "mapping",
94 "reverse_mapping",
95 "T1",
96 "T1_in",
97 "T1_tilde",
98 "T1_tilde_in",
99 "T2",
100 "T2_in",
101 "T2_tilde",
102 "T2_tilde_in",
103 ],
104)
107@nx._dispatchable(graphs={"G1": 0, "G2": 1}, node_attrs={"node_label": "default_label"})
108def vf2pp_isomorphism(G1, G2, node_label=None, default_label=None):
109 """Return an isomorphic mapping between `G1` and `G2` if it exists.
111 Parameters
112 ----------
113 G1, G2 : NetworkX Graph or MultiGraph instances.
114 The two graphs to check for isomorphism.
116 node_label : str, optional
117 The name of the node attribute to be used when comparing nodes.
118 The default is `None`, meaning node attributes are not considered
119 in the comparison. Any node that doesn't have the `node_label`
120 attribute uses `default_label` instead.
122 default_label : scalar
123 Default value to use when a node doesn't have an attribute
124 named `node_label`. Default is `None`.
126 Returns
127 -------
128 dict or None
129 Node mapping if the two graphs are isomorphic. None otherwise.
130 """
131 try:
132 mapping = next(vf2pp_all_isomorphisms(G1, G2, node_label, default_label))
133 return mapping
134 except StopIteration:
135 return None
138@nx._dispatchable(graphs={"G1": 0, "G2": 1}, node_attrs={"node_label": "default_label"})
139def vf2pp_is_isomorphic(G1, G2, node_label=None, default_label=None):
140 """Examines whether G1 and G2 are isomorphic.
142 Parameters
143 ----------
144 G1, G2 : NetworkX Graph or MultiGraph instances.
145 The two graphs to check for isomorphism.
147 node_label : str, optional
148 The name of the node attribute to be used when comparing nodes.
149 The default is `None`, meaning node attributes are not considered
150 in the comparison. Any node that doesn't have the `node_label`
151 attribute uses `default_label` instead.
153 default_label : scalar
154 Default value to use when a node doesn't have an attribute
155 named `node_label`. Default is `None`.
157 Returns
158 -------
159 bool
160 True if the two graphs are isomorphic, False otherwise.
161 """
162 if vf2pp_isomorphism(G1, G2, node_label, default_label) is not None:
163 return True
164 return False
167@nx._dispatchable(graphs={"G1": 0, "G2": 1}, node_attrs={"node_label": "default_label"})
168def vf2pp_all_isomorphisms(G1, G2, node_label=None, default_label=None):
169 """Yields all the possible mappings between G1 and G2.
171 Parameters
172 ----------
173 G1, G2 : NetworkX Graph or MultiGraph instances.
174 The two graphs to check for isomorphism.
176 node_label : str, optional
177 The name of the node attribute to be used when comparing nodes.
178 The default is `None`, meaning node attributes are not considered
179 in the comparison. Any node that doesn't have the `node_label`
180 attribute uses `default_label` instead.
182 default_label : scalar
183 Default value to use when a node doesn't have an attribute
184 named `node_label`. Default is `None`.
186 Yields
187 ------
188 dict
189 Isomorphic mapping between the nodes in `G1` and `G2`.
190 """
191 if G1.number_of_nodes() == 0 or G2.number_of_nodes() == 0:
192 return False
194 # Create the degree dicts based on graph type
195 if G1.is_directed():
196 G1_degree = {
197 n: (in_degree, out_degree)
198 for (n, in_degree), (_, out_degree) in zip(G1.in_degree, G1.out_degree)
199 }
200 G2_degree = {
201 n: (in_degree, out_degree)
202 for (n, in_degree), (_, out_degree) in zip(G2.in_degree, G2.out_degree)
203 }
204 else:
205 G1_degree = dict(G1.degree)
206 G2_degree = dict(G2.degree)
208 if not G1.is_directed():
209 find_candidates = _find_candidates
210 restore_Tinout = _restore_Tinout
211 else:
212 find_candidates = _find_candidates_Di
213 restore_Tinout = _restore_Tinout_Di
215 # Check that both graphs have the same number of nodes and degree sequence
216 if G1.order() != G2.order():
217 return False
218 if sorted(G1_degree.values()) != sorted(G2_degree.values()):
219 return False
221 # Initialize parameters and cache necessary information about degree and labels
222 graph_params, state_params = _initialize_parameters(
223 G1, G2, G2_degree, node_label, default_label
224 )
226 # Check if G1 and G2 have the same labels, and that number of nodes per label
227 # is equal between the two graphs
228 if not _precheck_label_properties(graph_params):
229 return False
231 # Calculate the optimal node ordering
232 node_order = _matching_order(graph_params)
234 # Initialize the stack
235 stack = []
236 candidates = iter(
237 find_candidates(node_order[0], graph_params, state_params, G1_degree)
238 )
239 stack.append((node_order[0], candidates))
241 mapping = state_params.mapping
242 reverse_mapping = state_params.reverse_mapping
244 # Index of the node from the order, currently being examined
245 matching_node = 1
247 while stack:
248 current_node, candidate_nodes = stack[-1]
250 try:
251 candidate = next(candidate_nodes)
252 except StopIteration:
253 # If no remaining candidates, return to a previous state, and follow another branch
254 stack.pop()
255 matching_node -= 1
256 if stack:
257 # Pop the previously added u-v pair, and look for a different candidate _v for u
258 popped_node1, _ = stack[-1]
259 popped_node2 = mapping[popped_node1]
260 mapping.pop(popped_node1)
261 reverse_mapping.pop(popped_node2)
262 restore_Tinout(popped_node1, popped_node2, graph_params, state_params)
263 continue
265 if _feasibility(current_node, candidate, graph_params, state_params):
266 # Terminate if mapping is extended to its full
267 if len(mapping) == G2.number_of_nodes() - 1:
268 cp_mapping = mapping.copy()
269 cp_mapping[current_node] = candidate
270 yield cp_mapping
271 continue
273 # Feasibility rules pass, so extend the mapping and update the parameters
274 mapping[current_node] = candidate
275 reverse_mapping[candidate] = current_node
276 _update_Tinout(current_node, candidate, graph_params, state_params)
277 # Append the next node and its candidates to the stack
278 candidates = iter(
279 find_candidates(
280 node_order[matching_node], graph_params, state_params, G1_degree
281 )
282 )
283 stack.append((node_order[matching_node], candidates))
284 matching_node += 1
287def _precheck_label_properties(graph_params):
288 G1, G2, G1_labels, G2_labels, nodes_of_G1Labels, nodes_of_G2Labels, _ = graph_params
289 if any(
290 label not in nodes_of_G1Labels or len(nodes_of_G1Labels[label]) != len(nodes)
291 for label, nodes in nodes_of_G2Labels.items()
292 ):
293 return False
294 return True
297def _initialize_parameters(G1, G2, G2_degree, node_label=None, default_label=-1):
298 """Initializes all the necessary parameters for VF2++
300 Parameters
301 ----------
302 G1,G2: NetworkX Graph or MultiGraph instances.
303 The two graphs to check for isomorphism or monomorphism
305 G1_labels,G2_labels: dict
306 The label of every node in G1 and G2 respectively
308 Returns
309 -------
310 graph_params: namedtuple
311 Contains all the Graph-related parameters:
313 G1,G2
314 G1_labels,G2_labels: dict
316 state_params: namedtuple
317 Contains all the State-related parameters:
319 mapping: dict
320 The mapping as extended so far. Maps nodes of G1 to nodes of G2
322 reverse_mapping: dict
323 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1.
324 It's basically "mapping" reversed
326 T1, T2: set
327 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes
328 that are not in the mapping, but are neighbors of nodes that are.
330 T1_out, T2_out: set
331 Ti_out contains all the nodes from Gi, that are neither in the mapping
332 nor in Ti
333 """
334 G1_labels = dict(G1.nodes(data=node_label, default=default_label))
335 G2_labels = dict(G2.nodes(data=node_label, default=default_label))
337 graph_params = _GraphParameters(
338 G1,
339 G2,
340 G1_labels,
341 G2_labels,
342 nx.utils.groups(G1_labels),
343 nx.utils.groups(G2_labels),
344 nx.utils.groups(G2_degree),
345 )
347 T1, T1_in = set(), set()
348 T2, T2_in = set(), set()
349 if G1.is_directed():
350 T1_tilde, T1_tilde_in = (
351 set(G1.nodes()),
352 set(),
353 ) # todo: do we need Ti_tilde_in? What nodes does it have?
354 T2_tilde, T2_tilde_in = set(G2.nodes()), set()
355 else:
356 T1_tilde, T1_tilde_in = set(G1.nodes()), set()
357 T2_tilde, T2_tilde_in = set(G2.nodes()), set()
359 state_params = _StateParameters(
360 {},
361 {},
362 T1,
363 T1_in,
364 T1_tilde,
365 T1_tilde_in,
366 T2,
367 T2_in,
368 T2_tilde,
369 T2_tilde_in,
370 )
372 return graph_params, state_params
375def _matching_order(graph_params):
376 """The node ordering as introduced in VF2++.
378 Notes
379 -----
380 Taking into account the structure of the Graph and the node labeling, the
381 nodes are placed in an order such that, most of the unfruitful/infeasible
382 branches of the search space can be pruned on high levels, significantly
383 decreasing the number of visited states. The premise is that, the algorithm
384 will be able to recognize inconsistencies early, proceeding to go deep into
385 the search tree only if it's needed.
387 Parameters
388 ----------
389 graph_params: namedtuple
390 Contains:
392 G1,G2: NetworkX Graph or MultiGraph instances.
393 The two graphs to check for isomorphism or monomorphism.
395 G1_labels,G2_labels: dict
396 The label of every node in G1 and G2 respectively.
398 Returns
399 -------
400 node_order: list
401 The ordering of the nodes.
402 """
403 G1, G2, G1_labels, _, _, nodes_of_G2Labels, _ = graph_params
404 if not G1 and not G2:
405 return {}
407 if G1.is_directed():
408 G1 = G1.to_undirected(as_view=True)
410 V1_unordered = set(G1.nodes())
411 label_rarity = {label: len(nodes) for label, nodes in nodes_of_G2Labels.items()}
412 used_degrees = {node: 0 for node in G1}
413 node_order = []
415 while V1_unordered:
416 max_rarity = min(label_rarity[G1_labels[x]] for x in V1_unordered)
417 rarest_nodes = [
418 n for n in V1_unordered if label_rarity[G1_labels[n]] == max_rarity
419 ]
420 max_node = max(rarest_nodes, key=G1.degree)
422 for dlevel_nodes in nx.bfs_layers(G1, max_node):
423 nodes_to_add = dlevel_nodes.copy()
424 while nodes_to_add:
425 max_used_degree = max(used_degrees[n] for n in nodes_to_add)
426 max_used_degree_nodes = [
427 n for n in nodes_to_add if used_degrees[n] == max_used_degree
428 ]
429 max_degree = max(G1.degree[n] for n in max_used_degree_nodes)
430 max_degree_nodes = [
431 n for n in max_used_degree_nodes if G1.degree[n] == max_degree
432 ]
433 next_node = min(
434 max_degree_nodes, key=lambda x: label_rarity[G1_labels[x]]
435 )
437 node_order.append(next_node)
438 for node in G1.neighbors(next_node):
439 used_degrees[node] += 1
441 nodes_to_add.remove(next_node)
442 label_rarity[G1_labels[next_node]] -= 1
443 V1_unordered.discard(next_node)
445 return node_order
448def _find_candidates(
449 u, graph_params, state_params, G1_degree
450): # todo: make the 4th argument the degree of u
451 """Given node u of G1, finds the candidates of u from G2.
453 Parameters
454 ----------
455 u: Graph node
456 The node from G1 for which to find the candidates from G2.
458 graph_params: namedtuple
459 Contains all the Graph-related parameters:
461 G1,G2: NetworkX Graph or MultiGraph instances.
462 The two graphs to check for isomorphism or monomorphism
464 G1_labels,G2_labels: dict
465 The label of every node in G1 and G2 respectively
467 state_params: namedtuple
468 Contains all the State-related parameters:
470 mapping: dict
471 The mapping as extended so far. Maps nodes of G1 to nodes of G2
473 reverse_mapping: dict
474 The reverse mapping as extended so far. Maps nodes from G2 to nodes
475 of G1. It's basically "mapping" reversed
477 T1, T2: set
478 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes
479 that are not in the mapping, but are neighbors of nodes that are.
481 T1_tilde, T2_tilde: set
482 Ti_tilde contains all the nodes from Gi, that are neither in the
483 mapping nor in Ti
485 Returns
486 -------
487 candidates: set
488 The nodes from G2 which are candidates for u.
489 """
490 G1, G2, G1_labels, _, _, nodes_of_G2Labels, G2_nodes_of_degree = graph_params
491 mapping, reverse_mapping, _, _, _, _, _, _, T2_tilde, _ = state_params
493 covered_nbrs = [nbr for nbr in G1[u] if nbr in mapping]
494 if not covered_nbrs:
495 candidates = set(nodes_of_G2Labels[G1_labels[u]])
496 candidates.intersection_update(G2_nodes_of_degree[G1_degree[u]])
497 candidates.intersection_update(T2_tilde)
498 candidates.difference_update(reverse_mapping)
499 if G1.is_multigraph():
500 candidates.difference_update(
501 {
502 node
503 for node in candidates
504 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node)
505 }
506 )
507 return candidates
509 nbr1 = covered_nbrs[0]
510 common_nodes = set(G2[mapping[nbr1]])
512 for nbr1 in covered_nbrs[1:]:
513 common_nodes.intersection_update(G2[mapping[nbr1]])
515 common_nodes.difference_update(reverse_mapping)
516 common_nodes.intersection_update(G2_nodes_of_degree[G1_degree[u]])
517 common_nodes.intersection_update(nodes_of_G2Labels[G1_labels[u]])
518 if G1.is_multigraph():
519 common_nodes.difference_update(
520 {
521 node
522 for node in common_nodes
523 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node)
524 }
525 )
526 return common_nodes
529def _find_candidates_Di(u, graph_params, state_params, G1_degree):
530 G1, G2, G1_labels, _, _, nodes_of_G2Labels, G2_nodes_of_degree = graph_params
531 mapping, reverse_mapping, _, _, _, _, _, _, T2_tilde, _ = state_params
533 covered_successors = [succ for succ in G1[u] if succ in mapping]
534 covered_predecessors = [pred for pred in G1.pred[u] if pred in mapping]
536 if not (covered_successors or covered_predecessors):
537 candidates = set(nodes_of_G2Labels[G1_labels[u]])
538 candidates.intersection_update(G2_nodes_of_degree[G1_degree[u]])
539 candidates.intersection_update(T2_tilde)
540 candidates.difference_update(reverse_mapping)
541 if G1.is_multigraph():
542 candidates.difference_update(
543 {
544 node
545 for node in candidates
546 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node)
547 }
548 )
549 return candidates
551 if covered_successors:
552 succ1 = covered_successors[0]
553 common_nodes = set(G2.pred[mapping[succ1]])
555 for succ1 in covered_successors[1:]:
556 common_nodes.intersection_update(G2.pred[mapping[succ1]])
557 else:
558 pred1 = covered_predecessors.pop()
559 common_nodes = set(G2[mapping[pred1]])
561 for pred1 in covered_predecessors:
562 common_nodes.intersection_update(G2[mapping[pred1]])
564 common_nodes.difference_update(reverse_mapping)
565 common_nodes.intersection_update(G2_nodes_of_degree[G1_degree[u]])
566 common_nodes.intersection_update(nodes_of_G2Labels[G1_labels[u]])
567 if G1.is_multigraph():
568 common_nodes.difference_update(
569 {
570 node
571 for node in common_nodes
572 if G1.number_of_edges(u, u) != G2.number_of_edges(node, node)
573 }
574 )
575 return common_nodes
578def _feasibility(node1, node2, graph_params, state_params):
579 """Given a candidate pair of nodes u and v from G1 and G2 respectively,
580 checks if it's feasible to extend the mapping, i.e. if u and v can be matched.
582 Notes
583 -----
584 This function performs all the necessary checking by applying both consistency
585 and cutting rules.
587 Parameters
588 ----------
589 node1, node2: Graph node
590 The candidate pair of nodes being checked for matching
592 graph_params: namedtuple
593 Contains all the Graph-related parameters:
595 G1,G2: NetworkX Graph or MultiGraph instances.
596 The two graphs to check for isomorphism or monomorphism
598 G1_labels,G2_labels: dict
599 The label of every node in G1 and G2 respectively
601 state_params: namedtuple
602 Contains all the State-related parameters:
604 mapping: dict
605 The mapping as extended so far. Maps nodes of G1 to nodes of G2
607 reverse_mapping: dict
608 The reverse mapping as extended so far. Maps nodes from G2 to nodes
609 of G1. It's basically "mapping" reversed
611 T1, T2: set
612 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes
613 that are not in the mapping, but are neighbors of nodes that are.
615 T1_out, T2_out: set
616 Ti_out contains all the nodes from Gi, that are neither in the mapping
617 nor in Ti
619 Returns
620 -------
621 True if all checks are successful, False otherwise.
622 """
623 G1 = graph_params.G1
625 if _cut_PT(node1, node2, graph_params, state_params):
626 return False
628 if G1.is_multigraph():
629 if not _consistent_PT(node1, node2, graph_params, state_params):
630 return False
632 return True
635def _cut_PT(u, v, graph_params, state_params):
636 """Implements the cutting rules for the ISO problem.
638 Parameters
639 ----------
640 u, v: Graph node
641 The two candidate nodes being examined.
643 graph_params: namedtuple
644 Contains all the Graph-related parameters:
646 G1,G2: NetworkX Graph or MultiGraph instances.
647 The two graphs to check for isomorphism or monomorphism
649 G1_labels,G2_labels: dict
650 The label of every node in G1 and G2 respectively
652 state_params: namedtuple
653 Contains all the State-related parameters:
655 mapping: dict
656 The mapping as extended so far. Maps nodes of G1 to nodes of G2
658 reverse_mapping: dict
659 The reverse mapping as extended so far. Maps nodes from G2 to nodes
660 of G1. It's basically "mapping" reversed
662 T1, T2: set
663 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes
664 that are not in the mapping, but are neighbors of nodes that are.
666 T1_tilde, T2_tilde: set
667 Ti_out contains all the nodes from Gi, that are neither in the
668 mapping nor in Ti
670 Returns
671 -------
672 True if we should prune this branch, i.e. the node pair failed the cutting checks. False otherwise.
673 """
674 G1, G2, G1_labels, G2_labels, _, _, _ = graph_params
675 (
676 _,
677 _,
678 T1,
679 T1_in,
680 T1_tilde,
681 _,
682 T2,
683 T2_in,
684 T2_tilde,
685 _,
686 ) = state_params
688 u_labels_predecessors, v_labels_predecessors = {}, {}
689 if G1.is_directed():
690 u_labels_predecessors = nx.utils.groups(
691 {n1: G1_labels[n1] for n1 in G1.pred[u]}
692 )
693 v_labels_predecessors = nx.utils.groups(
694 {n2: G2_labels[n2] for n2 in G2.pred[v]}
695 )
697 if set(u_labels_predecessors.keys()) != set(v_labels_predecessors.keys()):
698 return True
700 u_labels_successors = nx.utils.groups({n1: G1_labels[n1] for n1 in G1[u]})
701 v_labels_successors = nx.utils.groups({n2: G2_labels[n2] for n2 in G2[v]})
703 # if the neighbors of u, do not have the same labels as those of v, NOT feasible.
704 if set(u_labels_successors.keys()) != set(v_labels_successors.keys()):
705 return True
707 for label, G1_nbh in u_labels_successors.items():
708 G2_nbh = v_labels_successors[label]
710 if G1.is_multigraph():
711 # Check for every neighbor in the neighborhood, if u-nbr1 has same edges as v-nbr2
712 u_nbrs_edges = sorted(G1.number_of_edges(u, x) for x in G1_nbh)
713 v_nbrs_edges = sorted(G2.number_of_edges(v, x) for x in G2_nbh)
714 if any(
715 u_nbr_edges != v_nbr_edges
716 for u_nbr_edges, v_nbr_edges in zip(u_nbrs_edges, v_nbrs_edges)
717 ):
718 return True
720 if len(T1.intersection(G1_nbh)) != len(T2.intersection(G2_nbh)):
721 return True
722 if len(T1_tilde.intersection(G1_nbh)) != len(T2_tilde.intersection(G2_nbh)):
723 return True
724 if G1.is_directed() and len(T1_in.intersection(G1_nbh)) != len(
725 T2_in.intersection(G2_nbh)
726 ):
727 return True
729 if not G1.is_directed():
730 return False
732 for label, G1_pred in u_labels_predecessors.items():
733 G2_pred = v_labels_predecessors[label]
735 if G1.is_multigraph():
736 # Check for every neighbor in the neighborhood, if u-nbr1 has same edges as v-nbr2
737 u_pred_edges = sorted(G1.number_of_edges(u, x) for x in G1_pred)
738 v_pred_edges = sorted(G2.number_of_edges(v, x) for x in G2_pred)
739 if any(
740 u_nbr_edges != v_nbr_edges
741 for u_nbr_edges, v_nbr_edges in zip(u_pred_edges, v_pred_edges)
742 ):
743 return True
745 if len(T1.intersection(G1_pred)) != len(T2.intersection(G2_pred)):
746 return True
747 if len(T1_tilde.intersection(G1_pred)) != len(T2_tilde.intersection(G2_pred)):
748 return True
749 if len(T1_in.intersection(G1_pred)) != len(T2_in.intersection(G2_pred)):
750 return True
752 return False
755def _consistent_PT(u, v, graph_params, state_params):
756 """Checks the consistency of extending the mapping using the current node pair.
758 Parameters
759 ----------
760 u, v: Graph node
761 The two candidate nodes being examined.
763 graph_params: namedtuple
764 Contains all the Graph-related parameters:
766 G1,G2: NetworkX Graph or MultiGraph instances.
767 The two graphs to check for isomorphism or monomorphism
769 G1_labels,G2_labels: dict
770 The label of every node in G1 and G2 respectively
772 state_params: namedtuple
773 Contains all the State-related parameters:
775 mapping: dict
776 The mapping as extended so far. Maps nodes of G1 to nodes of G2
778 reverse_mapping: dict
779 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1.
780 It's basically "mapping" reversed
782 T1, T2: set
783 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes
784 that are not in the mapping, but are neighbors of nodes that are.
786 T1_out, T2_out: set
787 Ti_out contains all the nodes from Gi, that are neither in the mapping
788 nor in Ti
790 Returns
791 -------
792 True if the pair passes all the consistency checks successfully. False otherwise.
793 """
794 G1, G2 = graph_params.G1, graph_params.G2
795 mapping, reverse_mapping = state_params.mapping, state_params.reverse_mapping
797 for neighbor in G1[u]:
798 if neighbor in mapping:
799 if G1.number_of_edges(u, neighbor) != G2.number_of_edges(
800 v, mapping[neighbor]
801 ):
802 return False
804 for neighbor in G2[v]:
805 if neighbor in reverse_mapping:
806 if G1.number_of_edges(u, reverse_mapping[neighbor]) != G2.number_of_edges(
807 v, neighbor
808 ):
809 return False
811 if not G1.is_directed():
812 return True
814 for predecessor in G1.pred[u]:
815 if predecessor in mapping:
816 if G1.number_of_edges(predecessor, u) != G2.number_of_edges(
817 mapping[predecessor], v
818 ):
819 return False
821 for predecessor in G2.pred[v]:
822 if predecessor in reverse_mapping:
823 if G1.number_of_edges(
824 reverse_mapping[predecessor], u
825 ) != G2.number_of_edges(predecessor, v):
826 return False
828 return True
831def _update_Tinout(new_node1, new_node2, graph_params, state_params):
832 """Updates the Ti/Ti_out (i=1,2) when a new node pair u-v is added to the mapping.
834 Notes
835 -----
836 This function should be called right after the feasibility checks are passed,
837 and node1 is mapped to node2. The purpose of this function is to avoid brute
838 force computing of Ti/Ti_out by iterating over all nodes of the graph and
839 checking which nodes satisfy the necessary conditions. Instead, in every step
840 of the algorithm we focus exclusively on the two nodes that are being added
841 to the mapping, incrementally updating Ti/Ti_out.
843 Parameters
844 ----------
845 new_node1, new_node2: Graph node
846 The two new nodes, added to the mapping.
848 graph_params: namedtuple
849 Contains all the Graph-related parameters:
851 G1,G2: NetworkX Graph or MultiGraph instances.
852 The two graphs to check for isomorphism or monomorphism
854 G1_labels,G2_labels: dict
855 The label of every node in G1 and G2 respectively
857 state_params: namedtuple
858 Contains all the State-related parameters:
860 mapping: dict
861 The mapping as extended so far. Maps nodes of G1 to nodes of G2
863 reverse_mapping: dict
864 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1.
865 It's basically "mapping" reversed
867 T1, T2: set
868 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes
869 that are not in the mapping, but are neighbors of nodes that are.
871 T1_tilde, T2_tilde: set
872 Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti
873 """
874 G1, G2, _, _, _, _, _ = graph_params
875 (
876 mapping,
877 reverse_mapping,
878 T1,
879 T1_in,
880 T1_tilde,
881 T1_tilde_in,
882 T2,
883 T2_in,
884 T2_tilde,
885 T2_tilde_in,
886 ) = state_params
888 uncovered_successors_G1 = {succ for succ in G1[new_node1] if succ not in mapping}
889 uncovered_successors_G2 = {
890 succ for succ in G2[new_node2] if succ not in reverse_mapping
891 }
893 # Add the uncovered neighbors of node1 and node2 in T1 and T2 respectively
894 T1.update(uncovered_successors_G1)
895 T2.update(uncovered_successors_G2)
896 T1.discard(new_node1)
897 T2.discard(new_node2)
899 T1_tilde.difference_update(uncovered_successors_G1)
900 T2_tilde.difference_update(uncovered_successors_G2)
901 T1_tilde.discard(new_node1)
902 T2_tilde.discard(new_node2)
904 if not G1.is_directed():
905 return
907 uncovered_predecessors_G1 = {
908 pred for pred in G1.pred[new_node1] if pred not in mapping
909 }
910 uncovered_predecessors_G2 = {
911 pred for pred in G2.pred[new_node2] if pred not in reverse_mapping
912 }
914 T1_in.update(uncovered_predecessors_G1)
915 T2_in.update(uncovered_predecessors_G2)
916 T1_in.discard(new_node1)
917 T2_in.discard(new_node2)
919 T1_tilde.difference_update(uncovered_predecessors_G1)
920 T2_tilde.difference_update(uncovered_predecessors_G2)
921 T1_tilde.discard(new_node1)
922 T2_tilde.discard(new_node2)
925def _restore_Tinout(popped_node1, popped_node2, graph_params, state_params):
926 """Restores the previous version of Ti/Ti_out when a node pair is deleted
927 from the mapping.
929 Parameters
930 ----------
931 popped_node1, popped_node2: Graph node
932 The two nodes deleted from the mapping.
934 graph_params: namedtuple
935 Contains all the Graph-related parameters:
937 G1,G2: NetworkX Graph or MultiGraph instances.
938 The two graphs to check for isomorphism or monomorphism
940 G1_labels,G2_labels: dict
941 The label of every node in G1 and G2 respectively
943 state_params: namedtuple
944 Contains all the State-related parameters:
946 mapping: dict
947 The mapping as extended so far. Maps nodes of G1 to nodes of G2
949 reverse_mapping: dict
950 The reverse mapping as extended so far. Maps nodes from G2 to nodes of G1.
951 It's basically "mapping" reversed
953 T1, T2: set
954 Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes
955 that are not in the mapping, but are neighbors of nodes that are.
957 T1_tilde, T2_tilde: set
958 Ti_out contains all the nodes from Gi, that are neither in the mapping
959 nor in Ti
960 """
961 # If the node we want to remove from the mapping, has at least one covered
962 # neighbor, add it to T1.
963 G1, G2, _, _, _, _, _ = graph_params
964 (
965 mapping,
966 reverse_mapping,
967 T1,
968 T1_in,
969 T1_tilde,
970 T1_tilde_in,
971 T2,
972 T2_in,
973 T2_tilde,
974 T2_tilde_in,
975 ) = state_params
977 is_added = False
978 for neighbor in G1[popped_node1]:
979 if neighbor in mapping:
980 # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1
981 is_added = True
982 T1.add(popped_node1)
983 else:
984 # check if its neighbor has another connection with a covered node.
985 # If not, only then exclude it from T1
986 if any(nbr in mapping for nbr in G1[neighbor]):
987 continue
988 T1.discard(neighbor)
989 T1_tilde.add(neighbor)
991 # Case where the node is not present in neither the mapping nor T1.
992 # By definition, it should belong to T1_tilde
993 if not is_added:
994 T1_tilde.add(popped_node1)
996 is_added = False
997 for neighbor in G2[popped_node2]:
998 if neighbor in reverse_mapping:
999 is_added = True
1000 T2.add(popped_node2)
1001 else:
1002 if any(nbr in reverse_mapping for nbr in G2[neighbor]):
1003 continue
1004 T2.discard(neighbor)
1005 T2_tilde.add(neighbor)
1007 if not is_added:
1008 T2_tilde.add(popped_node2)
1011def _restore_Tinout_Di(popped_node1, popped_node2, graph_params, state_params):
1012 # If the node we want to remove from the mapping, has at least one covered neighbor, add it to T1.
1013 G1, G2, _, _, _, _, _ = graph_params
1014 (
1015 mapping,
1016 reverse_mapping,
1017 T1,
1018 T1_in,
1019 T1_tilde,
1020 T1_tilde_in,
1021 T2,
1022 T2_in,
1023 T2_tilde,
1024 T2_tilde_in,
1025 ) = state_params
1027 is_added = False
1028 for successor in G1[popped_node1]:
1029 if successor in mapping:
1030 # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1
1031 is_added = True
1032 T1_in.add(popped_node1)
1033 else:
1034 # check if its neighbor has another connection with a covered node.
1035 # If not, only then exclude it from T1
1036 if not any(pred in mapping for pred in G1.pred[successor]):
1037 T1.discard(successor)
1039 if not any(succ in mapping for succ in G1[successor]):
1040 T1_in.discard(successor)
1042 if successor not in T1:
1043 if successor not in T1_in:
1044 T1_tilde.add(successor)
1046 for predecessor in G1.pred[popped_node1]:
1047 if predecessor in mapping:
1048 # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1
1049 is_added = True
1050 T1.add(popped_node1)
1051 else:
1052 # check if its neighbor has another connection with a covered node.
1053 # If not, only then exclude it from T1
1054 if not any(pred in mapping for pred in G1.pred[predecessor]):
1055 T1.discard(predecessor)
1057 if not any(succ in mapping for succ in G1[predecessor]):
1058 T1_in.discard(predecessor)
1060 if not (predecessor in T1 or predecessor in T1_in):
1061 T1_tilde.add(predecessor)
1063 # Case where the node is not present in neither the mapping nor T1.
1064 # By definition it should belong to T1_tilde
1065 if not is_added:
1066 T1_tilde.add(popped_node1)
1068 is_added = False
1069 for successor in G2[popped_node2]:
1070 if successor in reverse_mapping:
1071 is_added = True
1072 T2_in.add(popped_node2)
1073 else:
1074 if not any(pred in reverse_mapping for pred in G2.pred[successor]):
1075 T2.discard(successor)
1077 if not any(succ in reverse_mapping for succ in G2[successor]):
1078 T2_in.discard(successor)
1080 if successor not in T2:
1081 if successor not in T2_in:
1082 T2_tilde.add(successor)
1084 for predecessor in G2.pred[popped_node2]:
1085 if predecessor in reverse_mapping:
1086 # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1
1087 is_added = True
1088 T2.add(popped_node2)
1089 else:
1090 # check if its neighbor has another connection with a covered node.
1091 # If not, only then exclude it from T1
1092 if not any(pred in reverse_mapping for pred in G2.pred[predecessor]):
1093 T2.discard(predecessor)
1095 if not any(succ in reverse_mapping for succ in G2[predecessor]):
1096 T2_in.discard(predecessor)
1098 if not (predecessor in T2 or predecessor in T2_in):
1099 T2_tilde.add(predecessor)
1101 if not is_added:
1102 T2_tilde.add(popped_node2)