Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / isomorphism / vf2userfunc.py @ 5cef0f13

History | View | Annotate | Download (7.35 KB)

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
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