ioftools / networkxMiCe / networkxmaster / networkx / algorithms / isomorphism / vf2userfunc.py @ 5cef0f13
History  View  Annotate  Download (7.35 KB)
1 
"""


2 
Module to simplify the specification of userdefined 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 
import networkx as nx 
35 
from . import isomorphvf2 as vf2 
36  
37 
__all__ = ['GraphMatcher',

38 
'DiGraphMatcher',

39 
'MultiGraphMatcher',

40 
'MultiDiGraphMatcher',

41 
] 
42  
43  
44 
def _semantic_feasibility(self, G1_node, G2_node): 
45 
"""Returns True if mapping G1_node to G2_node is semantically feasible.

46 
"""

47 
# Make sure the nodes match

48 
if self.node_match is not None: 
49 
nm = self.node_match(self.G1.nodes[G1_node], self.G2.nodes[G2_node]) 
50 
if not nm: 
51 
return False 
52  
53 
# Make sure the edges match

54 
if self.edge_match is not None: 
55  
56 
# Cached lookups

57 
G1_adj = self.G1_adj

58 
G2_adj = self.G2_adj

59 
core_1 = self.core_1

60 
edge_match = self.edge_match

61  
62 
for neighbor in G1_adj[G1_node]: 
63 
# G1_node is not in core_1, so we must handle R_self separately

64 
if neighbor == G1_node:

65 
if not edge_match(G1_adj[G1_node][G1_node], 
66 
G2_adj[G2_node][G2_node]): 
67 
return False 
68 
elif neighbor in core_1: 
69 
if not edge_match(G1_adj[G1_node][neighbor], 
70 
G2_adj[G2_node][core_1[neighbor]]): 
71 
return False 
72 
# syntactic check has already verified that neighbors are symmetric

73  
74 
return True 
75  
76  
77 
class GraphMatcher(vf2.GraphMatcher): 
78 
"""VF2 isomorphism checker for undirected graphs.

79 
"""

80  
81 
def __init__(self, G1, G2, node_match=None, edge_match=None): 
82 
"""Initialize graph matcher.

83 

84 
Parameters

85 


86 
G1, G2: graph

87 
The graphs to be tested.

88 

89 
node_match: callable

90 
A function that returns True iff node n1 in G1 and n2 in G2

91 
should be considered equal during the isomorphism test. The

92 
function will be called like::

93 

94 
node_match(G1.nodes[n1], G2.nodes[n2])

95 

96 
That is, the function will receive the node attribute dictionaries

97 
of the nodes under consideration. If None, then no attributes are

98 
considered when testing for an isomorphism.

99 

100 
edge_match: callable

101 
A function that returns True iff the edge attribute dictionary for

102 
the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be

103 
considered equal during the isomorphism test. The function will be

104 
called like::

105 

106 
edge_match(G1[u1][v1], G2[u2][v2])

107 

108 
That is, the function will receive the edge attribute dictionaries

109 
of the edges under consideration. If None, then no attributes are

110 
considered when testing for an isomorphism.

111 

112 
"""

113 
vf2.GraphMatcher.__init__(self, G1, G2)

114  
115 
self.node_match = node_match

116 
self.edge_match = edge_match

117  
118 
# These will be modified during checks to minimize code repeat.

119 
self.G1_adj = self.G1.adj 
120 
self.G2_adj = self.G2.adj 
121  
122 
semantic_feasibility = _semantic_feasibility 
123  
124  
125 
class DiGraphMatcher(vf2.DiGraphMatcher): 
126 
"""VF2 isomorphism checker for directed graphs.

127 
"""

128  
129 
def __init__(self, G1, G2, node_match=None, edge_match=None): 
130 
"""Initialize graph matcher.

131 

132 
Parameters

133 


134 
G1, G2 : graph

135 
The graphs to be tested.

136 

137 
node_match : callable

138 
A function that returns True iff node n1 in G1 and n2 in G2

139 
should be considered equal during the isomorphism test. The

140 
function will be called like::

141 

142 
node_match(G1.nodes[n1], G2.nodes[n2])

143 

144 
That is, the function will receive the node attribute dictionaries

145 
of the nodes under consideration. If None, then no attributes are

146 
considered when testing for an isomorphism.

147 

148 
edge_match : callable

149 
A function that returns True iff the edge attribute dictionary for

150 
the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be

151 
considered equal during the isomorphism test. The function will be

152 
called like::

153 

154 
edge_match(G1[u1][v1], G2[u2][v2])

155 

156 
That is, the function will receive the edge attribute dictionaries

157 
of the edges under consideration. If None, then no attributes are

158 
considered when testing for an isomorphism.

159 

160 
"""

161 
vf2.DiGraphMatcher.__init__(self, G1, G2)

162  
163 
self.node_match = node_match

164 
self.edge_match = edge_match

165  
166 
# These will be modified during checks to minimize code repeat.

167 
self.G1_adj = self.G1.adj 
168 
self.G2_adj = self.G2.adj 
169  
170 
def semantic_feasibility(self, G1_node, G2_node): 
171 
"""Returns True if mapping G1_node to G2_node is semantically feasible."""

172  
173 
# Test node_match and also test edge_match on successors

174 
feasible = _semantic_feasibility(self, G1_node, G2_node)

175 
if not feasible: 
176 
return False 
177  
178 
# Test edge_match on predecessors

179 
self.G1_adj = self.G1.pred 
180 
self.G2_adj = self.G2.pred 
181 
feasible = _semantic_feasibility(self, G1_node, G2_node)

182 
self.G1_adj = self.G1.adj 
183 
self.G2_adj = self.G2.adj 
184  
185 
return feasible

186  
187 
# The "semantics" of edge_match are different for multi(di)graphs, but

188 
# the implementation is the same. So, technically we do not need to

189 
# provide "multi" versions, but we do so to match NetworkX's base classes.

190  
191  
192 
class MultiGraphMatcher(GraphMatcher): 
193 
"""VF2 isomorphism checker for undirected multigraphs. """

194 
pass

195  
196  
197 
class MultiDiGraphMatcher(DiGraphMatcher): 
198 
"""VF2 isomorphism checker for directed multigraphs. """

199 
pass
