Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.97 KB)

1
#!/usr/bin/env python
2
"""
3
Threshold Graphs
4
================
5
"""
6

    
7
from nose.tools import assert_true, assert_false, assert_equal, assert_almost_equal, assert_raises
8
from nose import SkipTest
9
from nose.plugins.attrib import attr
10
import networkx as nx
11
import networkx.algorithms.threshold as nxt
12
from networkx.algorithms.isomorphism.isomorph import graph_could_be_isomorphic
13

    
14
cnlti = nx.convert_node_labels_to_integers
15

    
16

    
17
class TestGeneratorThreshold():
18
    def test_threshold_sequence_graph_test(self):
19
        G = nx.star_graph(10)
20
        assert_true(nxt.is_threshold_graph(G))
21
        assert_true(nxt.is_threshold_sequence(list(d for n, d in G.degree())))
22

    
23
        G = nx.complete_graph(10)
24
        assert_true(nxt.is_threshold_graph(G))
25
        assert_true(nxt.is_threshold_sequence(list(d for n, d in G.degree())))
26

    
27
        deg = [3, 2, 2, 1, 1, 1]
28
        assert_false(nxt.is_threshold_sequence(deg))
29

    
30
        deg = [3, 2, 2, 1]
31
        assert_true(nxt.is_threshold_sequence(deg))
32

    
33
        G = nx.generators.havel_hakimi_graph(deg)
34
        assert_true(nxt.is_threshold_graph(G))
35

    
36
    def test_creation_sequences(self):
37
        deg = [3, 2, 2, 1]
38
        G = nx.generators.havel_hakimi_graph(deg)
39

    
40
        with assert_raises(ValueError):
41
            nxt.creation_sequence(deg, with_labels=True, compact=True)
42

    
43
        cs0 = nxt.creation_sequence(deg)
44
        H0 = nxt.threshold_graph(cs0)
45
        assert_equal(''.join(cs0), 'ddid')
46

    
47
        cs1 = nxt.creation_sequence(deg, with_labels=True)
48
        H1 = nxt.threshold_graph(cs1)
49
        assert_equal(cs1, [(1, 'd'), (2, 'd'), (3, 'i'), (0, 'd')])
50

    
51
        cs2 = nxt.creation_sequence(deg, compact=True)
52
        H2 = nxt.threshold_graph(cs2)
53
        assert_equal(cs2, [2, 1, 1])
54
        assert_equal(''.join(nxt.uncompact(cs2)), 'ddid')
55
        assert_true(graph_could_be_isomorphic(H0, G))
56
        assert_true(graph_could_be_isomorphic(H0, H1))
57
        assert_true(graph_could_be_isomorphic(H0, H2))
58

    
59
    def test_make_compact(self):
60
        assert_equal(nxt.make_compact(['d', 'd', 'd', 'i', 'd', 'd']), [3, 1, 2])
61
        assert_equal(nxt.make_compact([3, 1, 2]), [3, 1, 2])
62
        assert_raises(TypeError, nxt.make_compact, [3., 1., 2.])
63

    
64
    def test_uncompact(self):
65
        assert_equal(nxt.uncompact([3, 1, 2]), ['d', 'd', 'd', 'i', 'd', 'd'])
66
        assert_equal(nxt.uncompact(['d', 'd', 'i', 'd']), ['d', 'd', 'i', 'd'])
67
        assert_equal(nxt.uncompact(nxt.uncompact([(1, 'd'), (2, 'd'), (3, 'i'), (0, 'd')])),
68
                     nxt.uncompact([(1, 'd'), (2, 'd'), (3, 'i'), (0, 'd')]))
69
        assert_raises(TypeError, nxt.uncompact, [3., 1., 2.])
70

    
71
    def test_creation_sequence_to_weights(self):
72
        assert_equal(nxt.creation_sequence_to_weights([3, 1, 2]), [0.5, 0.5, 0.5, 0.25, 0.75, 0.75])
73
        assert_raises(TypeError, nxt.creation_sequence_to_weights, [3., 1., 2.])
74

    
75
    def test_weights_to_creation_sequence(self):
76
        deg = [3, 2, 2, 1]
77
        with assert_raises(ValueError):
78
            nxt.weights_to_creation_sequence(deg, with_labels=True, compact=True)
79
        assert_equal(nxt.weights_to_creation_sequence(deg, with_labels=True),
80
                     [(3, 'd'), (1, 'd'), (2, 'd'), (0, 'd')])
81
        assert_equal(nxt.weights_to_creation_sequence(deg, compact=True), [4])
82

    
83
    def test_find_alternating_4_cycle(self):
84
        G = nx.Graph()
85
        G.add_edge(1, 2)
86
        assert_false(nxt.find_alternating_4_cycle(G))
87

    
88
    def test_shortest_path(self):
89
        deg = [3, 2, 2, 1]
