Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (18.9 KB)

1
#!/usr/bin/env python
2
from nose.tools import *
3
from nose import SkipTest
4
import networkx as nx
5
from networkx.algorithms.similarity import *
6
from networkx.generators.classic import *
7

    
8

    
9
def nmatch(n1, n2):
10
    return n1 == n2
11

    
12
def ematch(e1, e2):
13
    return e1 == e2
14

    
15
def getCanonical():
16
    G = nx.Graph()
17
    G.add_node('A', label='A')
18
    G.add_node('B', label='B')
19
    G.add_node('C', label='C')
20
    G.add_node('D', label='D')
21
    G.add_edge('A', 'B', label='a-b')
22
    G.add_edge('B', 'C', label='b-c')
23
    G.add_edge('B', 'D', label='b-d')
24
    return G
25

    
26

    
27
class TestSimilarity:
28

    
29
    @classmethod
30
    def setupClass(cls):
31
        global numpy
32
        global scipy
33
        try:
34
            import numpy
35
        except ImportError:
36
            raise SkipTest('NumPy not available.')
37
        try:
38
            import scipy
39
        except ImportError:
40
            raise SkipTest('SciPy not available.')
41

    
42
    def test_graph_edit_distance(self):
43
        G0 = nx.Graph()
44
        G1 = path_graph(6)
45
        G2 = cycle_graph(6)
46
        G3 = wheel_graph(7)
47

    
48
        assert_equal(graph_edit_distance(G0, G0), 0)
49
        assert_equal(graph_edit_distance(G0, G1), 11)
50
        assert_equal(graph_edit_distance(G1, G0), 11)
51
        assert_equal(graph_edit_distance(G0, G2), 12)
52
        assert_equal(graph_edit_distance(G2, G0), 12)
53
        assert_equal(graph_edit_distance(G0, G3), 19)
54
        assert_equal(graph_edit_distance(G3, G0), 19)
55

    
56
        assert_equal(graph_edit_distance(G1, G1), 0)
57
        assert_equal(graph_edit_distance(G1, G2), 1)
58
        assert_equal(graph_edit_distance(G2, G1), 1)
59
        assert_equal(graph_edit_distance(G1, G3), 8)
60
        assert_equal(graph_edit_distance(G3, G1), 8)
61

    
62
        assert_equal(graph_edit_distance(G2, G2), 0)
63
        assert_equal(graph_edit_distance(G2, G3), 7)
64
        assert_equal(graph_edit_distance(G3, G2), 7)
65

    
66
        assert_equal(graph_edit_distance(G3, G3), 0)
67

    
68
    def test_graph_edit_distance_node_match(self):
69
        G1 = cycle_graph(5)
70
        G2 = cycle_graph(5)
71
        for n, attr in G1.nodes.items():
72
            attr['color'] = 'red' if n % 2 == 0 else 'blue'
73
        for n, attr in G2.nodes.items():
74
            attr['color'] = 'red' if n % 2 == 1 else 'blue'
75
        assert_equal(graph_edit_distance(G1, G2), 0)
76
        assert_equal(graph_edit_distance(G1, G2, node_match=lambda n1, n2: n1['color'] == n2['color']), 1)
77

    
78
    def test_graph_edit_distance_edge_match(self):
79
        G1 = path_graph(6)
80
        G2 = path_graph(6)
81
        for e, attr in G1.edges.items():
82
            attr['color'] = 'red' if min(e) % 2 == 0 else 'blue'
83
        for e, attr in G2.edges.items():
84
            attr['color'] = 'red' if min(e) // 3 == 0 else 'blue'
85
        assert_equal(graph_edit_distance(G1, G2), 0)
86
        assert_equal(graph_edit_distance(G1, G2, edge_match=lambda e1, e2: e1['color'] == e2['color']), 2)
87

    
88
    def test_graph_edit_distance_node_cost(self):
89
        G1 = path_graph(6)
90
        G2 = path_graph(6)
91
        for n, attr in G1.nodes.items():
92
            attr['color'] = 'red' if n % 2 == 0 else 'blue'
