Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (14.5 KB)

1
#!/usr/bin/env python
2
from nose.tools import assert_equal
3
import networkx as nx
4
from networkx.algorithms import bipartite
5
from networkx.testing import assert_edges_equal, assert_nodes_equal
6

    
7

    
8
class TestBipartiteProject:
9

    
10
    def test_path_projected_graph(self):
11
        G = nx.path_graph(4)
12
        P = bipartite.projected_graph(G, [1, 3])
13
        assert_nodes_equal(list(P), [1, 3])
14
        assert_edges_equal(list(P.edges()), [(1, 3)])
15
        P = bipartite.projected_graph(G, [0, 2])
16
        assert_nodes_equal(list(P), [0, 2])
17
        assert_edges_equal(list(P.edges()), [(0, 2)])
18

    
19
    def test_path_projected_properties_graph(self):
20
        G = nx.path_graph(4)
21
        G.add_node(1, name='one')
22
        G.add_node(2, name='two')
23
        P = bipartite.projected_graph(G, [1, 3])
24
        assert_nodes_equal(list(P), [1, 3])
25
        assert_edges_equal(list(P.edges()), [(1, 3)])
26
        assert_equal(P.nodes[1]['name'], G.nodes[1]['name'])
27
        P = bipartite.projected_graph(G, [0, 2])
28
        assert_nodes_equal(list(P), [0, 2])
29
        assert_edges_equal(list(P.edges()), [(0, 2)])
30
        assert_equal(P.nodes[2]['name'], G.nodes[2]['name'])
31

    
32
    def test_path_collaboration_projected_graph(self):
33
        G = nx.path_graph(4)
34
        P = bipartite.collaboration_weighted_projected_graph(G, [1, 3])
35
        assert_nodes_equal(list(P), [1, 3])
36
        assert_edges_equal(list(P.edges()), [(1, 3)])
37
        P[1][3]['weight'] = 1
38
        P = bipartite.collaboration_weighted_projected_graph(G, [0, 2])
39
        assert_nodes_equal(list(P), [0, 2])
40
        assert_edges_equal(list(P.edges()), [(0, 2)])
41
        P[0][2]['weight'] = 1
42

    
43
    def test_directed_path_collaboration_projected_graph(self):
44
        G = nx.DiGraph()
45
        nx.add_path(G, range(4))
46
        P = bipartite.collaboration_weighted_projected_graph(G, [1, 3])
47
        assert_nodes_equal(list(P), [1, 3])
48
        assert_edges_equal(list(P.edges()), [(1, 3)])
49
        P[1][3]['weight'] = 1
50
        P = bipartite.collaboration_weighted_projected_graph(G, [0, 2])
51
        assert_nodes_equal(list(P), [0, 2])
52
        assert_edges_equal(list(P.edges()), [(0, 2)])
53
        P[0][2]['weight'] = 1
54

    
55
    def test_path_weighted_projected_graph(self):
56
        G = nx.path_graph(4)
57
        P = bipartite.weighted_projected_graph(G, [1, 3])
58
        assert_nodes_equal(list(P), [1, 3])
59
        assert_edges_equal(list(P.edges()), [(1, 3)])
60
        P[1][3]['weight'] = 1
61
        P = bipartite.weighted_projected_graph(G, [0, 2])
62
        assert_nodes_equal(list(P), [0, 2])
63
        assert_edges_equal(list(P.edges()), [(0, 2)])
64
        P[0][2]['weight'] = 1
65

    
66
    def test_path_weighted_projected_directed_graph(self):
67
        G = nx.DiGraph()
68
        nx.add_path(G, range(4))
69
        P = bipartite.weighted_projected_graph(G, [1, 3])
70
        assert_nodes_equal(list(P), [1, 3])
71
        assert_edges_equal(list(P.edges()), [(1, 3)])
72
        P[1][3]['weight'] = 1
73
        P = bipartite.weighted_projected_graph(G, [0, 2])
74
        assert_nodes_equal(list(P), [0, 2])
75
        assert_edges_equal(list(P.edges()), [(0, 2)])
76
        P[0][2]['weight'] = 1
77

    
78
    def test_star_projected_graph(self):
79
        G = nx.star_graph(3)
80
        P = bipartite.projected_graph(G, [1, 2, 3])
81
        assert_nodes_equal(list(P), [1, 2, 3])
82
        assert_edges_equal(list(P.edges()), [(1, 2), (1, 3), (2, 3)])
83
        P = bipartite.weighted_projected_graph(G, [1, 2, 3])
84
        assert_nodes_equal(list(P), [1, 2, 3])
85
        assert_edges_equal(list(P.edges()), [(1, 2), (1, 3), (2, 3)])
86

    
87
        P = bipartite.projected_graph(G, [0])
