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