93
        for n, attr in G2.nodes.items():
94
            attr['color'] = 'red' if n % 2 == 1 else 'blue'
95

    
96
        def node_subst_cost(uattr, vattr):
97
            if uattr['color'] == vattr['color']:
98
                return 1
99
            else:
100
                return 10
101

    
102
        def node_del_cost(attr):
103
            if attr['color'] == 'blue':
104
                return 20
105
            else:
106
                return 50
107

    
108
        def node_ins_cost(attr):
109
            if attr['color'] == 'blue':
110
                return 40
111
            else:
112
                return 100
113

    
114
        assert_equal(graph_edit_distance(G1, G2,
115
                                         node_subst_cost=node_subst_cost,
116
                                         node_del_cost=node_del_cost,
117
                                         node_ins_cost=node_ins_cost), 6)
118

    
119
    def test_graph_edit_distance_edge_cost(self):
120
        G1 = path_graph(6)
121
        G2 = path_graph(6)
122
        for e, attr in G1.edges.items():
123
            attr['color'] = 'red' if min(e) % 2 == 0 else 'blue'
124
        for e, attr in G2.edges.items():
125
            attr['color'] = 'red' if min(e) // 3 == 0 else 'blue'
126

    
127
        def edge_subst_cost(gattr, hattr):
128
            if gattr['color'] == hattr['color']:
129
                return 0.01
130
            else:
131
                return 0.1
132

    
133
        def edge_del_cost(attr):
134
            if attr['color'] == 'blue':
135
                return 0.2
136
            else:
137
                return 0.5
138

    
139
        def edge_ins_cost(attr):
140
            if attr['color'] == 'blue':
141
                return 0.4
142
            else:
143
                return 1.0
144

    
145
        assert_equal(graph_edit_distance(G1, G2,
146
                                         edge_subst_cost=edge_subst_cost,
147
                                         edge_del_cost=edge_del_cost,
148
                                         edge_ins_cost=edge_ins_cost), 0.23)
149

    
150
    def test_graph_edit_distance_upper_bound(self):
151
        G1 = circular_ladder_graph(2)
152
        G2 = circular_ladder_graph(6)
153
        assert_equal(graph_edit_distance(G1, G2, upper_bound=5), None)
154
        assert_equal(graph_edit_distance(G1, G2, upper_bound=24), 22)
155
        assert_equal(graph_edit_distance(G1, G2), 22)
156

    
157
    def test_optimal_edit_paths(self):
158
        G1 = path_graph(3)
159
        G2 = cycle_graph(3)
160
        paths, cost = optimal_edit_paths(G1, G2)
161
        assert_equal(cost, 1)
162
        assert_equal(len(paths), 6)
163

    
164
        def canonical(vertex_path, edge_path):
165
            return tuple(sorted(vertex_path)), tuple(sorted(edge_path, key=lambda x: (None in x, x)))
166

    
167
        expected_paths = [([(0, 0), (1, 1), (2, 2)], [((0, 1), (0, 1)), ((1, 2), (1, 2)), (None, (0, 2))]),
168
                          ([(0, 0), (1, 2), (2, 1)], [((0, 1), (0, 2)), ((1, 2), (1, 2)), (None, (0, 1))]),
169
                          ([(0, 1), (1, 0), (2, 2)], [((0, 1), (0, 1)), ((1, 2), (0, 2)), (None, (1, 2))]),
170
                          ([(0, 1), (1, 2), (2, 0)], [((0, 1), (1, 2)), ((1, 2), (0, 2)), (None, (0, 1))]),
171
                          ([(0, 2), (1, 0), (2, 1)], [((0, 1), (0, 2)), ((1, 2), (0, 1)), (None, (1, 2))]),
172
                          ([(0, 2), (1, 1), (2, 0)], [((0, 1), (1, 2)), ((1, 2), (0, 1)), (None, (0, 2))])]
173
        assert_equal(set(canonical(*p) for p in paths),
174
                     set(canonical(*p) for p in expected_paths))
