Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.8 KB)

1
"""
2
    Tests for VF2 isomorphism algorithm.
3
"""
4

    
5
import os
6
import struct
7
import random
8

    
9
from nose.tools import assert_true, assert_equal
10
from nose import SkipTest
11
import networkx as nx
12
from networkx.algorithms import isomorphism as iso
13

    
14

    
15
class TestWikipediaExample(object):
16
    # Source: https://en.wikipedia.org/wiki/Graph_isomorphism
17

    
18
    # Nodes 'a', 'b', 'c' and 'd' form a column.
19
    # Nodes 'g', 'h', 'i' and 'j' form a column.
20
    g1edges = [['a', 'g'], ['a', 'h'], ['a', 'i'],
21
               ['b', 'g'], ['b', 'h'], ['b', 'j'],
22
               ['c', 'g'], ['c', 'i'], ['c', 'j'],
23
               ['d', 'h'], ['d', 'i'], ['d', 'j']]
24

    
25
    # Nodes 1,2,3,4 form the clockwise corners of a large square.
26
    # Nodes 5,6,7,8 form the clockwise corners of a small square
27
    g2edges = [[1, 2], [2, 3], [3, 4], [4, 1],
28
               [5, 6], [6, 7], [7, 8], [8, 5],
29
               [1, 5], [2, 6], [3, 7], [4, 8]]
30

    
31
    def test_graph(self):
32
        g1 = nx.Graph()
33
        g2 = nx.Graph()
34
        g1.add_edges_from(self.g1edges)
35
        g2.add_edges_from(self.g2edges)
36
        gm = iso.GraphMatcher(g1, g2)
37
        assert_true(gm.is_isomorphic())
38
        #Just testing some cases
39
        assert_true(gm.subgraph_is_monomorphic())
40

    
41
        mapping = sorted(gm.mapping.items())
42
# this mapping is only one of the possibilies
43
# so this test needs to be reconsidered
44
#        isomap = [('a', 1), ('b', 6), ('c', 3), ('d', 8),
45
#                  ('g', 2), ('h', 5), ('i', 4), ('j', 7)]
46
#        assert_equal(mapping, isomap)
47

    
48
    def test_subgraph(self):
49
        g1 = nx.Graph()
50
        g2 = nx.Graph()
51
        g1.add_edges_from(self.g1edges)
52
        g2.add_edges_from(self.g2edges)
53
        g3 = g2.subgraph([1, 2, 3, 4])
54
        gm = iso.GraphMatcher(g1, g3)
55
        assert_true(gm.subgraph_is_isomorphic())
56

    
57

    
58
    def test_subgraph_mono(self):
59
        g1 = nx.Graph()
60
        g2 = nx.Graph()
61
        g1.add_edges_from(self.g1edges)
62
        g2.add_edges_from([[1, 2], [2, 3], [3, 4]])
63
        gm = iso.GraphMatcher(g1, g2)
64
        assert_true(gm.subgraph_is_monomorphic())
65

    
66

    
67
class TestVF2GraphDB(object):
68
    # http://amalfi.dis.unina.it/graph/db/
69

    
70
    @staticmethod
71
    def create_graph(filename):
72
        """Creates a Graph instance from the filename."""
73

    
74
        # The file is assumed to be in the format from the VF2 graph database.
75
        # Each file is composed of 16-bit numbers (unsigned short int).
76
        # So we will want to read 2 bytes at a time.
77

    
78
        # We can read the number as follows:
79
        #   number = struct.unpack('<H', file.read(2))
80
        # This says, expect the data in little-endian encoding
81
        # as an unsigned short int and unpack 2 bytes from the file.
82

    
83
        fh = open(filename, mode='rb')
84

    
85
        # Grab the number of nodes.
86
        # Node numeration is 0-based, so the first node has index 0.
87
        nodes = struct.unpack('<H', fh.read(2))[0]
88

    
89
        graph = nx.Graph()
90
        for from_node in range(nodes):
91
            # Get the number of edges.
92
            edges = struct.unpack('<H', fh.read(2))[0]
93
            for edge in range(edges):
94
                # Get the terminal node.
95
                to_node = struct.unpack('<H', fh.read(2))[0]
96
                graph.add_edge(from_node, to_node)
97

    
98
        fh.close()
99
        return graph
100

    
101
    def test_graph(self):
102
        head, tail = os.path.split(__file__)
103
        g1 = self.create_graph(os.path.join(head, 'iso_r01_s80.A99'))
104
        g2 = self.create_graph(os.path.join(head, 'iso_r01_s80.B99'))
105
        gm = iso.GraphMatcher(g1, g2)
106
        assert_true(gm.is_isomorphic())
107

    
108
    def test_subgraph(self):
109
        # A is the subgraph
110
        # B is the full graph
111
        head, tail = os.path.split(__file__)
112
        subgraph = self.create_graph(os.path.join(head, 'si2_b06_m200.A99'))