88
        assert_nodes_equal(list(P), [0])
89
        assert_edges_equal(list(P.edges()), [])
90

    
91
    def test_project_multigraph(self):
92
        G = nx.Graph()
93
        G.add_edge('a', 1)
94
        G.add_edge('b', 1)
95
        G.add_edge('a', 2)
96
        G.add_edge('b', 2)
97
        P = bipartite.projected_graph(G, 'ab')
98
        assert_edges_equal(list(P.edges()), [('a', 'b')])
99
        P = bipartite.weighted_projected_graph(G, 'ab')
100
        assert_edges_equal(list(P.edges()), [('a', 'b')])
101
        P = bipartite.projected_graph(G, 'ab', multigraph=True)
102
        assert_edges_equal(list(P.edges()), [('a', 'b'), ('a', 'b')])
103

    
104
    def test_project_collaboration(self):
105
        G = nx.Graph()
106
        G.add_edge('a', 1)
107
        G.add_edge('b', 1)
108
        G.add_edge('b', 2)
109
        G.add_edge('c', 2)
110
        G.add_edge('c', 3)
111
        G.add_edge('c', 4)
112
        G.add_edge('b', 4)
113
        P = bipartite.collaboration_weighted_projected_graph(G, 'abc')
114
        assert_equal(P['a']['b']['weight'], 1)
115
        assert_equal(P['b']['c']['weight'], 2)
116

    
117
    def test_directed_projection(self):
118
        G = nx.DiGraph()
119
        G.add_edge('A', 1)
120
        G.add_edge(1, 'B')
121
        G.add_edge('A', 2)
122
        G.add_edge('B', 2)
123
        P = bipartite.projected_graph(G, 'AB')
124
        assert_edges_equal(list(P.edges()), [('A', 'B')])
125
        P = bipartite.weighted_projected_graph(G, 'AB')
126
        assert_edges_equal(list(P.edges()), [('A', 'B')])
127
        assert_equal(P['A']['B']['weight'], 1)
128

    
129
        P = bipartite.projected_graph(G, 'AB', multigraph=True)
130
        assert_edges_equal(list(P.edges()), [('A', 'B')])
131

    
132
        G = nx.DiGraph()
133
        G.add_edge('A', 1)
134
        G.add_edge(1, 'B')
135
        G.add_edge('A', 2)
136
        G.add_edge(2, 'B')
137
        P = bipartite.projected_graph(G, 'AB')
138
        assert_edges_equal(list(P.edges()), [('A', 'B')])
139
        P = bipartite.weighted_projected_graph(G, 'AB')
140
        assert_edges_equal(list(P.edges()), [('A', 'B')])
141
        assert_equal(P['A']['B']['weight'], 2)
142

    
143
        P = bipartite.projected_graph(G, 'AB', multigraph=True)
144
        assert_edges_equal(list(P.edges()), [('A', 'B'), ('A', 'B')])
145

    
146

    
147
class TestBipartiteWeightedProjection:
148

    
149
    def setUp(self):
150
        # Tore Opsahl's example
151
        # http://toreopsahl.com/2009/05/01/projecting-two-mode-networks-onto-weighted-one-mode-networks/
152
        self.G = nx.Graph()
153
        self.G.add_edge('A', 1)
154
        self.G.add_edge('A', 2)
155
        self.G.add_edge('B', 1)
156
        self.G.add_edge('B', 2)
157
        self.G.add_edge('B', 3)
158
        self.G.add_edge('B', 4)
159
        self.G.add_edge('B', 5)
160
        self.G.add_edge('C', 1)
161
        self.G.add_edge('D', 3)
162
        self.G.add_edge('E', 4)
163
        self.G.add_edge('E', 5)
164
        self.G.add_edge('E', 6)
165
        self.G.add_edge('F', 6)
166
        # Graph based on figure 6 from Newman (2001)
167
        self.N = nx.Graph()
168
        self.N.add_edge('A', 1)
169
        self.N.add_edge('A', 2)
170
        self.N.add_edge('A', 3)
171
        self.N.add_edge('B', 1)
172
        self.N.add_edge('B', 2)
173
        self.N.add_edge('B', 3)
174
        self.N.add_edge('C', 1)
175
        self.N.add_edge('D', 1)
176
        self.N.add_edge('E', 3)
177

    
178
    def test_project_weighted_shared(self):
179
        edges = [('A', 'B', 2),
180
                 ('A', 'C', 1),
181
                 ('B', 'C', 1),
182
                 ('B', 'D', 1),
183
                 ('B', 'E', 2),
184
                 ('E', 'F', 1)]
185
        Panswer = nx.Graph()
186
        Panswer.add_weighted_edges_from(edges)