175

    
176
    def test_optimize_graph_edit_distance(self):
177
        G1 = circular_ladder_graph(2)
178
        G2 = circular_ladder_graph(6)
179
        bestcost = 1000
180
        for cost in optimize_graph_edit_distance(G1, G2):
181
            assert_less(cost, bestcost)
182
            bestcost = cost
183
        assert_equal(bestcost, 22)
184

    
185
    # def test_graph_edit_distance_bigger(self):
186
    #     G1 = circular_ladder_graph(12)
187
    #     G2 = circular_ladder_graph(16)
188
    #     assert_equal(graph_edit_distance(G1, G2), 22)
189

    
190
    def test_selfloops(self):
191
        G0 = nx.Graph()
192
        G1 = nx.Graph()
193
        G1.add_edges_from((('A', 'A'), ('A', 'B')))
194
        G2 = nx.Graph()
195
        G2.add_edges_from((('A', 'B'), ('B', 'B')))
196
        G3 = nx.Graph()
197
        G3.add_edges_from((('A', 'A'), ('A', 'B'), ('B', 'B')))
198

    
199
        assert_equal(graph_edit_distance(G0, G0), 0)
200
        assert_equal(graph_edit_distance(G0, G1), 4)
201
        assert_equal(graph_edit_distance(G1, G0), 4)
202
        assert_equal(graph_edit_distance(G0, G2), 4)
203
        assert_equal(graph_edit_distance(G2, G0), 4)
204
        assert_equal(graph_edit_distance(G0, G3), 5)
205
        assert_equal(graph_edit_distance(G3, G0), 5)
206

    
207
        assert_equal(graph_edit_distance(G1, G1), 0)
208
        assert_equal(graph_edit_distance(G1, G2), 0)
209
        assert_equal(graph_edit_distance(G2, G1), 0)
210
        assert_equal(graph_edit_distance(G1, G3), 1)
211
        assert_equal(graph_edit_distance(G3, G1), 1)
212

    
213
        assert_equal(graph_edit_distance(G2, G2), 0)
214
        assert_equal(graph_edit_distance(G2, G3), 1)
215
        assert_equal(graph_edit_distance(G3, G2), 1)
216

    
217
        assert_equal(graph_edit_distance(G3, G3), 0)
218

    
219
    def test_digraph(self):
220
        G0 = nx.DiGraph()
221
        G1 = nx.DiGraph()
222
        G1.add_edges_from((('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A')))
223
        G2 = nx.DiGraph()
224
        G2.add_edges_from((('A', 'B'), ('B', 'C'), ('C', 'D'), ('A', 'D')))
225
        G3 = nx.DiGraph()
226
        G3.add_edges_from((('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')))
227

    
228
        assert_equal(graph_edit_distance(G0, G0), 0)
229
        assert_equal(graph_edit_distance(G0, G1), 8)
230
        assert_equal(graph_edit_distance(G1, G0), 8)
231
        assert_equal(graph_edit_distance(G0, G2), 8)
232
        assert_equal(graph_edit_distance(G2, G0), 8)
233
        assert_equal(graph_edit_distance(G0, G3), 8)
234
        assert_equal(graph_edit_distance(G3, G0), 8)
235

    
236
        assert_equal(graph_edit_distance(G1, G1), 0)
237
        assert_equal(graph_edit_distance(G1, G2), 2)
238
        assert_equal(graph_edit_distance(G2, G1), 2)
239
        assert_equal(graph_edit_distance(G1, G3), 4)
240
        assert_equal(graph_edit_distance(G3, G1), 4)
241

    
242
        assert_equal(graph_edit_distance(G2, G2), 0)
243
        assert_equal(graph_edit_distance(G2, G3), 2)
244
        assert_equal(graph_edit_distance(G3, G2), 2)
245

    
246
        assert_equal(graph_edit_distance(G3, G3), 0)
247

    
248
    def test_multigraph(self):
249
        G0 = nx.MultiGraph()
250
        G1 = nx.MultiGraph()
251
        G1.add_edges_from((('A', 'B'), ('B', 'C'), ('A', 'C')))
