Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.9 KB)

1
#!/usr/bin/env python
2
from nose.tools import *
3
import networkx as nx
4

    
5

    
6
class TestTriangles:
7

    
8
    def test_empty(self):
9
        G = nx.Graph()
10
        assert_equal(list(nx.triangles(G).values()), [])
11

    
12
    def test_path(self):
13
        G = nx.path_graph(10)
14
        assert_equal(list(nx.triangles(G).values()),
15
                     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
16
        assert_equal(nx.triangles(G),
17
                     {0: 0, 1: 0, 2: 0, 3: 0, 4: 0,
18
                      5: 0, 6: 0, 7: 0, 8: 0, 9: 0})
19

    
20
    def test_cubical(self):
21
        G = nx.cubical_graph()
22
        assert_equal(list(nx.triangles(G).values()),
23
                     [0, 0, 0, 0, 0, 0, 0, 0])
24
        assert_equal(nx.triangles(G, 1), 0)
25
        assert_equal(list(nx.triangles(G, [1, 2]).values()), [0, 0])
26
        assert_equal(nx.triangles(G, 1), 0)
27
        assert_equal(nx.triangles(G, [1, 2]), {1: 0, 2: 0})
28

    
29
    def test_k5(self):
30
        G = nx.complete_graph(5)
31
        assert_equal(list(nx.triangles(G).values()), [6, 6, 6, 6, 6])
32
        assert_equal(sum(nx.triangles(G).values()) / 3.0, 10)
33
        assert_equal(nx.triangles(G, 1), 6)
34
        G.remove_edge(1, 2)
35
        assert_equal(list(nx.triangles(G).values()), [5, 3, 3, 5, 5])
36
        assert_equal(nx.triangles(G, 1), 3)
37

    
38

    
39
class TestDirectedClustering:
40

    
41
    def test_clustering(self):
42
        G = nx.DiGraph()
43
        assert_equal(list(nx.clustering(G).values()), [])
44
        assert_equal(nx.clustering(G), {})
45

    
46
    def test_path(self):
47
        G = nx.path_graph(10, create_using=nx.DiGraph())
48
        assert_equal(list(nx.clustering(G).values()),
49
                     [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
50
        assert_equal(nx.clustering(G),
51
                     {0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0,
52
                      5: 0.0, 6: 0.0, 7: 0.0, 8: 0.0, 9: 0.0})
53

    
54
    def test_k5(self):
55
        G = nx.complete_graph(5, create_using=nx.DiGraph())
56
        assert_equal(list(nx.clustering(G).values()), [1, 1, 1, 1, 1])
57
        assert_equal(nx.average_clustering(G), 1)
58
        G.remove_edge(1, 2)
59
        assert_equal(list(nx.clustering(G).values()),
60
                     [11. / 12., 1.0, 1.0, 11. / 12., 11. / 12.])
61
        assert_equal(nx.clustering(G, [1, 4]), {1: 1.0, 4: 11. /12.})
62
        G.remove_edge(2, 1)
63
        assert_equal(list(nx.clustering(G).values()),
64
                     [5. / 6., 1.0, 1.0, 5. / 6., 5. / 6.])
65
        assert_equal(nx.clustering(G, [1, 4]), {1: 1.0, 4: 0.83333333333333337})
66

    
67
    def test_triangle_and_edge(self):
68
        G = nx.cycle_graph(3, create_using=nx.DiGraph())
69
        G.add_edge(0, 4)
70
        assert_equal(nx.clustering(G)[0], 1.0 / 6.0)
71

    
72

    
73
class TestDirectedWeightedClustering:
74

    
75
    def test_clustering(self):
76
        G = nx.DiGraph()
77
        assert_equal(list(nx.clustering(G, weight='weight').values()), [])
78
        assert_equal(nx.clustering(G), {})
79

    
80
    def test_path(self):
81
        G = nx.path_graph(10, create_using=nx.DiGraph())
82
        assert_equal(list(nx.clustering(G, weight='weight').values()),
83
                     [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
84
        assert_equal(nx.clustering(G, weight='weight'),
85
                     {0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0,
86
                      5: 0.0, 6: 0.0, 7: 0.0, 8: 0.0, 9: 0.0})
87

    
88
    def test_k5(self):
89
        G = nx.complete_graph(5, create_using=nx.DiGraph())
90
        assert_equal(list(nx.clustering(G, weight='weight').values()), [1, 1, 1, 1, 1])
91
        assert_equal(nx.average_clustering(G, weight='weight'), 1)
92
        G.remove_edge(1, 2)
93
        assert_equal(list(nx.clustering(G, weight='weight').values()),
94
                     [11. / 12., 1.0, 1.0, 11. / 12., 11. / 12.])
95
        assert_equal(nx.clustering(G, [1, 4], weight='weight'), {1: 1.0, 4: 11. /12.})
96
        G.remove_edge(2, 1)
97
        assert_equal(list(nx.clustering(G, weight='weight').values()),
98
                     [5. / 6., 1.0, 1.0, 5. / 6., 5. / 6.])
99
        assert_equal(nx.clustering(G, [1, 4], weight='weight'), {1: 1.0, 4: 0.83333333333333337})
100

    
101
    def test_triangle_and_edge(self):
102
        G = nx.cycle_graph(3, create_using=nx.DiGraph())
103
        G.add_edge(0, 4, weight=2)
104
        assert_equal(nx.clustering(G)[0], 1.0 / 6.0)
105
        assert_equal(nx.clustering(G, weight='weight')[0], 1.0 / 12.0)
106

    
107

    
108
class TestWeightedClustering:
109

    
110
    def test_clustering(self):
111
        G = nx.Graph()
112
        assert_equal(list(nx.clustering(G, weight='weight').values()), [])
113
        assert_equal(nx.clustering(G), {})
114

    
115
    def test_path(self):
116
        G = nx.path_graph(10)
117
        assert_equal(list(nx.clustering(G, weight='weight').values()),
118
                     [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
119
        assert_equal(nx.clustering(G, weight='weight'),
120
                     {0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0,
121
                      5: 0.0, 6: 0.0, 7: 0.0, 8: 0.0, 9: 0.0})
122

    
123
    def test_cubical(self):
124
        G = nx.cubical_graph()
125
        assert_equal(list(nx.clustering(G, weight='weight').values()),
126
                     [0, 0, 0, 0, 0, 0, 0, 0])
127
        assert_equal(nx.clustering(G, 1), 0)
128
        assert_equal(list(nx.clustering(G, [1, 2], weight='weight').values()), [0, 0])
129
        assert_equal(nx.clustering(G, 1, weight='weight'), 0)
130
        assert_equal(nx.clustering(G, [1, 2], weight='weight'), {1: 0, 2: 0})
131

    
132
    def test_k5(self):
133
        G = nx.complete_graph(5)
134
        assert_equal(list(nx.clustering(G, weight='weight').values()), [1, 1, 1, 1, 1])
135
        assert_equal(nx.average_clustering(G, weight='weight'), 1)
136
        G.remove_edge(1, 2)
137
        assert_equal(list(nx.clustering(G, weight='weight').values()),
138
                     [5. / 6., 1.0, 1.0, 5. / 6., 5. / 6.])
139
        assert_equal(nx.clustering(G, [1, 4], weight='weight'), {1: 1.0, 4: 0.83333333333333337})
140

    
141
    def test_triangle_and_edge(self):
142
        G = nx.cycle_graph(3)
143
        G.add_edge(0, 4, weight=2)
144
        assert_equal(nx.clustering(G)[0], 1.0 / 3.0)
145
        assert_equal(nx.clustering(G, weight='weight')[0], 1.0 / 6.0)
146

    
147

    
148
class TestClustering:
149

    
150
    def test_clustering(self):
151
        G = nx.Graph()
152
        assert_equal(list(nx.clustering(G).values()), [])
153
        assert_equal(nx.clustering(G), {})
154

    
155
    def test_path(self):
156
        G = nx.path_graph(10)
157
        assert_equal(list(nx.clustering(G).values()),
158
                     [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
159
        assert_equal(nx.clustering(G),
160
                     {0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0,
161
                      5: 0.0, 6: 0.0, 7: 0.0, 8: 0.0, 9: 0.0})
162

    
163
    def test_cubical(self):
164
        G = nx.cubical_graph()
165
        assert_equal(list(nx.clustering(G).values()),
166
                     [0, 0, 0, 0, 0, 0, 0, 0])
167
        assert_equal(nx.clustering(G, 1), 0)
168
        assert_equal(list(nx.clustering(G, [1, 2]).values()), [0, 0])
169
        assert_equal(nx.clustering(G, 1), 0)
170
        assert_equal(nx.clustering(G, [1, 2]), {1: 0, 2: 0})
171

    
172
    def test_k5(self):
173
        G = nx.complete_graph(5)
174
        assert_equal(list(nx.clustering(G).values()), [1, 1, 1, 1, 1])
175
        assert_equal(nx.average_clustering(G), 1)
176
        G.remove_edge(1, 2)
177
        assert_equal(list(nx.clustering(G).values()),
178
                     [5. / 6., 1.0, 1.0, 5. / 6., 5. / 6.])
179
        assert_equal(nx.clustering(G, [1, 4]), {1: 1.0, 4: 0.83333333333333337})
180

    
181

    
182
class TestTransitivity:
183

    
184
    def test_transitivity(self):
185
        G = nx.Graph()
186
        assert_equal(nx.transitivity(G), 0.0)
187

    
188
    def test_path(self):
189
        G = nx.path_graph(10)
190
        assert_equal(nx.transitivity(G), 0.0)
191

    
192
    def test_cubical(self):
193
        G = nx.cubical_graph()
194
        assert_equal(nx.transitivity(G), 0.0)
195

    
196
    def test_k5(self):
197
        G = nx.complete_graph(5)
198
        assert_equal(nx.transitivity(G), 1.0)
199
        G.remove_edge(1, 2)
200
        assert_equal(nx.transitivity(G), 0.875)
201

    
202
    # def test_clustering_transitivity(self):
203
    #     # check that weighted average of clustering is transitivity
204
    #     G = nx.complete_graph(5)
205
    #     G.remove_edge(1,2)
206
    #     t1=nx.transitivity(G)
207
    #     (cluster_d2,weights)=nx.clustering(G,weights=True)
208
    #     trans=[]
209
    #     for v in G.nodes():
210
    #         trans.append(cluster_d2[v]*weights[v])
211
    #     t2=sum(trans)
212
    #     assert_almost_equal(abs(t1-t2),0)
213

    
214

    
215
class TestSquareClustering:
216

    
217
    def test_clustering(self):
218
        G = nx.Graph()
219
        assert_equal(list(nx.square_clustering(G).values()), [])
220
        assert_equal(nx.square_clustering(G), {})
221

    
222
    def test_path(self):
223
        G = nx.path_graph(10)
224
        assert_equal(list(nx.square_clustering(G).values()),
225
                     [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
226
        assert_equal(nx.square_clustering(G),
227
                     {0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0,
228
                      5: 0.0, 6: 0.0, 7: 0.0, 8: 0.0, 9: 0.0})
229

    
230
    def test_cubical(self):
231
        G = nx.cubical_graph()
232
        assert_equal(list(nx.square_clustering(G).values()),
233
                     [0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5])
234
        assert_equal(list(nx.square_clustering(G, [1, 2]).values()), [0.5, 0.5])
235
        assert_equal(nx.square_clustering(G, [1])[1], 0.5)
236
        assert_equal(nx.square_clustering(G, [1, 2]), {1: 0.5, 2: 0.5})
237

    
238
    def test_k5(self):
239
        G = nx.complete_graph(5)
240
        assert_equal(list(nx.square_clustering(G).values()), [1, 1, 1, 1, 1])
241

    
242
    def test_bipartite_k5(self):
243
        G = nx.complete_bipartite_graph(5, 5)
244
        assert_equal(list(nx.square_clustering(G).values()),
245
                     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
246

    
247
    def test_lind_square_clustering(self):
248
        """Test C4 for figure 1 Lind et al (2005)"""
249
        G = nx.Graph([(1, 2), (1, 3), (1, 6), (1, 7), (2, 4), (2, 5),
250
                      (3, 4), (3, 5), (6, 7), (7, 8), (6, 8), (7, 9),
251
                      (7, 10), (6, 11), (6, 12), (2, 13), (2, 14), (3, 15), (3, 16)])
252
        G1 = G.subgraph([1, 2, 3, 4, 5, 13, 14, 15, 16])
253
        G2 = G.subgraph([1, 6, 7, 8, 9, 10, 11, 12])
254
        assert_equal(nx.square_clustering(G, [1])[1], 3 / 75.0)
255
        assert_equal(nx.square_clustering(G1, [1])[1], 2 / 6.0)
256
        assert_equal(nx.square_clustering(G2, [1])[1], 1 / 5.0)
257

    
258

    
259
def test_average_clustering():
260
    G = nx.cycle_graph(3)
261
    G.add_edge(2, 3)
262
    assert_equal(nx.average_clustering(G), (1 + 1 + 1 / 3.0) / 4.0)
263
    assert_equal(nx.average_clustering(G, count_zeros=True), (1 + 1 + 1 / 3.0) / 4.0)
264
    assert_equal(nx.average_clustering(G, count_zeros=False), (1 + 1 + 1 / 3.0) / 3.0)
265

    
266

    
267
class TestGeneralizedDegree:
268

    
269
    def test_generalized_degree(self):
270
        G = nx.Graph()
271
        assert_equal(nx.generalized_degree(G), {})
272

    
273
    def test_path(self):
274
        G = nx.path_graph(5)
275
        assert_equal(nx.generalized_degree(G, 0), {0: 1})
276
        assert_equal(nx.generalized_degree(G, 1), {0: 2})
277

    
278
    def test_cubical(self):
279
        G = nx.cubical_graph()
280
        assert_equal(nx.generalized_degree(G, 0), {0: 3})
281

    
282
    def test_k5(self):
283
        G = nx.complete_graph(5)
284
        assert_equal(nx.generalized_degree(G, 0), {3: 4})
285
        G.remove_edge(0, 1)
286
        assert_equal(nx.generalized_degree(G, 0), {2: 3})