187
        P = bipartite.weighted_projected_graph(self.G, 'ABCDEF')
188
        assert_edges_equal(list(P.edges()), Panswer.edges())
189
        for u, v in list(P.edges()):
190
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
191

    
192
        edges = [('A', 'B', 3),
193
                 ('A', 'E', 1),
194
                 ('A', 'C', 1),
195
                 ('A', 'D', 1),
196
                 ('B', 'E', 1),
197
                 ('B', 'C', 1),
198
                 ('B', 'D', 1),
199
                 ('C', 'D', 1)]
200
        Panswer = nx.Graph()
201
        Panswer.add_weighted_edges_from(edges)
202
        P = bipartite.weighted_projected_graph(self.N, 'ABCDE')
203
        assert_edges_equal(list(P.edges()), Panswer.edges())
204
        for u, v in list(P.edges()):
205
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
206

    
207
    def test_project_weighted_newman(self):
208
        edges = [('A', 'B', 1.5),
209
                 ('A', 'C', 0.5),
210
                 ('B', 'C', 0.5),
211
                 ('B', 'D', 1),
212
                 ('B', 'E', 2),
213
                 ('E', 'F', 1)]
214
        Panswer = nx.Graph()
215
        Panswer.add_weighted_edges_from(edges)
216
        P = bipartite.collaboration_weighted_projected_graph(self.G, 'ABCDEF')
217
        assert_edges_equal(list(P.edges()), Panswer.edges())
218
        for u, v in list(P.edges()):
219
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
220

    
221
        edges = [('A', 'B', 11 / 6.0),
222
                 ('A', 'E', 1 / 2.0),
223
                 ('A', 'C', 1 / 3.0),
224
                 ('A', 'D', 1 / 3.0),
225
                 ('B', 'E', 1 / 2.0),
226
                 ('B', 'C', 1 / 3.0),
227
                 ('B', 'D', 1 / 3.0),
228
                 ('C', 'D', 1 / 3.0)]
229
        Panswer = nx.Graph()
230
        Panswer.add_weighted_edges_from(edges)
231
        P = bipartite.collaboration_weighted_projected_graph(self.N, 'ABCDE')
232
        assert_edges_equal(list(P.edges()), Panswer.edges())
233
        for u, v in list(P.edges()):
234
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
235

    
236
    def test_project_weighted_ratio(self):
237
        edges = [('A', 'B', 2 / 6.0),
238
                 ('A', 'C', 1 / 6.0),
239
                 ('B', 'C', 1 / 6.0),
240
                 ('B', 'D', 1 / 6.0),
241
                 ('B', 'E', 2 / 6.0),
242
                 ('E', 'F', 1 / 6.0)]
243
        Panswer = nx.Graph()
244
        Panswer.add_weighted_edges_from(edges)
245
        P = bipartite.weighted_projected_graph(self.G, 'ABCDEF', ratio=True)
246
        assert_edges_equal(list(P.edges()), Panswer.edges())
247
        for u, v in list(P.edges()):
248
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
249

    
250
        edges = [('A', 'B', 3 / 3.0),
251
                 ('A', 'E', 1 / 3.0),
252
                 ('A', 'C', 1 / 3.0),
253
                 ('A', 'D', 1 / 3.0),
254
                 ('B', 'E', 1 / 3.0),
255
                 ('B', 'C', 1 / 3.0),
256
                 ('B', 'D', 1 / 3.0),
257
                 ('C', 'D', 1 / 3.0)]
258
        Panswer = nx.Graph()
259
        Panswer.add_weighted_edges_from(edges)
260
        P = bipartite.weighted_projected_graph(self.N, 'ABCDE', ratio=True)
261
        assert_edges_equal(list(P.edges()), Panswer.edges())
262
        for u, v in list(P.edges()):
263
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
264

    
265
    def test_project_weighted_overlap(self):
266
        edges = [('A', 'B', 2 / 2.0),
267
                 ('A', 'C', 1 / 1.0),
268
                 ('B', 'C', 1 / 1.0),
269
                 ('B', 'D', 1 / 1.0),
270
                 ('B', 'E', 2 / 3.0),
271
                 ('E', 'F', 1 / 1.0)]
272
        Panswer = nx.Graph()
273
        Panswer.add_weighted_edges_from(edges)
274
        P = bipartite.overlap_weighted_projected_graph(self.G, 'ABCDEF', jaccard=False)
275
        assert_edges_equal(list(P.edges()), Panswer.edges())
276
        for u, v in list(P.edges()):