252
        G2 = nx.MultiGraph()
253
        G2.add_edges_from((('A', 'B'), ('B', 'C'), ('B', 'C'), ('A', 'C')))
254
        G3 = nx.MultiGraph()
255
        G3.add_edges_from((('A', 'B'), ('B', 'C'), ('A', 'C'), ('A', 'C'), ('A', 'C')))
256

    
257
        assert_equal(graph_edit_distance(G0, G0), 0)
258
        assert_equal(graph_edit_distance(G0, G1), 6)
259
        assert_equal(graph_edit_distance(G1, G0), 6)
260
        assert_equal(graph_edit_distance(G0, G2), 7)
261
        assert_equal(graph_edit_distance(G2, G0), 7)
262
        assert_equal(graph_edit_distance(G0, G3), 8)
263
        assert_equal(graph_edit_distance(G3, G0), 8)
264

    
265
        assert_equal(graph_edit_distance(G1, G1), 0)
266
        assert_equal(graph_edit_distance(G1, G2), 1)
267
        assert_equal(graph_edit_distance(G2, G1), 1)
268
        assert_equal(graph_edit_distance(G1, G3), 2)
269
        assert_equal(graph_edit_distance(G3, G1), 2)
270

    
271
        assert_equal(graph_edit_distance(G2, G2), 0)
272
        assert_equal(graph_edit_distance(G2, G3), 1)
273
        assert_equal(graph_edit_distance(G3, G2), 1)
274

    
275
        assert_equal(graph_edit_distance(G3, G3), 0)
276

    
277
    def test_multidigraph(self):
278
        G1 = nx.MultiDiGraph()
279
        G1.add_edges_from((('hardware', 'kernel'), ('kernel', 'hardware'), ('kernel', 'userspace'), ('userspace', 'kernel')))
280
        G2 = nx.MultiDiGraph()
281
        G2.add_edges_from((('winter', 'spring'), ('spring', 'summer'), ('summer', 'autumn'), ('autumn', 'winter')))
282

    
283
        assert_equal(graph_edit_distance(G1, G2), 5)
284
        assert_equal(graph_edit_distance(G2, G1), 5)
285

    
286
    # by https://github.com/jfbeaumont
287
    def testCopy(self):
288
        G = nx.Graph()
289
        G.add_node('A', label='A')
290
        G.add_node('B', label='B')
291
        G.add_edge('A', 'B', label='a-b')
292
        assert_equal(graph_edit_distance(G, G.copy(), node_match=nmatch, edge_match=ematch), 0)
293

    
294
    def testSame(self):
295
        G1 = nx.Graph()
296
        G1.add_node('A', label='A')
297
        G1.add_node('B', label='B')
298
        G1.add_edge('A', 'B', label='a-b')
299
        G2 = nx.Graph()
300
        G2.add_node('A', label='A')
301
        G2.add_node('B', label='B')
302
        G2.add_edge('A', 'B', label='a-b')
303
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 0)
304

    
305
    def testOneEdgeLabelDiff(self):
306
        G1 = nx.Graph()
307
        G1.add_node('A', label='A')
308
        G1.add_node('B', label='B')
309
        G1.add_edge('A', 'B', label='a-b')
310
        G2 = nx.Graph()
311
        G2.add_node('A', label='A')
312
        G2.add_node('B', label='B')
313
        G2.add_edge('A', 'B', label='bad')
314
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 1)
315

    
316
    def testOneNodeLabelDiff(self):
317
        G1 = nx.Graph()
318
        G1.add_node('A', label='A')
319
        G1.add_node('B', label='B')
320
        G1.add_edge('A', 'B', label='a-b')
321
        G2 = nx.Graph()
322
        G2.add_node('A', label='Z')
323
        G2.add_node('B', label='B')
324
        G2.add_edge('A', 'B', label='a-b')
325
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 1)
326

    
327
    def testOneExtraNode(self):
328
        G1 = nx.Graph()
329
        G1.add_node('A', label='A')
330
        G1.add_node('B', label='B')
