1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
"""Unit tests for the :mod:`networkx.generators.expanders` module."""
import pytest
import networkx as nx
@pytest.mark.parametrize("n", (2, 3, 5, 6, 10))
def test_margulis_gabber_galil_graph_properties(n):
g = nx.margulis_gabber_galil_graph(n)
assert g.number_of_nodes() == n * n
for node in g:
assert g.degree(node) == 8
assert len(node) == 2
for i in node:
assert int(i) == i
assert 0 <= i < n
@pytest.mark.parametrize("n", (2, 3, 5, 6, 10))
def test_margulis_gabber_galil_graph_eigvals(n):
np = pytest.importorskip("numpy")
sp = pytest.importorskip("scipy")
g = nx.margulis_gabber_galil_graph(n)
# Eigenvalues are already sorted using the scipy eigvalsh,
# but the implementation in numpy does not guarantee order.
w = sorted(sp.linalg.eigvalsh(nx.adjacency_matrix(g).toarray()))
assert w[-2] < 5 * np.sqrt(2)
@pytest.mark.parametrize("p", (3, 5, 7, 11)) # Primes
def test_chordal_cycle_graph(p):
"""Test for the :func:`networkx.chordal_cycle_graph` function."""
G = nx.chordal_cycle_graph(p)
assert len(G) == p
# TODO The second largest eigenvalue should be smaller than a constant,
# independent of the number of nodes in the graph:
#
# eigs = sorted(sp.linalg.eigvalsh(nx.adjacency_matrix(G).toarray()))
# assert_less(eigs[-2], ...)
#
@pytest.mark.parametrize("p", (3, 5, 7, 11, 13)) # Primes
def test_paley_graph(p):
"""Test for the :func:`networkx.paley_graph` function."""
G = nx.paley_graph(p)
# G has p nodes
assert len(G) == p
# G is (p-1)/2-regular
in_degrees = {G.in_degree(node) for node in G.nodes}
out_degrees = {G.out_degree(node) for node in G.nodes}
assert len(in_degrees) == 1 and in_degrees.pop() == (p - 1) // 2
assert len(out_degrees) == 1 and out_degrees.pop() == (p - 1) // 2
# If p = 1 mod 4, -1 is a square mod 4 and therefore the
# edge in the Paley graph are symmetric.
if p % 4 == 1:
for u, v in G.edges:
assert (v, u) in G.edges
@pytest.mark.parametrize("d, n", [(2, 7), (4, 10), (4, 16)])
def test_maybe_regular_expander(d, n):
pytest.importorskip("numpy")
G = nx.maybe_regular_expander(n, d)
assert len(G) == n, "Should have n nodes"
assert len(G.edges) == n * d / 2, "Should have n*d/2 edges"
assert nx.is_k_regular(G, d), "Should be d-regular"
@pytest.mark.parametrize("n", (3, 5, 6, 10))
def test_is_regular_expander(n):
pytest.importorskip("numpy")
pytest.importorskip("scipy")
G = nx.complete_graph(n)
assert nx.is_regular_expander(G) == True, "Should be a regular expander"
@pytest.mark.parametrize("d, n", [(2, 7), (4, 10), (4, 16)])
def test_random_regular_expander(d, n):
pytest.importorskip("numpy")
pytest.importorskip("scipy")
G = nx.random_regular_expander_graph(n, d)
assert len(G) == n, "Should have n nodes"
assert len(G.edges) == n * d / 2, "Should have n*d/2 edges"
assert nx.is_k_regular(G, d), "Should be d-regular"
assert nx.is_regular_expander(G) == True, "Should be a regular expander"
def test_random_regular_expander_explicit_construction():
pytest.importorskip("numpy")
pytest.importorskip("scipy")
G = nx.random_regular_expander_graph(d=4, n=5)
assert len(G) == 5 and len(G.edges) == 10, "Should be a complete graph"
@pytest.mark.parametrize("graph_type", (nx.Graph, nx.DiGraph, nx.MultiDiGraph))
def test_margulis_gabber_galil_graph_badinput(graph_type):
with pytest.raises(
nx.NetworkXError, match="`create_using` must be an undirected multigraph"
):
nx.margulis_gabber_galil_graph(3, create_using=graph_type)
@pytest.mark.parametrize("graph_type", (nx.Graph, nx.DiGraph, nx.MultiDiGraph))
def test_chordal_cycle_graph_badinput(graph_type):
with pytest.raises(
nx.NetworkXError, match="`create_using` must be an undirected multigraph"
):
nx.chordal_cycle_graph(3, create_using=graph_type)
def test_paley_graph_badinput():
with pytest.raises(
nx.NetworkXError, match="`create_using` cannot be a multigraph."
):
nx.paley_graph(3, create_using=nx.MultiGraph)
def test_maybe_regular_expander_badinput():
pytest.importorskip("numpy")
pytest.importorskip("scipy")
with pytest.raises(nx.NetworkXError, match="n must be a positive integer"):
nx.maybe_regular_expander(n=-1, d=2)
with pytest.raises(nx.NetworkXError, match="d must be greater than or equal to 2"):
nx.maybe_regular_expander(n=10, d=0)
with pytest.raises(nx.NetworkXError, match="Need n-1>= d to have room"):
nx.maybe_regular_expander(n=5, d=6)
def test_is_regular_expander_badinput():
pytest.importorskip("numpy")
pytest.importorskip("scipy")
with pytest.raises(nx.NetworkXError, match="epsilon must be non negative"):
nx.is_regular_expander(nx.Graph(), epsilon=-1)
def test_random_regular_expander_badinput():
pytest.importorskip("numpy")
pytest.importorskip("scipy")
with pytest.raises(nx.NetworkXError, match="n must be a positive integer"):
nx.random_regular_expander_graph(n=-1, d=2)
with pytest.raises(nx.NetworkXError, match="d must be greater than or equal to 2"):
nx.random_regular_expander_graph(n=10, d=0)
with pytest.raises(nx.NetworkXError, match="Need n-1>= d to have room"):
nx.random_regular_expander_graph(n=5, d=6)
with pytest.raises(nx.NetworkXError, match="epsilon must be non negative"):
nx.random_regular_expander_graph(n=4, d=2, epsilon=-1)
|