277
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
278

    
279
        edges = [('A', 'B', 3 / 3.0),
280
                 ('A', 'E', 1 / 1.0),
281
                 ('A', 'C', 1 / 1.0),
282
                 ('A', 'D', 1 / 1.0),
283
                 ('B', 'E', 1 / 1.0),
284
                 ('B', 'C', 1 / 1.0),
285
                 ('B', 'D', 1 / 1.0),
286
                 ('C', 'D', 1 / 1.0)]
287
        Panswer = nx.Graph()
288
        Panswer.add_weighted_edges_from(edges)
289
        P = bipartite.overlap_weighted_projected_graph(self.N, 'ABCDE', jaccard=False)
290
        assert_edges_equal(list(P.edges()), Panswer.edges())
291
        for u, v in list(P.edges()):
292
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
293

    
294
    def test_project_weighted_jaccard(self):
295
        edges = [('A', 'B', 2 / 5.0),
296
                 ('A', 'C', 1 / 2.0),
297
                 ('B', 'C', 1 / 5.0),
298
                 ('B', 'D', 1 / 5.0),
299
                 ('B', 'E', 2 / 6.0),
300
                 ('E', 'F', 1 / 3.0)]
301
        Panswer = nx.Graph()
302
        Panswer.add_weighted_edges_from(edges)
303
        P = bipartite.overlap_weighted_projected_graph(self.G, 'ABCDEF')
304
        assert_edges_equal(list(P.edges()), Panswer.edges())
305
        for u, v in list(P.edges()):
306
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
307

    
308
        edges = [('A', 'B', 3 / 3.0),
309
                 ('A', 'E', 1 / 3.0),
310
                 ('A', 'C', 1 / 3.0),
311
                 ('A', 'D', 1 / 3.0),
312
                 ('B', 'E', 1 / 3.0),
313
                 ('B', 'C', 1 / 3.0),
314
                 ('B', 'D', 1 / 3.0),
315
                 ('C', 'D', 1 / 1.0)]
316
        Panswer = nx.Graph()
317
        Panswer.add_weighted_edges_from(edges)
318
        P = bipartite.overlap_weighted_projected_graph(self.N, 'ABCDE')
319
        assert_edges_equal(list(P.edges()), Panswer.edges())
320
        for u, v in P.edges():
321
            assert_equal(P[u][v]['weight'], Panswer[u][v]['weight'])
322

    
323
    def test_generic_weighted_projected_graph_simple(self):
324
        def shared(G, u, v):
325
            return len(set(G[u]) & set(G[v]))
326
        B = nx.path_graph(5)
327
        G = bipartite.generic_weighted_projected_graph(B, [0, 2, 4], weight_function=shared)
328
        assert_nodes_equal(list(G), [0, 2, 4])
329
        assert_edges_equal(list(list(G.edges(data=True))),
330
                           [(0, 2, {'weight': 1}), (2, 4, {'weight': 1})])
331

    
332
        G = bipartite.generic_weighted_projected_graph(B, [0, 2, 4])
333
        assert_nodes_equal(list(G), [0, 2, 4])
334
        assert_edges_equal(list(list(G.edges(data=True))),
335
                           [(0, 2, {'weight': 1}), (2, 4, {'weight': 1})])
336
        B = nx.DiGraph()
337
        nx.add_path(B, range(5))
338
        G = bipartite.generic_weighted_projected_graph(B, [0, 2, 4])
339
        assert_nodes_equal(list(G), [0, 2, 4])
340
        assert_edges_equal(list(G.edges(data=True)),
341
                           [(0, 2, {'weight': 1}), (2, 4, {'weight': 1})])
342

    
343
    def test_generic_weighted_projected_graph_custom(self):
344
        def jaccard(G, u, v):
345
            unbrs = set(G[u])
346
            vnbrs = set(G[v])
347
            return float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)
348

    
349
        def my_weight(G, u, v, weight='weight'):
350
            w = 0
351
            for nbr in set(G[u]) & set(G[v]):
352
                w += G.edges[u, nbr].get(weight, 1) + G.edges[v, nbr].get(weight, 1)
353
            return w
354
        B = nx.bipartite.complete_bipartite_graph(2, 2)
355
        for i, (u, v) in enumerate(B.edges()):
356
            B.edges[u, v]['weight'] = i + 1
357
        G = bipartite.generic_weighted_projected_graph(B, [0, 1],
358
                                                       weight_function=jaccard)
359
        assert_edges_equal(list(G.edges(data=True)), [(0, 1, {'weight': 1.0})])
360
        G = bipartite.generic_weighted_projected_graph(B, [0, 1],
361
                                                       weight_function=my_weight)
362
        assert_edges_equal(list(G.edges(data=True)), [(0, 1, {'weight': 10})])
363
        G = bipartite.generic_weighted_projected_graph(B, [0, 1])
364
        assert_edges_equal(list(G.edges(data=True)), [(0, 1, {'weight': 2})])