331
        G1.add_edge('A', 'B', label='a-b')
332
        G2 = nx.Graph()
333
        G2.add_node('A', label='A')
334
        G2.add_node('B', label='B')
335
        G2.add_edge('A', 'B', label='a-b')
336
        G2.add_node('C', label='C')
337
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 1)
338

    
339
    def testOneExtraEdge(self):
340
        G1 = nx.Graph()
341
        G1.add_node('A', label='A')
342
        G1.add_node('B', label='B')
343
        G1.add_node('C', label='C')
344
        G1.add_node('C', label='C')
345
        G1.add_edge('A', 'B', label='a-b')
346
        G2 = nx.Graph()
347
        G2.add_node('A', label='A')
348
        G2.add_node('B', label='B')
349
        G2.add_node('C', label='C')
350
        G2.add_edge('A', 'B', label='a-b')
351
        G2.add_edge('A', 'C', label='a-c')
352
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 1)
353

    
354
    def testOneExtraNodeAndEdge(self):
355
        G1 = nx.Graph()
356
        G1.add_node('A', label='A')
357
        G1.add_node('B', label='B')
358
        G1.add_edge('A', 'B', label='a-b')
359
        G2 = nx.Graph()
360
        G2.add_node('A', label='A')
361
        G2.add_node('B', label='B')
362
        G2.add_node('C', label='C')
363
        G2.add_edge('A', 'B', label='a-b')
364
        G2.add_edge('A', 'C', label='a-c')
365
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 2)
366

    
367
    def testGraph1(self):
368
        G1 = getCanonical()
369
        G2 = nx.Graph()
370
        G2.add_node('A', label='A')
371
        G2.add_node('B', label='B')
372
        G2.add_node('D', label='D')
373
        G2.add_node('E', label='E')
374
        G2.add_edge('A', 'B', label='a-b')
375
        G2.add_edge('B', 'D', label='b-d')
376
        G2.add_edge('D', 'E', label='d-e')
377
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 3)
378

    
379
    def testGraph2(self):
380
        G1 = getCanonical()
381
        G2 = nx.Graph()
382
        G2.add_node('A', label='A')
383
        G2.add_node('B', label='B')
384
        G2.add_node('C', label='C')
385
        G2.add_node('D', label='D')
386
        G2.add_node('E', label='E')
387
        G2.add_edge('A', 'B', label='a-b')
388
        G2.add_edge('B', 'C', label='b-c')
389
        G2.add_edge('C', 'D', label='c-d')
390
        G2.add_edge('C', 'E', label='c-e')
391
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 4)
392

    
393
    def testGraph3(self):
394
        G1 = getCanonical()
395
        G2 = nx.Graph()
396
        G2.add_node('A', label='A')
397
        G2.add_node('B', label='B')
398
        G2.add_node('C', label='C')
399
        G2.add_node('D', label='D')
400
        G2.add_node('E', label='E')
401
        G2.add_node('F', label='F')
402
        G2.add_node('G', label='G')
403
        G2.add_edge('A', 'C', label='a-c')
404
        G2.add_edge('A', 'D', label='a-d')
405
        G2.add_edge('D', 'E', label='d-e')
406
        G2.add_edge('D', 'F', label='d-f')
407
        G2.add_edge('D', 'G', label='d-g')
408
        G2.add_edge('E', 'B', label='e-b')
409
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 12)
410

    
411
    def testGraph4(self):
412
        G1 = getCanonical()
413
        G2 = nx.Graph()
414
        G2.add_node('A', label='A')
415
        G2.add_node('B', label='B')
416
        G2.add_node('C', label='C')
417
        G2.add_node('D', label='D')
418
        G2.add_edge('A', 'B', label='a-b')
419
        G2.add_edge('B', 'C', label='b-c')
420
        G2.add_edge('C', 'D', label='c-d')
421
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 2)
422

    
423
    def testGraph4_a(self):
424
        G1 = getCanonical()
425
        G2 = nx.Graph()
426
        G2.add_node('A', label='A')
427
        G2.add_node('B', label='B')
