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
|
import pytest
import networkx
import networkx as nx
import networkx.algorithms.regular as reg
import networkx.generators as gen
class TestKFactor:
def test_k_factor_trivial(self):
g = gen.cycle_graph(4)
f = reg.k_factor(g, 2)
assert g.edges == f.edges
def test_k_factor1(self):
g = gen.grid_2d_graph(4, 4)
g_kf = reg.k_factor(g, 2)
for edge in g_kf.edges():
assert g.has_edge(edge[0], edge[1])
for _, degree in g_kf.degree():
assert degree == 2
def test_k_factor2(self):
g = gen.complete_graph(6)
g_kf = reg.k_factor(g, 3)
for edge in g_kf.edges():
assert g.has_edge(edge[0], edge[1])
for _, degree in g_kf.degree():
assert degree == 3
def test_k_factor3(self):
g = gen.grid_2d_graph(4, 4)
with pytest.raises(nx.NetworkXUnfeasible):
reg.k_factor(g, 3)
def test_k_factor4(self):
g = gen.lattice.hexagonal_lattice_graph(4, 4)
# Perfect matching doesn't exist for 4,4 hexagonal lattice graph
with pytest.raises(nx.NetworkXUnfeasible):
reg.k_factor(g, 2)
def test_k_factor5(self):
g = gen.complete_graph(6)
# small k to exercise SmallKGadget
g_kf = reg.k_factor(g, 2)
for edge in g_kf.edges():
assert g.has_edge(edge[0], edge[1])
for _, degree in g_kf.degree():
assert degree == 2
class TestIsRegular:
def test_is_regular1(self):
g = gen.cycle_graph(4)
assert reg.is_regular(g)
def test_is_regular2(self):
g = gen.complete_graph(5)
assert reg.is_regular(g)
def test_is_regular3(self):
g = gen.lollipop_graph(5, 5)
assert not reg.is_regular(g)
def test_is_regular4(self):
g = nx.DiGraph()
g.add_edges_from([(0, 1), (1, 2), (2, 0)])
assert reg.is_regular(g)
def test_is_regular_empty_graph_raises():
G = nx.Graph()
with pytest.raises(nx.NetworkXPointlessConcept, match="Graph has no nodes"):
nx.is_regular(G)
class TestIsKRegular:
def test_is_k_regular1(self):
g = gen.cycle_graph(4)
assert reg.is_k_regular(g, 2)
assert not reg.is_k_regular(g, 3)
def test_is_k_regular2(self):
g = gen.complete_graph(5)
assert reg.is_k_regular(g, 4)
assert not reg.is_k_regular(g, 3)
assert not reg.is_k_regular(g, 6)
def test_is_k_regular3(self):
g = gen.lollipop_graph(5, 5)
assert not reg.is_k_regular(g, 5)
assert not reg.is_k_regular(g, 6)
|