Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/vf2userfunc.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Module to simplify the specification of user-defined equality functions for | |
3 node and edge attributes during isomorphism checks. | |
4 | |
5 During the construction of an isomorphism, the algorithm considers two | |
6 candidate nodes n1 in G1 and n2 in G2. The graphs G1 and G2 are then | |
7 compared with respect to properties involving n1 and n2, and if the outcome | |
8 is good, then the candidate nodes are considered isomorphic. NetworkX | |
9 provides a simple mechanism for users to extend the comparisons to include | |
10 node and edge attributes. | |
11 | |
12 Node attributes are handled by the node_match keyword. When considering | |
13 n1 and n2, the algorithm passes their node attribute dictionaries to | |
14 node_match, and if it returns False, then n1 and n2 cannot be | |
15 considered to be isomorphic. | |
16 | |
17 Edge attributes are handled by the edge_match keyword. When considering | |
18 n1 and n2, the algorithm must verify that outgoing edges from n1 are | |
19 commensurate with the outgoing edges for n2. If the graph is directed, | |
20 then a similar check is also performed for incoming edges. | |
21 | |
22 Focusing only on outgoing edges, we consider pairs of nodes (n1, v1) from | |
23 G1 and (n2, v2) from G2. For graphs and digraphs, there is only one edge | |
24 between (n1, v1) and only one edge between (n2, v2). Those edge attribute | |
25 dictionaries are passed to edge_match, and if it returns False, then | |
26 n1 and n2 cannot be considered isomorphic. For multigraphs and | |
27 multidigraphs, there can be multiple edges between (n1, v1) and also | |
28 multiple edges between (n2, v2). Now, there must exist an isomorphism | |
29 from "all the edges between (n1, v1)" to "all the edges between (n2, v2)". | |
30 So, all of the edge attribute dictionaries are passed to edge_match, and | |
31 it must determine if there is an isomorphism between the two sets of edges. | |
32 """ | |
33 | |
34 from . import isomorphvf2 as vf2 | |
35 | |
36 __all__ = ["GraphMatcher", "DiGraphMatcher", "MultiGraphMatcher", "MultiDiGraphMatcher"] | |
37 | |
38 | |
39 def _semantic_feasibility(self, G1_node, G2_node): | |
40 """Returns True if mapping G1_node to G2_node is semantically feasible. | |
41 """ | |
42 # Make sure the nodes match | |
43 if self.node_match is not None: | |
44 nm = self.node_match(self.G1.nodes[G1_node], self.G2.nodes[G2_node]) | |
45 if not nm: | |
46 return False | |
47 | |
48 # Make sure the edges match | |
49 if self.edge_match is not None: | |
50 | |
51 # Cached lookups | |
52 G1nbrs = self.G1_adj[G1_node] | |
53 G2nbrs = self.G2_adj[G2_node] | |
54 core_1 = self.core_1 | |
55 edge_match = self.edge_match | |
56 | |
57 for neighbor in G1nbrs: | |
58 # G1_node is not in core_1, so we must handle R_self separately | |
59 if neighbor == G1_node: | |
60 if G2_node in G2nbrs and not edge_match( | |
61 G1nbrs[G1_node], G2nbrs[G2_node] | |
62 ): | |
63 return False | |
64 elif neighbor in core_1: | |
65 G2_nbr = core_1[neighbor] | |
66 if G2_nbr in G2nbrs and not edge_match( | |
67 G1nbrs[neighbor], G2nbrs[G2_nbr] | |
68 ): | |
69 return False | |
70 # syntactic check has already verified that neighbors are symmetric | |
71 | |
72 return True | |
73 | |
74 | |
75 class GraphMatcher(vf2.GraphMatcher): | |
76 """VF2 isomorphism checker for undirected graphs. | |
77 """ | |
78 | |
79 def __init__(self, G1, G2, node_match=None, edge_match=None): | |
80 """Initialize graph matcher. | |
81 | |
82 Parameters | |
83 ---------- | |
84 G1, G2: graph | |
85 The graphs to be tested. | |
86 | |
87 node_match: callable | |
88 A function that returns True iff node n1 in G1 and n2 in G2 | |
89 should be considered equal during the isomorphism test. The | |
90 function will be called like:: | |
91 | |
92 node_match(G1.nodes[n1], G2.nodes[n2]) | |
93 | |
94 That is, the function will receive the node attribute dictionaries | |
95 of the nodes under consideration. If None, then no attributes are | |
96 considered when testing for an isomorphism. | |
97 | |
98 edge_match: callable | |
99 A function that returns True iff the edge attribute dictionary for | |
100 the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be | |
101 considered equal during the isomorphism test. The function will be | |
102 called like:: | |
103 | |
104 edge_match(G1[u1][v1], G2[u2][v2]) | |
105 | |
106 That is, the function will receive the edge attribute dictionaries | |
107 of the edges under consideration. If None, then no attributes are | |
108 considered when testing for an isomorphism. | |
109 | |
110 """ | |
111 vf2.GraphMatcher.__init__(self, G1, G2) | |
112 | |
113 self.node_match = node_match | |
114 self.edge_match = edge_match | |
115 | |
116 # These will be modified during checks to minimize code repeat. | |
117 self.G1_adj = self.G1.adj | |
118 self.G2_adj = self.G2.adj | |
119 | |
120 semantic_feasibility = _semantic_feasibility | |
121 | |
122 | |
123 class DiGraphMatcher(vf2.DiGraphMatcher): | |
124 """VF2 isomorphism checker for directed graphs. | |
125 """ | |
126 | |
127 def __init__(self, G1, G2, node_match=None, edge_match=None): | |
128 """Initialize graph matcher. | |
129 | |
130 Parameters | |
131 ---------- | |
132 G1, G2 : graph | |
133 The graphs to be tested. | |
134 | |
135 node_match : callable | |
136 A function that returns True iff node n1 in G1 and n2 in G2 | |
137 should be considered equal during the isomorphism test. The | |
138 function will be called like:: | |
139 | |
140 node_match(G1.nodes[n1], G2.nodes[n2]) | |
141 | |
142 That is, the function will receive the node attribute dictionaries | |
143 of the nodes under consideration. If None, then no attributes are | |
144 considered when testing for an isomorphism. | |
145 | |
146 edge_match : callable | |
147 A function that returns True iff the edge attribute dictionary for | |
148 the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be | |
149 considered equal during the isomorphism test. The function will be | |
150 called like:: | |
151 | |
152 edge_match(G1[u1][v1], G2[u2][v2]) | |
153 | |
154 That is, the function will receive the edge attribute dictionaries | |
155 of the edges under consideration. If None, then no attributes are | |
156 considered when testing for an isomorphism. | |
157 | |
158 """ | |
159 vf2.DiGraphMatcher.__init__(self, G1, G2) | |
160 | |
161 self.node_match = node_match | |
162 self.edge_match = edge_match | |
163 | |
164 # These will be modified during checks to minimize code repeat. | |
165 self.G1_adj = self.G1.adj | |
166 self.G2_adj = self.G2.adj | |
167 | |
168 def semantic_feasibility(self, G1_node, G2_node): | |
169 """Returns True if mapping G1_node to G2_node is semantically feasible.""" | |
170 | |
171 # Test node_match and also test edge_match on successors | |
172 feasible = _semantic_feasibility(self, G1_node, G2_node) | |
173 if not feasible: | |
174 return False | |
175 | |
176 # Test edge_match on predecessors | |
177 self.G1_adj = self.G1.pred | |
178 self.G2_adj = self.G2.pred | |
179 feasible = _semantic_feasibility(self, G1_node, G2_node) | |
180 self.G1_adj = self.G1.adj | |
181 self.G2_adj = self.G2.adj | |
182 | |
183 return feasible | |
184 | |
185 | |
186 # The "semantics" of edge_match are different for multi(di)graphs, but | |
187 # the implementation is the same. So, technically we do not need to | |
188 # provide "multi" versions, but we do so to match NetworkX's base classes. | |
189 | |
190 | |
191 class MultiGraphMatcher(GraphMatcher): | |
192 """VF2 isomorphism checker for undirected multigraphs. """ | |
193 | |
194 pass | |
195 | |
196 | |
197 class MultiDiGraphMatcher(DiGraphMatcher): | |
198 """VF2 isomorphism checker for directed multigraphs. """ | |
199 | |
200 pass |