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"""
2Module to simplify the specification of user-defined equality functions for
3node and edge attributes during isomorphism checks.
5During the construction of an isomorphism, the algorithm considers two
6candidate nodes n1 in G1 and n2 in G2. The graphs G1 and G2 are then
7compared with respect to properties involving n1 and n2, and if the outcome
8is good, then the candidate nodes are considered isomorphic. NetworkX
9provides a simple mechanism for users to extend the comparisons to include
10node and edge attributes.
12Node attributes are handled by the node_match keyword. When considering
13n1 and n2, the algorithm passes their node attribute dictionaries to
14node_match, and if it returns False, then n1 and n2 cannot be
15considered to be isomorphic.
17Edge attributes are handled by the edge_match keyword. When considering
18n1 and n2, the algorithm must verify that outgoing edges from n1 are
19commensurate with the outgoing edges for n2. If the graph is directed,
20then a similar check is also performed for incoming edges.
22Focusing only on outgoing edges, we consider pairs of nodes (n1, v1) from
23G1 and (n2, v2) from G2. For graphs and digraphs, there is only one edge
24between (n1, v1) and only one edge between (n2, v2). Those edge attribute
25dictionaries are passed to edge_match, and if it returns False, then
26n1 and n2 cannot be considered isomorphic. For multigraphs and
27multidigraphs, there can be multiple edges between (n1, v1) and also
28multiple edges between (n2, v2). Now, there must exist an isomorphism
29from "all the edges between (n1, v1)" to "all the edges between (n2, v2)".
30So, all of the edge attribute dictionaries are passed to edge_match, and
31it must determine if there is an isomorphism between the two sets of edges.
32"""
34from . import isomorphvf2 as vf2
36__all__ = ["GraphMatcher", "DiGraphMatcher", "MultiGraphMatcher", "MultiDiGraphMatcher"]
39def _semantic_feasibility(self, G1_node, G2_node):
40 """Returns True if mapping G1_node to G2_node is semantically feasible."""
41 # Make sure the nodes match
42 if self.node_match is not None:
43 nm = self.node_match(self.G1.nodes[G1_node], self.G2.nodes[G2_node])
44 if not nm:
45 return False
47 # Make sure the edges match
48 if self.edge_match is not None:
49 # Cached lookups
50 G1nbrs = self.G1_adj[G1_node]
51 G2nbrs = self.G2_adj[G2_node]
52 core_1 = self.core_1
53 edge_match = self.edge_match
55 for neighbor in G1nbrs:
56 # G1_node is not in core_1, so we must handle R_self separately
57 if neighbor == G1_node:
58 if G2_node in G2nbrs and not edge_match(
59 G1nbrs[G1_node], G2nbrs[G2_node]
60 ):
61 return False
62 elif neighbor in core_1:
63 G2_nbr = core_1[neighbor]
64 if G2_nbr in G2nbrs and not edge_match(
65 G1nbrs[neighbor], G2nbrs[G2_nbr]
66 ):
67 return False
68 # syntactic check has already verified that neighbors are symmetric
70 return True
73class GraphMatcher(vf2.GraphMatcher):
74 """VF2 isomorphism checker for undirected graphs."""
76 def __init__(self, G1, G2, node_match=None, edge_match=None):
77 """Initialize graph matcher.
79 Parameters
80 ----------
81 G1, G2: graph
82 The graphs to be tested.
84 node_match: callable
85 A function that returns True iff node n1 in G1 and n2 in G2
86 should be considered equal during the isomorphism test. The
87 function will be called like::
89 node_match(G1.nodes[n1], G2.nodes[n2])
91 That is, the function will receive the node attribute dictionaries
92 of the nodes under consideration. If None, then no attributes are
93 considered when testing for an isomorphism.
95 edge_match: callable
96 A function that returns True iff the edge attribute dictionary for
97 the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be
98 considered equal during the isomorphism test. The function will be
99 called like::
101 edge_match(G1[u1][v1], G2[u2][v2])
103 That is, the function will receive the edge attribute dictionaries
104 of the edges under consideration. If None, then no attributes are
105 considered when testing for an isomorphism.
107 """
108 vf2.GraphMatcher.__init__(self, G1, G2)
110 self.node_match = node_match
111 self.edge_match = edge_match
113 # These will be modified during checks to minimize code repeat.
114 self.G1_adj = self.G1.adj
115 self.G2_adj = self.G2.adj
117 semantic_feasibility = _semantic_feasibility
120class DiGraphMatcher(vf2.DiGraphMatcher):
121 """VF2 isomorphism checker for directed graphs."""
123 def __init__(self, G1, G2, node_match=None, edge_match=None):
124 """Initialize graph matcher.
126 Parameters
127 ----------
128 G1, G2 : graph
129 The graphs to be tested.
131 node_match : callable
132 A function that returns True iff node n1 in G1 and n2 in G2
133 should be considered equal during the isomorphism test. The
134 function will be called like::
136 node_match(G1.nodes[n1], G2.nodes[n2])
138 That is, the function will receive the node attribute dictionaries
139 of the nodes under consideration. If None, then no attributes are
140 considered when testing for an isomorphism.
142 edge_match : callable
143 A function that returns True iff the edge attribute dictionary for
144 the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be
145 considered equal during the isomorphism test. The function will be
146 called like::
148 edge_match(G1[u1][v1], G2[u2][v2])
150 That is, the function will receive the edge attribute dictionaries
151 of the edges under consideration. If None, then no attributes are
152 considered when testing for an isomorphism.
154 """
155 vf2.DiGraphMatcher.__init__(self, G1, G2)
157 self.node_match = node_match
158 self.edge_match = edge_match
160 # These will be modified during checks to minimize code repeat.
161 self.G1_adj = self.G1.adj
162 self.G2_adj = self.G2.adj
164 def semantic_feasibility(self, G1_node, G2_node):
165 """Returns True if mapping G1_node to G2_node is semantically feasible."""
167 # Test node_match and also test edge_match on successors
168 feasible = _semantic_feasibility(self, G1_node, G2_node)
169 if not feasible:
170 return False
172 # Test edge_match on predecessors
173 self.G1_adj = self.G1.pred
174 self.G2_adj = self.G2.pred
175 feasible = _semantic_feasibility(self, G1_node, G2_node)
176 self.G1_adj = self.G1.adj
177 self.G2_adj = self.G2.adj
179 return feasible
182# The "semantics" of edge_match are different for multi(di)graphs, but
183# the implementation is the same. So, technically we do not need to
184# provide "multi" versions, but we do so to match NetworkX's base classes.
187class MultiGraphMatcher(GraphMatcher):
188 """VF2 isomorphism checker for undirected multigraphs."""
191class MultiDiGraphMatcher(DiGraphMatcher):
192 """VF2 isomorphism checker for directed multigraphs."""