428
        G2.add_node('C', label='C')
429
        G2.add_node('D', label='D')
430
        G2.add_edge('A', 'B', label='a-b')
431
        G2.add_edge('B', 'C', label='b-c')
432
        G2.add_edge('A', 'D', label='a-d')
433
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 2)
434

    
435
    def testGraph4_b(self):
436
        G1 = getCanonical()
437
        G2 = nx.Graph()
438
        G2.add_node('A', label='A')
439
        G2.add_node('B', label='B')
440
        G2.add_node('C', label='C')
441
        G2.add_node('D', label='D')
442
        G2.add_edge('A', 'B', label='a-b')
443
        G2.add_edge('B', 'C', label='b-c')
444
        G2.add_edge('B', 'D', label='bad')
445
        assert_equal(graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch), 1)
446

    
447
    def test_simrank_no_source_no_target(self):
448
        G = nx.cycle_graph(5)
449
        expected = {0: {0: 1, 1: 0.3951219505902448, 2: 0.5707317069281646, 3: 0.5707317069281646, 4: 0.3951219505902449}, 1: {0: 0.3951219505902448, 1: 1, 2: 0.3951219505902449, 3: 0.5707317069281646, 4: 0.5707317069281646}, 2: {0: 0.5707317069281646, 1: 0.3951219505902449, 2: 1, 3: 0.3951219505902449, 4: 0.5707317069281646}, 3: {0: 0.5707317069281646, 1: 0.5707317069281646, 2: 0.3951219505902449, 3: 1, 4: 0.3951219505902449}, 4: {0: 0.3951219505902449, 1: 0.5707317069281646, 2: 0.5707317069281646, 3: 0.3951219505902449, 4: 1}}
450
        actual = nx.simrank_similarity(G)
451
        assert_equal(expected, actual)
452

    
453
    def test_simrank_source_no_target(self):
454
        G = nx.cycle_graph(5)
455
        expected = {0: 1, 1: 0.3951219505902448, 2: 0.5707317069281646, 3: 0.5707317069281646, 4: 0.3951219505902449}
456
        actual = nx.simrank_similarity(G, source=0)
457
        assert_equal(expected, actual)
458

    
459
    def test_simrank_source_and_target(self):
460
        G = nx.cycle_graph(5)
461
        expected = 1
462
        actual = nx.simrank_similarity(G, source=0, target=0)
463
        assert_equal(expected, actual)
464

    
465
    def test_simrank_numpy_no_source_no_target(self):
466
        G = nx.cycle_graph(5)
467
        expected = numpy.array([
468
            [1.0, 0.3947180735764555, 0.570482097206368, 0.570482097206368, 0.3947180735764555],
469
            [0.3947180735764555, 1.0, 0.3947180735764555, 0.570482097206368, 0.570482097206368],
470
            [0.570482097206368, 0.3947180735764555, 1.0, 0.3947180735764555, 0.570482097206368],
471
            [0.570482097206368, 0.570482097206368, 0.3947180735764555, 1.0, 0.3947180735764555],
472
            [0.3947180735764555, 0.570482097206368, 0.570482097206368, 0.3947180735764555, 1.0]
473
        ])
474
        actual = nx.simrank_similarity_numpy(G)
475
        numpy.testing.assert_allclose(expected, actual, atol=1e-7)
476

    
477
    def test_simrank_numpy_source_no_target(self):
478
        G = nx.cycle_graph(5)
479
        expected = numpy.array(
480
            [1.0, 0.3947180735764555, 0.570482097206368, 0.570482097206368, 0.3947180735764555],
481
        )
482
        actual = nx.simrank_similarity_numpy(G, source=0)
483
        numpy.testing.assert_allclose(expected, actual, atol=1e-7)
484

    
485
    def test_simrank_numpy_source_and_target(self):
486
        G = nx.cycle_graph(5)
487
        expected = 1.0
488
        actual = nx.simrank_similarity_numpy(G, source=0, target=0)
489
        numpy.testing.assert_allclose(expected, actual, atol=1e-7)