90
        G = nx.generators.havel_hakimi_graph(deg)
91
        cs1 = nxt.creation_sequence(deg, with_labels=True)
92
        for n, m in [(3, 0), (0, 3), (0, 2), (0, 1), (1, 3),
93
                     (3, 1), (1, 2), (2, 3)]:
94
            assert_equal(nxt.shortest_path(cs1, n, m),
95
                         nx.shortest_path(G, n, m))
96

    
97
        spl = nxt.shortest_path_length(cs1, 3)
98
        spl2 = nxt.shortest_path_length([t for v, t in cs1], 2)
99
        assert_equal(spl, spl2)
100

    
101
        spld = {}
102
        for j, pl in enumerate(spl):
103
            n = cs1[j][0]
104
            spld[n] = pl
105
        assert_equal(spld, nx.single_source_shortest_path_length(G, 3))
106

    
107
        assert_equal(nxt.shortest_path(['d', 'd', 'd', 'i', 'd', 'd'], 1, 2), [1, 2])
108
        assert_equal(nxt.shortest_path([3, 1, 2], 1, 2), [1, 2])
109
        assert_raises(TypeError, nxt.shortest_path, [3., 1., 2.], 1, 2)
110
        assert_raises(ValueError, nxt.shortest_path, [3, 1, 2], 'a', 2)
111
        assert_raises(ValueError, nxt.shortest_path, [3, 1, 2], 1, 'b')
112
        assert_equal(nxt.shortest_path([3, 1, 2], 1, 1), [1])
113

    
114
    def test_shortest_path_length(self):
115
        assert_equal(nxt.shortest_path_length([3, 1, 2], 1), [1, 0, 1, 2, 1, 1])
116
        assert_equal(nxt.shortest_path_length(['d', 'd', 'd', 'i', 'd', 'd'], 1),
117
                     [1, 0, 1, 2, 1, 1])
118
        assert_equal(nxt.shortest_path_length(('d', 'd', 'd', 'i', 'd', 'd'), 1),
119
                     [1, 0, 1, 2, 1, 1])
120
        assert_raises(TypeError, nxt.shortest_path, [3., 1., 2.], 1)
121

    
122
    def random_threshold_sequence(self):
123
        assert_equal(len(nxt.random_threshold_sequence(10, 0.5)), 10)
124
        assert_equal(nxt.random_threshold_sequence(10, 0.5, seed=42),
125
                     ['d', 'i', 'd', 'd', 'd', 'i', 'i', 'i', 'd', 'd'])
126
        assert_raises(ValueError, nxt.random_threshold_sequence, 10, 1.5)
127

    
128
    def test_right_d_threshold_sequence(self):
129
        assert_equal(nxt.right_d_threshold_sequence(3, 2), ['d', 'i', 'd'])
130
        assert_raises(ValueError, nxt.right_d_threshold_sequence, 2, 3)
131

    
132
    def test_left_d_threshold_sequence(self):
133
        assert_equal(nxt.left_d_threshold_sequence(3, 2), ['d', 'i', 'd'])
134
        assert_raises(ValueError, nxt.left_d_threshold_sequence, 2, 3)
135

    
136
    def test_weights_thresholds(self):
137
        wseq = [3, 4, 3, 3, 5, 6, 5, 4, 5, 6]
138
        cs = nxt.weights_to_creation_sequence(wseq, threshold=10)
139
        wseq = nxt.creation_sequence_to_weights(cs)
140
        cs2 = nxt.weights_to_creation_sequence(wseq)
141
        assert_equal(cs, cs2)
142

    
143
        wseq = nxt.creation_sequence_to_weights(nxt.uncompact([3, 1, 2, 3, 3, 2, 3]))
144
        assert_equal(wseq,
145
                     [s * 0.125 for s in [4, 4, 4, 3, 5, 5, 2, 2, 2, 6, 6, 6, 1, 1, 7, 7, 7]])
146

    
147
        wseq = nxt.creation_sequence_to_weights([3, 1, 2, 3, 3, 2, 3])
148
        assert_equal(wseq,
149
                     [s * 0.125 for s in [4, 4, 4, 3, 5, 5, 2, 2, 2, 6, 6, 6, 1, 1, 7, 7, 7]])
150

    
151
        wseq = nxt.creation_sequence_to_weights(list(enumerate('ddidiiidididi')))
152
        assert_equal(wseq,
153
                     [s * 0.1 for s in [5, 5, 4, 6, 3, 3, 3, 7, 2, 8, 1, 9, 0]])
154

    
155
        wseq = nxt.creation_sequence_to_weights('ddidiiidididi')
156
        assert_equal(wseq,
157
                     [s * 0.1 for s in [5, 5, 4, 6, 3, 3, 3, 7, 2, 8, 1, 9, 0]])
158

    
159
        wseq = nxt.creation_sequence_to_weights('ddidiiidididid')
