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
163
|
"""Unit tests for the :mod:`networkx.algorithms.tournament` module."""
from itertools import combinations
import pytest
from networkx import DiGraph
from networkx.algorithms.tournament import (
hamiltonian_path,
index_satisfying,
is_reachable,
is_strongly_connected,
is_tournament,
random_tournament,
score_sequence,
tournament_matrix,
)
def test_condition_not_satisfied():
condition = lambda x: x > 0
iter_in = [0]
assert index_satisfying(iter_in, condition) == 1
def test_empty_iterable():
condition = lambda x: x > 0
with pytest.raises(ValueError):
index_satisfying([], condition)
def test_is_tournament():
G = DiGraph()
G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
assert is_tournament(G)
def test_self_loops():
"""A tournament must have no self-loops."""
G = DiGraph()
G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
G.add_edge(0, 0)
assert not is_tournament(G)
def test_missing_edges():
"""A tournament must not have any pair of nodes without at least
one edge joining the pair.
"""
G = DiGraph()
G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)])
assert not is_tournament(G)
def test_bidirectional_edges():
"""A tournament must not have any pair of nodes with greater
than one edge joining the pair.
"""
G = DiGraph()
G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
G.add_edge(1, 0)
assert not is_tournament(G)
def test_graph_is_tournament():
for _ in range(10):
G = random_tournament(5)
assert is_tournament(G)
def test_graph_is_tournament_seed():
for _ in range(10):
G = random_tournament(5, seed=1)
assert is_tournament(G)
def test_graph_is_tournament_one_node():
G = random_tournament(1)
assert is_tournament(G)
def test_graph_is_tournament_zero_node():
G = random_tournament(0)
assert is_tournament(G)
def test_hamiltonian_empty_graph():
path = hamiltonian_path(DiGraph())
assert len(path) == 0
def test_path_is_hamiltonian():
G = DiGraph()
G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
path = hamiltonian_path(G)
assert len(path) == 4
assert all(v in G[u] for u, v in zip(path, path[1:]))
def test_hamiltonian_cycle():
"""Tests that :func:`networkx.tournament.hamiltonian_path`
returns a Hamiltonian cycle when provided a strongly connected
tournament.
"""
G = DiGraph()
G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
path = hamiltonian_path(G)
assert len(path) == 4
assert all(v in G[u] for u, v in zip(path, path[1:]))
assert path[0] in G[path[-1]]
def test_score_sequence_edge():
G = DiGraph([(0, 1)])
assert score_sequence(G) == [0, 1]
def test_score_sequence_triangle():
G = DiGraph([(0, 1), (1, 2), (2, 0)])
assert score_sequence(G) == [1, 1, 1]
def test_tournament_matrix():
np = pytest.importorskip("numpy")
pytest.importorskip("scipy")
npt = np.testing
G = DiGraph([(0, 1)])
m = tournament_matrix(G)
npt.assert_array_equal(m.todense(), np.array([[0, 1], [-1, 0]]))
def test_reachable_pair():
"""Tests for a reachable pair of nodes."""
G = DiGraph([(0, 1), (1, 2), (2, 0)])
assert is_reachable(G, 0, 2)
def test_same_node_is_reachable():
"""Tests that a node is always reachable from it."""
# G is an arbitrary tournament on ten nodes.
G = DiGraph(sorted(p) for p in combinations(range(10), 2))
assert all(is_reachable(G, v, v) for v in G)
def test_unreachable_pair():
"""Tests for an unreachable pair of nodes."""
G = DiGraph([(0, 1), (0, 2), (1, 2)])
assert not is_reachable(G, 1, 0)
def test_is_strongly_connected():
"""Tests for a strongly connected tournament."""
G = DiGraph([(0, 1), (1, 2), (2, 0)])
assert is_strongly_connected(G)
def test_not_strongly_connected():
"""Tests for a tournament that is not strongly connected."""
G = DiGraph([(0, 1), (0, 2), (1, 2)])
assert not is_strongly_connected(G)
|