113
        graph = self.create_graph(os.path.join(head, 'si2_b06_m200.B99'))
114
        gm = iso.GraphMatcher(graph, subgraph)
115
        assert_true(gm.subgraph_is_isomorphic())
116
        #Just testing some cases
117
        assert_true(gm.subgraph_is_monomorphic())
118

    
119
        
120
    # There isn't a similar test implemented for subgraph monomorphism,
121
    # feel free to create one.
122

    
123

    
124
class TestAtlas(object):
125
    @classmethod
126
    def setupClass(cls):
127
        global atlas
128
        import platform
129
        if platform.python_implementation() == 'Jython':
130
            raise SkipTest('graph atlas not available under Jython.')
131
        import networkx.generators.atlas as atlas
132

    
133
    def setUp(self):
134
        self.GAG = atlas.graph_atlas_g()
135

    
136
    def test_graph_atlas(self):
137
        # Atlas = nx.graph_atlas_g()[0:208] # 208, 6 nodes or less
138
        Atlas = self.GAG[0:100]
139
        alphabet = list(range(26))
140
        for graph in Atlas:
141
            nlist = list(graph)
142
            labels = alphabet[:len(nlist)]
143
            for s in range(10):
144
                random.shuffle(labels)
145
                d = dict(zip(nlist, labels))
146
                relabel = nx.relabel_nodes(graph, d)
147
                gm = iso.GraphMatcher(graph, relabel)
148
                assert_true(gm.is_isomorphic())
149

    
150

    
151
def test_multiedge():
152
    # Simple test for multigraphs
153
    # Need something much more rigorous
154
    edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5),
155
             (5, 6), (6, 7), (7, 8), (8, 9), (9, 10),
156
             (10, 11), (10, 11), (11, 12), (11, 12),
157
             (12, 13), (12, 13), (13, 14), (13, 14),
158
             (14, 15), (14, 15), (15, 16), (15, 16),
159
             (16, 17), (16, 17), (17, 18), (17, 18),
160
             (18, 19), (18, 19), (19, 0), (19, 0)]
161
    nodes = list(range(20))
162

    
163
    for g1 in [nx.MultiGraph(), nx.MultiDiGraph()]:
164
        g1.add_edges_from(edges)
165
        for _ in range(10):
166
            new_nodes = list(nodes)
167
            random.shuffle(new_nodes)
168
            d = dict(zip(nodes, new_nodes))
169
            g2 = nx.relabel_nodes(g1, d)
170
            if not g1.is_directed():
171
                gm = iso.GraphMatcher(g1, g2)
172
            else:
173
                gm = iso.DiGraphMatcher(g1, g2)
174
            assert_true(gm.is_isomorphic())
175
            #Testing if monomorphism works in multigraphs
176
            assert_true(gm.subgraph_is_monomorphic())
177

    
178

    
179
def test_selfloop():
180
    # Simple test for graphs with selfloops
181
    edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 2),
182
             (2, 4), (3, 1), (3, 2), (4, 2), (4, 5), (5, 4)]
183
    nodes = list(range(6))
184

    
185
    for g1 in [nx.Graph(), nx.DiGraph()]:
186
        g1.add_edges_from(edges)
187
        for _ in range(100):
188
            new_nodes = list(nodes)
189
            random.shuffle(new_nodes)
190
            d = dict(zip(nodes, new_nodes))
191
            g2 = nx.relabel_nodes(g1, d)
192
            if not g1.is_directed():
193
                gm = iso.GraphMatcher(g1, g2)
194
            else:
195
                gm = iso.DiGraphMatcher(g1, g2)
196
            assert_true(gm.is_isomorphic())
197
            
198

    
199
def test_selfloop_mono():
200
    # Simple test for graphs with selfloops
201
    edges0 = [(0, 1), (0, 2), (1, 2), (1, 3),
202
             (2, 4), (3, 1), (3, 2), (4, 2), (4, 5), (5, 4)]
203
    edges = edges0 + [(2, 2)]
204
    nodes = list(range(6))
205

    
206
    for g1 in [nx.Graph(), nx.DiGraph()]:
207
        g1.add_edges_from(edges)
208
        for _ in range(100):
209
            new_nodes = list(nodes)
210
            random.shuffle(new_nodes)
211
            d = dict(zip(nodes, new_nodes))
212
            g2 = nx.relabel_nodes(g1, d)
213
            g2.remove_edges_from(g2.selfloop_edges())
214
            if not g1.is_directed():
215
                gm = iso.GraphMatcher(g2, g1)
216
            else:
217
                gm = iso.DiGraphMatcher(g2, g1)
218
            assert_true(not gm.subgraph_is_monomorphic())
219

    
220

    
221
def test_isomorphism_iter1():
222
    # As described in:
223
    # http://groups.google.com/group/networkx-discuss/browse_thread/thread/2ff65c67f5e3b99f/d674544ebea359bb?fwc=1
224
    g1 = nx.DiGraph()