160
        ws = [s / float(12) for s in [6, 6, 5, 7, 4, 4, 4, 8, 3, 9, 2, 10, 1, 11]]
161
        assert_true(sum([abs(c - d) for c, d in zip(wseq, ws)]) < 1e-14)
162

    
163
    def test_finding_routines(self):
164
        G = nx.Graph({1: [2], 2: [3], 3: [4], 4: [5], 5: [6]})
165
        G.add_edge(2, 4)
166
        G.add_edge(2, 5)
167
        G.add_edge(2, 7)
168
        G.add_edge(3, 6)
169
        G.add_edge(4, 6)
170

    
171
        # Alternating 4 cycle
172
        assert_equal(nxt.find_alternating_4_cycle(G), [1, 2, 3, 6])
173

    
174
        # Threshold graph
175
        TG = nxt.find_threshold_graph(G)
176
        assert_true(nxt.is_threshold_graph(TG))
177
        assert_equal(sorted(TG.nodes()), [1, 2, 3, 4, 5, 7])
178

    
179
        cs = nxt.creation_sequence(dict(TG.degree()), with_labels=True)
180
        assert_equal(nxt.find_creation_sequence(G), cs)
181

    
182
    def test_fast_versions_properties_threshold_graphs(self):
183
        cs = 'ddiiddid'
184
        G = nxt.threshold_graph(cs)
185
        assert_equal(nxt.density('ddiiddid'), nx.density(G))
186
        assert_equal(sorted(nxt.degree_sequence(cs)),
187
                     sorted(d for n, d in G.degree()))
188

    
189
        ts = nxt.triangle_sequence(cs)
190
        assert_equal(ts, list(nx.triangles(G).values()))
191
        assert_equal(sum(ts) // 3, nxt.triangles(cs))
192

    
193
        c1 = nxt.cluster_sequence(cs)
194
        c2 = list(nx.clustering(G).values())
195
        assert_almost_equal(sum([abs(c - d) for c, d in zip(c1, c2)]), 0)
196

    
197
        b1 = nx.betweenness_centrality(G).values()
198
        b2 = nxt.betweenness_sequence(cs)
199
        assert_true(sum([abs(c - d) for c, d in zip(b1, b2)]) < 1e-14)
200

    
201
        assert_equal(nxt.eigenvalues(cs), [0, 1, 3, 3, 5, 7, 7, 8])
202

    
203
        # Degree Correlation
204
        assert_true(abs(nxt.degree_correlation(cs) + 0.593038821954) < 1e-12)
205
        assert_equal(nxt.degree_correlation('diiiddi'), -0.8)
206
        assert_equal(nxt.degree_correlation('did'), -1.0)
207
        assert_equal(nxt.degree_correlation('ddd'), 1.0)
208
        assert_equal(nxt.eigenvalues('dddiii'), [0, 0, 0, 0, 3, 3])
209
        assert_equal(nxt.eigenvalues('dddiiid'), [0, 1, 1, 1, 4, 4, 7])
210

    
211
    def test_tg_creation_routines(self):
212
        s = nxt.left_d_threshold_sequence(5, 7)
213
        s = nxt.right_d_threshold_sequence(5, 7)
214
        s1 = nxt.swap_d(s, 1.0, 1.0)
215
        s1 = nxt.swap_d(s, 1.0, 1.0, seed=1)
216

    
217
    @attr('numpy')
218
    def test_eigenvectors(self):
219
        try:
220
            import numpy as N
221
            eigenval = N.linalg.eigvals
222
            import scipy
223
        except ImportError:
224
            raise SkipTest('SciPy not available.')
225

    
226
        cs = 'ddiiddid'
227
        G = nxt.threshold_graph(cs)
228
        (tgeval, tgevec) = nxt.eigenvectors(cs)
229
        dot = N.dot
230
        assert_equal([abs(dot(lv, lv) - 1.0) < 1e-9 for lv in tgevec], [True] * 8)
231
        lapl = nx.laplacian_matrix(G)
232
#        tgev=[ dot(lv,dot(lapl,lv)) for lv in tgevec ]
233
#        assert_true(sum([abs(c-d) for c,d in zip(tgev,tgeval)]) < 1e-9)
234
#        tgev.sort()
235
#        lev=list(eigenval(lapl))
236
#        lev.sort()
237
#        assert_true(sum([abs(c-d) for c,d in zip(tgev,lev)]) < 1e-9)
238

    
239
    def test_create_using(self):
240
        cs = 'ddiiddid'
241
        G = nxt.threshold_graph(cs)
242
        assert_raises(nx.exception.NetworkXError,
243
                      nxt.threshold_graph, cs, create_using=nx.DiGraph())
244
        MG = nxt.threshold_graph(cs, create_using=nx.MultiGraph())
245
        assert_equal(sorted(MG.edges()), sorted(G.edges()))