Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / tests / test_degree_seq.py @ 5cef0f13

History | View | Annotate | Download (7.08 KB)

1
from nose.tools import assert_equal
2
from nose.tools import assert_raises
3
from nose.tools import assert_true
4
from nose.tools import raises
5

    
6
import networkx as nx
7

    
8

    
9
class TestConfigurationModel(object):
10
    """Unit tests for the :func:`~networkx.configuration_model`
11
    function.
12

13
    """
14

    
15
    def test_empty_degree_sequence(self):
16
        """Tests that an empty degree sequence yields the null graph."""
17
        G = nx.configuration_model([])
18
        assert_equal(len(G), 0)
19

    
20
    def test_degree_zero(self):
21
        """Tests that a degree sequence of all zeros yields the empty
22
        graph.
23

24
        """
25
        G = nx.configuration_model([0, 0, 0])
26
        assert_equal(len(G), 3)
27
        assert_equal(G.number_of_edges(), 0)
28

    
29
    def test_degree_sequence(self):
30
        """Tests that the degree sequence of the generated graph matches
31
        the input degree sequence.
32

33
        """
34
        deg_seq = [5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1]
35
        G = nx.configuration_model(deg_seq, seed=12345678)
36
        assert_equal(sorted((d for n, d in G.degree()), reverse=True),
37
                     [5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1])
38
        assert_equal(sorted((d for n, d in G.degree(range(len(deg_seq)))),
39
                            reverse=True),
40
                     [5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1])
41

    
42
    def test_random_seed(self):
43
        """Tests that each call with the same random seed generates the
44
        same graph.
45

46
        """
47
        deg_seq = [3] * 12
48
        G1 = nx.configuration_model(deg_seq, seed=1000)
49
        G2 = nx.configuration_model(deg_seq, seed=1000)
50
        assert_true(nx.is_isomorphic(G1, G2))
51
        G1 = nx.configuration_model(deg_seq, seed=10)
52
        G2 = nx.configuration_model(deg_seq, seed=10)
53
        assert_true(nx.is_isomorphic(G1, G2))
54

    
55
    @raises(nx.NetworkXNotImplemented)
56
    def test_directed_disallowed(self):
57
        """Tests that attempting to create a configuration model graph
58
        using a directed graph yields an exception.
59

60
        """
61
        nx.configuration_model([], create_using=nx.DiGraph())
62

    
63
    @raises(nx.NetworkXError)
64
    def test_odd_degree_sum(self):
65
        """Tests that a degree sequence whose sum is odd yields an
66
        exception.
67

68
        """
69
        nx.configuration_model([1, 2])
70

    
71

    
72
@raises(nx.NetworkXError)
73
def test_directed_configuation_raise_unequal():
74
    zin = [5, 3, 3, 3, 3, 2, 2, 2, 1, 1]
75
    zout = [5, 3, 3, 3, 3, 2, 2, 2, 1, 2]
76
    nx.directed_configuration_model(zin, zout)
77

    
78

    
79
def test_directed_configuation_model():
80
    G = nx.directed_configuration_model([], [], seed=0)
81
    assert_equal(len(G), 0)
82

    
83

    
84
def test_simple_directed_configuation_model():
85
    G = nx.directed_configuration_model([1, 1], [1, 1], seed=0)
86
    assert_equal(len(G), 2)
87

    
88

    
89
def test_expected_degree_graph_empty():
90
    # empty graph has empty degree sequence
91
    deg_seq = []
92
    G = nx.expected_degree_graph(deg_seq)
93
    assert_equal(dict(G.degree()), {})
94

    
95

    
96
def test_expected_degree_graph():
97
    # test that fixed seed delivers the same graph
98
    deg_seq = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
99
    G1 = nx.expected_degree_graph(deg_seq, seed=1000)
100
    assert_equal(len(G1), 12)
101

    
102
    G2 = nx.expected_degree_graph(deg_seq, seed=1000)
103
    assert_true(nx.is_isomorphic(G1, G2))
104

    
105
    G1 = nx.expected_degree_graph(deg_seq, seed=10)
106
    G2 = nx.expected_degree_graph(deg_seq, seed=10)
107
    assert_true(nx.is_isomorphic(G1, G2))
108

    
109

    
110
def test_expected_degree_graph_selfloops():
111
    deg_seq = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
112
    G1 = nx.expected_degree_graph(deg_seq, seed=1000, selfloops=False)
113
    G2 = nx.expected_degree_graph(deg_seq, seed=1000, selfloops=False)
114
    assert_true(nx.is_isomorphic(G1, G2))
115
    assert_equal(len(G1), 12)
116

    
117

    
118
def test_expected_degree_graph_skew():
119
    deg_seq = [10, 2, 2, 2, 2]