225
    g2 = nx.DiGraph()
226
    g3 = nx.DiGraph()
227
    g1.add_edge('A', 'B')
228
    g1.add_edge('B', 'C')
229
    g2.add_edge('Y', 'Z')
230
    g3.add_edge('Z', 'Y')
231
    gm12 = iso.DiGraphMatcher(g1, g2)
232
    gm13 = iso.DiGraphMatcher(g1, g3)
233
    x = list(gm12.subgraph_isomorphisms_iter())
234
    y = list(gm13.subgraph_isomorphisms_iter())
235
    assert_true({'A': 'Y', 'B': 'Z'} in x)
236
    assert_true({'B': 'Y', 'C': 'Z'} in x)
237
    assert_true({'A': 'Z', 'B': 'Y'} in y)
238
    assert_true({'B': 'Z', 'C': 'Y'} in y)
239
    assert_equal(len(x), len(y))
240
    assert_equal(len(x), 2)
241

    
242

    
243
def test_monomorphism_iter1():
244
    g1 = nx.DiGraph()
245
    g2 = nx.DiGraph()
246
    g1.add_edge('A', 'B')
247
    g1.add_edge('B', 'C')
248
    g1.add_edge('C', 'A')
249
    g2.add_edge('X', 'Y')
250
    g2.add_edge('Y', 'Z')
251
    gm12 = iso.DiGraphMatcher(g1, g2)
252
    x = list(gm12.subgraph_monomorphisms_iter())
253
    assert_true({'A': 'X', 'B': 'Y', 'C': 'Z'} in x)
254
    assert_true({'A': 'Y', 'B': 'Z', 'C': 'X'} in x)
255
    assert_true({'A': 'Z', 'B': 'X', 'C': 'Y'} in x)
256
    assert_equal(len(x), 3)
257
    gm21 = iso.DiGraphMatcher(g2, g1)
258
    #Check if StopIteration exception returns False
259
    assert_true(not gm21.subgraph_is_monomorphic())
260

    
261

    
262
def test_isomorphism_iter2():
263
    # Path
264
    for L in range(2, 10):
265
        g1 = nx.path_graph(L)
266
        gm = iso.GraphMatcher(g1, g1)
267
        s = len(list(gm.isomorphisms_iter()))
268
        assert_equal(s, 2)
269
    # Cycle
270
    for L in range(3, 10):
271
        g1 = nx.cycle_graph(L)
272
        gm = iso.GraphMatcher(g1, g1)
273
        s = len(list(gm.isomorphisms_iter()))
274
        assert_equal(s, 2 * L)
275

    
276

    
277
def test_multiple():
278
    # Verify that we can use the graph matcher multiple times
279
    edges = [('A', 'B'), ('B', 'A'), ('B', 'C')]
280
    for g1, g2 in [(nx.Graph(), nx.Graph()), (nx.DiGraph(), nx.DiGraph())]:
281
        g1.add_edges_from(edges)
282
        g2.add_edges_from(edges)
283
        g3 = nx.subgraph(g2, ['A', 'B'])
284
        if not g1.is_directed():
285
            gmA = iso.GraphMatcher(g1, g2)
286
            gmB = iso.GraphMatcher(g1, g3)
287
        else:
288
            gmA = iso.DiGraphMatcher(g1, g2)
289
            gmB = iso.DiGraphMatcher(g1, g3)
290
        assert_true(gmA.is_isomorphic())
291
        g2.remove_node('C')
292
        if not g1.is_directed():
293
            gmA = iso.GraphMatcher(g1, g2)
294
        else:
295
            gmA = iso.DiGraphMatcher(g1, g2)
296
        assert_true(gmA.subgraph_is_isomorphic())
297
        assert_true(gmB.subgraph_is_isomorphic())
298
        assert_true(gmA.subgraph_is_monomorphic())
299
        assert_true(gmB.subgraph_is_monomorphic())
300
#        for m in [gmB.mapping, gmB.mapping]:
301
#            assert_true(m['A'] == 'A')
302
#            assert_true(m['B'] == 'B')
303
#            assert_true('C' not in m)
304

    
305
def test_noncomparable_nodes():
306
    node1 = object()
307
    node2 = object()
308
    node3 = object()
309

    
310
    # Graph
311
    G = nx.path_graph([node1, node2, node3])
312
    gm = iso.GraphMatcher(G, G)
313
    assert_true(gm.is_isomorphic())
314
    #Just testing some cases
315
    assert_true(gm.subgraph_is_monomorphic())
316

    
317
    # DiGraph
318
    G = nx.path_graph([node1, node2, node3], create_using=nx.DiGraph)
319
    H = nx.path_graph([node3, node2, node1], create_using=nx.DiGraph)
320
    dgm = iso.DiGraphMatcher(G, H)
321
    assert_true(dgm.is_isomorphic())
322
    #Just testing some cases
323
    assert_true(gm.subgraph_is_monomorphic())