1"""
2Threshold Graphs
3================
4"""
5
6import pytest
7
8import networkx as nx
9import networkx.algorithms.threshold as nxt
10from networkx.algorithms.isomorphism.isomorph import graph_could_be_isomorphic
11
12cnlti = nx.convert_node_labels_to_integers
13
14
15class TestGeneratorThreshold:
16    def test_threshold_sequence_graph_test(self):
17        G = nx.star_graph(10)
18        assert nxt.is_threshold_graph(G)
19        assert nxt.is_threshold_sequence(list(d for n, d in G.degree()))
20
21        G = nx.complete_graph(10)
22        assert nxt.is_threshold_graph(G)
23        assert nxt.is_threshold_sequence(list(d for n, d in G.degree()))
24
25        deg = [3, 2, 2, 1, 1, 1]
26        assert not nxt.is_threshold_sequence(deg)
27
28        deg = [3, 2, 2, 1]
29        assert nxt.is_threshold_sequence(deg)
30
31        G = nx.generators.havel_hakimi_graph(deg)
32        assert nxt.is_threshold_graph(G)
33
34    def test_creation_sequences(self):
35        deg = [3, 2, 2, 1]
36        G = nx.generators.havel_hakimi_graph(deg)
37
38        with pytest.raises(ValueError):
39            nxt.creation_sequence(deg, with_labels=True, compact=True)
40
41        cs0 = nxt.creation_sequence(deg)
42        H0 = nxt.threshold_graph(cs0)
43        assert "".join(cs0) == "ddid"
44
45        cs1 = nxt.creation_sequence(deg, with_labels=True)
46        H1 = nxt.threshold_graph(cs1)
47        assert cs1 == [(1, "d"), (2, "d"), (3, "i"), (0, "d")]
48
49        cs2 = nxt.creation_sequence(deg, compact=True)
50        H2 = nxt.threshold_graph(cs2)
51        assert cs2 == [2, 1, 1]
52        assert "".join(nxt.uncompact(cs2)) == "ddid"
53        assert graph_could_be_isomorphic(H0, G)
54        assert graph_could_be_isomorphic(H0, H1)
55        assert graph_could_be_isomorphic(H0, H2)
56
57    def test_make_compact(self):
58        assert nxt.make_compact(["d", "d", "d", "i", "d", "d"]) == [3, 1, 2]
59        assert nxt.make_compact([3, 1, 2]) == [3, 1, 2]
60        assert pytest.raises(TypeError, nxt.make_compact, [3.0, 1.0, 2.0])
61
62    def test_uncompact(self):
63        assert nxt.uncompact([3, 1, 2]) == ["d", "d", "d", "i", "d", "d"]
64        assert nxt.uncompact(["d", "d", "i", "d"]) == ["d", "d", "i", "d"]
65        assert nxt.uncompact(
66            nxt.uncompact([(1, "d"), (2, "d"), (3, "i"), (0, "d")])
67        ) == nxt.uncompact([(1, "d"), (2, "d"), (3, "i"), (0, "d")])
68        assert pytest.raises(TypeError, nxt.uncompact, [3.0, 1.0, 2.0])
69
70    def test_creation_sequence_to_weights(self):
71        assert nxt.creation_sequence_to_weights([3, 1, 2]) == [
72            0.5,
73            0.5,
74            0.5,
75            0.25,
76            0.75,
77            0.75,
78        ]
79        assert pytest.raises(
80            TypeError, nxt.creation_sequence_to_weights, [3.0, 1.0, 2.0]
81        )
82
83    def test_weights_to_creation_sequence(self):
84        deg = [3, 2, 2, 1]
85        with pytest.raises(ValueError):
86            nxt.weights_to_creation_sequence(deg, with_labels=True, compact=True)
87        assert nxt.weights_to_creation_sequence(deg, with_labels=True) == [
88            (3, "d"),
89            (1, "d"),
90            (2, "d"),
91            (0, "d"),
92        ]
93        assert nxt.weights_to_creation_sequence(deg, compact=True) == [4]
94
95    def test_find_alternating_4_cycle(self):
96        G = nx.Graph()
97        G.add_edge(1, 2)
98        assert not nxt.find_alternating_4_cycle(G)
99
100    def test_shortest_path(self):
101        deg = [3, 2, 2, 1]
102        G = nx.generators.havel_hakimi_graph(deg)
103        cs1 = nxt.creation_sequence(deg, with_labels=True)
104        for n, m in [(3, 0), (0, 3), (0, 2), (0, 1), (1, 3), (3, 1), (1, 2), (2, 3)]:
105            assert nxt.shortest_path(cs1, n, m) == nx.shortest_path(G, n, m)
106
107        spl = nxt.shortest_path_length(cs1, 3)
108        spl2 = nxt.shortest_path_length([t for v, t in cs1], 2)
109        assert spl == spl2
110
111        spld = {}
112        for j, pl in enumerate(spl):
113            n = cs1[j][0]
114            spld[n] = pl
115        assert spld == nx.single_source_shortest_path_length(G, 3)
116
117        assert nxt.shortest_path(["d", "d", "d", "i", "d", "d"], 1, 2) == [1, 2]
118        assert nxt.shortest_path([3, 1, 2], 1, 2) == [1, 2]
119        assert pytest.raises(TypeError, nxt.shortest_path, [3.0, 1.0, 2.0], 1, 2)
120        assert pytest.raises(ValueError, nxt.shortest_path, [3, 1, 2], "a", 2)
121        assert pytest.raises(ValueError, nxt.shortest_path, [3, 1, 2], 1, "b")
122        assert nxt.shortest_path([3, 1, 2], 1, 1) == [1]
123
124    def test_shortest_path_length(self):
125        assert nxt.shortest_path_length([3, 1, 2], 1) == [1, 0, 1, 2, 1, 1]
126        assert nxt.shortest_path_length(["d", "d", "d", "i", "d", "d"], 1) == [
127            1,
128            0,
129            1,
130            2,
131            1,
132            1,
133        ]
134        assert nxt.shortest_path_length(("d", "d", "d", "i", "d", "d"), 1) == [
135            1,
136            0,
137            1,
138            2,
139            1,
140            1,
141        ]
142        assert pytest.raises(TypeError, nxt.shortest_path, [3.0, 1.0, 2.0], 1)
143
144    def test_random_threshold_sequence(self):
145        assert len(nxt.random_threshold_sequence(10, 0.5)) == 10
146        assert nxt.random_threshold_sequence(10, 0.5, seed=42) == [
147            "d",
148            "i",
149            "d",
150            "d",
151            "d",
152            "i",
153            "i",
154            "i",
155            "d",
156            "d",
157        ]
158        assert pytest.raises(ValueError, nxt.random_threshold_sequence, 10, 1.5)
159
160    def test_right_d_threshold_sequence(self):
161        assert nxt.right_d_threshold_sequence(3, 2) == ["d", "i", "d"]
162        assert pytest.raises(ValueError, nxt.right_d_threshold_sequence, 2, 3)
163
164    def test_left_d_threshold_sequence(self):
165        assert nxt.left_d_threshold_sequence(3, 2) == ["d", "i", "d"]
166        assert pytest.raises(ValueError, nxt.left_d_threshold_sequence, 2, 3)
167
168    def test_weights_thresholds(self):
169        wseq = [3, 4, 3, 3, 5, 6, 5, 4, 5, 6]
170        cs = nxt.weights_to_creation_sequence(wseq, threshold=10)
171        wseq = nxt.creation_sequence_to_weights(cs)
172        cs2 = nxt.weights_to_creation_sequence(wseq)
173        assert cs == cs2
174
175        wseq = nxt.creation_sequence_to_weights(nxt.uncompact([3, 1, 2, 3, 3, 2, 3]))
176        assert wseq == [
177            s * 0.125 for s in [4, 4, 4, 3, 5, 5, 2, 2, 2, 6, 6, 6, 1, 1, 7, 7, 7]
178        ]
179
180        wseq = nxt.creation_sequence_to_weights([3, 1, 2, 3, 3, 2, 3])
181        assert wseq == [
182            s * 0.125 for s in [4, 4, 4, 3, 5, 5, 2, 2, 2, 6, 6, 6, 1, 1, 7, 7, 7]
183        ]
184
185        wseq = nxt.creation_sequence_to_weights(list(enumerate("ddidiiidididi")))
186        assert wseq == [s * 0.1 for s in [5, 5, 4, 6, 3, 3, 3, 7, 2, 8, 1, 9, 0]]
187
188        wseq = nxt.creation_sequence_to_weights("ddidiiidididi")
189        assert wseq == [s * 0.1 for s in [5, 5, 4, 6, 3, 3, 3, 7, 2, 8, 1, 9, 0]]
190
191        wseq = nxt.creation_sequence_to_weights("ddidiiidididid")
192        ws = [s / float(12) for s in [6, 6, 5, 7, 4, 4, 4, 8, 3, 9, 2, 10, 1, 11]]
193        assert sum([abs(c - d) for c, d in zip(wseq, ws)]) < 1e-14
194
195    def test_finding_routines(self):
196        G = nx.Graph({1: [2], 2: [3], 3: [4], 4: [5], 5: [6]})
197        G.add_edge(2, 4)
198        G.add_edge(2, 5)
199        G.add_edge(2, 7)
200        G.add_edge(3, 6)
201        G.add_edge(4, 6)
202
203        # Alternating 4 cycle
204        assert nxt.find_alternating_4_cycle(G) == [1, 2, 3, 6]
205
206        # Threshold graph
207        TG = nxt.find_threshold_graph(G)
208        assert nxt.is_threshold_graph(TG)
209        assert sorted(TG.nodes()) == [1, 2, 3, 4, 5, 7]
210
211        cs = nxt.creation_sequence(dict(TG.degree()), with_labels=True)
212        assert nxt.find_creation_sequence(G) == cs
213
214    def test_fast_versions_properties_threshold_graphs(self):
215        cs = "ddiiddid"
216        G = nxt.threshold_graph(cs)
217        assert nxt.density("ddiiddid") == nx.density(G)
218        assert sorted(nxt.degree_sequence(cs)) == sorted(d for n, d in G.degree())
219
220        ts = nxt.triangle_sequence(cs)
221        assert ts == list(nx.triangles(G).values())
222        assert sum(ts) // 3 == nxt.triangles(cs)
223
224        c1 = nxt.cluster_sequence(cs)
225        c2 = list(nx.clustering(G).values())
226        assert sum([abs(c - d) for c, d in zip(c1, c2)]) == pytest.approx(0, abs=1e-7)
227
228        b1 = nx.betweenness_centrality(G).values()
229        b2 = nxt.betweenness_sequence(cs)
230        assert sum([abs(c - d) for c, d in zip(b1, b2)]) < 1e-14
231
232        assert nxt.eigenvalues(cs) == [0, 1, 3, 3, 5, 7, 7, 8]
233
234        # Degree Correlation
235        assert abs(nxt.degree_correlation(cs) + 0.593038821954) < 1e-12
236        assert nxt.degree_correlation("diiiddi") == -0.8
237        assert nxt.degree_correlation("did") == -1.0
238        assert nxt.degree_correlation("ddd") == 1.0
239        assert nxt.eigenvalues("dddiii") == [0, 0, 0, 0, 3, 3]
240        assert nxt.eigenvalues("dddiiid") == [0, 1, 1, 1, 4, 4, 7]
241
242    def test_tg_creation_routines(self):
243        s = nxt.left_d_threshold_sequence(5, 7)
244        s = nxt.right_d_threshold_sequence(5, 7)
245        s1 = nxt.swap_d(s, 1.0, 1.0)
246        s1 = nxt.swap_d(s, 1.0, 1.0, seed=1)
247
248    def test_eigenvectors(self):
249        np = pytest.importorskip("numpy")
250        eigenval = np.linalg.eigvals
251        pytest.importorskip("scipy")
252
253        cs = "ddiiddid"
254        G = nxt.threshold_graph(cs)
255        (tgeval, tgevec) = nxt.eigenvectors(cs)
256        np.testing.assert_allclose([np.dot(lv, lv) for lv in tgevec], 1.0, rtol=1e-9)
257        lapl = nx.laplacian_matrix(G)
258
259    def test_create_using(self):
260        cs = "ddiiddid"
261        G = nxt.threshold_graph(cs)
262        assert pytest.raises(
263            nx.exception.NetworkXError,
264            nxt.threshold_graph,
265            cs,
266            create_using=nx.DiGraph(),
267        )
268        MG = nxt.threshold_graph(cs, create_using=nx.MultiGraph())
269        assert sorted(MG.edges()) == sorted(G.edges())
270