120
    G1 = nx.expected_degree_graph(deg_seq, seed=1000)
121
    G2 = nx.expected_degree_graph(deg_seq, seed=1000)
122
    assert_true(nx.is_isomorphic(G1, G2))
123
    assert_equal(len(G1), 5)
124

    
125

    
126
def test_havel_hakimi_construction():
127
    G = nx.havel_hakimi_graph([])
128
    assert_equal(len(G), 0)
129

    
130
    z = [1000, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1]
131
    assert_raises(nx.NetworkXError, nx.havel_hakimi_graph, z)
132
    z = ["A", 3, 3, 3, 3, 2, 2, 2, 1, 1, 1]
133
    assert_raises(nx.NetworkXError, nx.havel_hakimi_graph, z)
134

    
135
    z = [5, 4, 3, 3, 3, 2, 2, 2]
136
    G = nx.havel_hakimi_graph(z)
137
    G = nx.configuration_model(z)
138
    z = [6, 5, 4, 4, 2, 1, 1, 1]
139
    assert_raises(nx.NetworkXError, nx.havel_hakimi_graph, z)
140

    
141
    z = [10, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2]
142

    
143
    G = nx.havel_hakimi_graph(z)
144

    
145
    assert_raises(nx.NetworkXError, nx.havel_hakimi_graph, z,
146
                  create_using=nx.DiGraph())
147

    
148

    
149
def test_directed_havel_hakimi():
150
    # Test range of valid directed degree sequences
151
    n, r = 100, 10
152
    p = 1.0 / r
153
    for i in range(r):
154
        G1 = nx.erdos_renyi_graph(n, p * (i + 1), None, True)
155
        din1 = list(d for n, d in G1.in_degree())
156
        dout1 = list(d for n, d in G1.out_degree())
157
        G2 = nx.directed_havel_hakimi_graph(din1, dout1)
158
        din2 = list(d for n, d in G2.in_degree())
159
        dout2 = list(d for n, d in G2.out_degree())
160
        assert_equal(sorted(din1), sorted(din2))
161
        assert_equal(sorted(dout1), sorted(dout2))
162

    
163
    # Test non-graphical sequence
164
    dout = [1000, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1]
165
    din = [103, 102, 102, 102, 102, 102, 102, 102, 102, 102]
166
    assert_raises(nx.exception.NetworkXError,
167
                  nx.directed_havel_hakimi_graph, din, dout)
168
    # Test valid sequences
169
    dout = [1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
170
    din = [2, 2, 2, 2, 2, 2, 2, 2, 0, 2]
171
    G2 = nx.directed_havel_hakimi_graph(din, dout)
172
    dout2 = (d for n, d in G2.out_degree())
173
    din2 = (d for n, d in G2.in_degree())
174
    assert_equal(sorted(dout), sorted(dout2))
175
    assert_equal(sorted(din), sorted(din2))
176
    # Test unequal sums
177
    din = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
178
    assert_raises(nx.exception.NetworkXError,
179
                  nx.directed_havel_hakimi_graph, din, dout)
180
    # Test for negative values
181
    din = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, -2]
182
    assert_raises(nx.exception.NetworkXError,
183
                  nx.directed_havel_hakimi_graph, din, dout)
184

    
185

    
186
def test_degree_sequence_tree():
187
    z = [1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
188
    G = nx.degree_sequence_tree(z)
189
    assert_equal(len(G), len(z))
190
    assert_true(len(list(G.edges())) == sum(z) / 2)
191

    
192
    assert_raises(nx.NetworkXError, nx.degree_sequence_tree, z,
193
                  create_using=nx.DiGraph())
194

    
195
    z = [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
196
    assert_raises(nx.NetworkXError, nx.degree_sequence_tree, z)
197

    
198

    
199
def test_random_degree_sequence_graph():
200
    d = [1, 2, 2, 3]
201
    G = nx.random_degree_sequence_graph(d, seed=42)
202
    assert_equal(d, sorted(d for n, d in G.degree()))
203
    G = nx.random_degree_sequence_graph(d)
204
    assert_equal(d, sorted(d for n, d in G.degree()))
205

    
206

    
207
def test_random_degree_sequence_graph_raise():
208
    z = [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
209
    assert_raises(nx.NetworkXUnfeasible, nx.random_degree_sequence_graph, z)
210

    
211

    
212
def test_random_degree_sequence_large():
213
    G1 = nx.fast_gnp_random_graph(100, 0.1)
214
    d1 = (d for n, d in G1.degree())
215
    G2 = nx.random_degree_sequence_graph(d1, seed=42)
216
    d2 = (d for n, d in G2.degree())
217
    assert_equal(sorted(d1), sorted(d2))