Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_distance_measures.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 from random import Random | |
2 | |
3 import pytest | |
4 | |
5 | |
6 import networkx as nx | |
7 from networkx import convert_node_labels_to_integers as cnlti | |
8 | |
9 | |
10 class TestDistance: | |
11 def setup_method(self): | |
12 G = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted") | |
13 self.G = G | |
14 | |
15 def test_eccentricity(self): | |
16 assert nx.eccentricity(self.G, 1) == 6 | |
17 e = nx.eccentricity(self.G) | |
18 assert e[1] == 6 | |
19 | |
20 sp = dict(nx.shortest_path_length(self.G)) | |
21 e = nx.eccentricity(self.G, sp=sp) | |
22 assert e[1] == 6 | |
23 | |
24 e = nx.eccentricity(self.G, v=1) | |
25 assert e == 6 | |
26 | |
27 # This behavior changed in version 1.8 (ticket #739) | |
28 e = nx.eccentricity(self.G, v=[1, 1]) | |
29 assert e[1] == 6 | |
30 e = nx.eccentricity(self.G, v=[1, 2]) | |
31 assert e[1] == 6 | |
32 | |
33 # test against graph with one node | |
34 G = nx.path_graph(1) | |
35 e = nx.eccentricity(G) | |
36 assert e[0] == 0 | |
37 e = nx.eccentricity(G, v=0) | |
38 assert e == 0 | |
39 pytest.raises(nx.NetworkXError, nx.eccentricity, G, 1) | |
40 | |
41 # test against empty graph | |
42 G = nx.empty_graph() | |
43 e = nx.eccentricity(G) | |
44 assert e == {} | |
45 | |
46 def test_diameter(self): | |
47 assert nx.diameter(self.G) == 6 | |
48 | |
49 def test_radius(self): | |
50 assert nx.radius(self.G) == 4 | |
51 | |
52 def test_periphery(self): | |
53 assert set(nx.periphery(self.G)) == {1, 4, 13, 16} | |
54 | |
55 def test_center(self): | |
56 assert set(nx.center(self.G)) == {6, 7, 10, 11} | |
57 | |
58 def test_bound_diameter(self): | |
59 assert nx.diameter(self.G, usebounds=True) == 6 | |
60 | |
61 def test_bound_radius(self): | |
62 assert nx.radius(self.G, usebounds=True) == 4 | |
63 | |
64 def test_bound_periphery(self): | |
65 result = {1, 4, 13, 16} | |
66 assert set(nx.periphery(self.G, usebounds=True)) == result | |
67 | |
68 def test_bound_center(self): | |
69 result = {6, 7, 10, 11} | |
70 assert set(nx.center(self.G, usebounds=True)) == result | |
71 | |
72 def test_radius_exception(self): | |
73 G = nx.Graph() | |
74 G.add_edge(1, 2) | |
75 G.add_edge(3, 4) | |
76 pytest.raises(nx.NetworkXError, nx.diameter, G) | |
77 | |
78 def test_eccentricity_infinite(self): | |
79 with pytest.raises(nx.NetworkXError): | |
80 G = nx.Graph([(1, 2), (3, 4)]) | |
81 e = nx.eccentricity(G) | |
82 | |
83 def test_eccentricity_undirected_not_connected(self): | |
84 with pytest.raises(nx.NetworkXError): | |
85 G = nx.Graph([(1, 2), (3, 4)]) | |
86 e = nx.eccentricity(G, sp=1) | |
87 | |
88 def test_eccentricity_directed_weakly_connected(self): | |
89 with pytest.raises(nx.NetworkXError): | |
90 DG = nx.DiGraph([(1, 2), (1, 3)]) | |
91 nx.eccentricity(DG) | |
92 | |
93 | |
94 class TestResistanceDistance: | |
95 @classmethod | |
96 def setup_class(cls): | |
97 global np | |
98 global sp_sparse | |
99 np = pytest.importorskip("numpy") | |
100 scipy = pytest.importorskip("scipy") | |
101 sp_sparse = pytest.importorskip("scipy.sparse") | |
102 | |
103 def setup_method(self): | |
104 G = nx.Graph() | |
105 G.add_edge(1, 2, weight=2) | |
106 G.add_edge(2, 3, weight=4) | |
107 G.add_edge(3, 4, weight=1) | |
108 G.add_edge(1, 4, weight=3) | |
109 self.G = G | |
110 | |
111 def test_laplacian_submatrix(self): | |
112 from networkx.algorithms.distance_measures import _laplacian_submatrix | |
113 | |
114 M = sp_sparse.csr_matrix([[1, 2, 3], [4, 5, 6], [7, 8, 9]], dtype=np.float32) | |
115 N = sp_sparse.csr_matrix([[5, 6], [8, 9]], dtype=np.float32) | |
116 Mn, Mn_nodelist = _laplacian_submatrix(1, M, [1, 2, 3]) | |
117 assert Mn_nodelist == [2, 3] | |
118 assert np.allclose(Mn.toarray(), N.toarray()) | |
119 | |
120 def test_laplacian_submatrix_square(self): | |
121 with pytest.raises(nx.NetworkXError): | |
122 from networkx.algorithms.distance_measures import _laplacian_submatrix | |
123 | |
124 M = sp_sparse.csr_matrix([[1, 2], [4, 5], [7, 8]], dtype=np.float32) | |
125 _laplacian_submatrix(1, M, [1, 2, 3]) | |
126 | |
127 def test_laplacian_submatrix_matrix_node_dim(self): | |
128 with pytest.raises(nx.NetworkXError): | |
129 from networkx.algorithms.distance_measures import _laplacian_submatrix | |
130 | |
131 M = sp_sparse.csr_matrix( | |
132 [[1, 2, 3], [4, 5, 6], [7, 8, 9]], dtype=np.float32 | |
133 ) | |
134 _laplacian_submatrix(1, M, [1, 2, 3, 4]) | |
135 | |
136 def test_resistance_distance(self): | |
137 rd = nx.resistance_distance(self.G, 1, 3, "weight", True) | |
138 test_data = 1 / (1 / (2 + 4) + 1 / (1 + 3)) | |
139 assert round(rd, 5) == round(test_data, 5) | |
140 | |
141 def test_resistance_distance_noinv(self): | |
142 rd = nx.resistance_distance(self.G, 1, 3, "weight", False) | |
143 test_data = 1 / (1 / (1 / 2 + 1 / 4) + 1 / (1 / 1 + 1 / 3)) | |
144 assert round(rd, 5) == round(test_data, 5) | |
145 | |
146 def test_resistance_distance_no_weight(self): | |
147 rd = nx.resistance_distance(self.G, 1, 3) | |
148 assert round(rd, 5) == 1 | |
149 | |
150 def test_resistance_distance_neg_weight(self): | |
151 self.G[2][3]["weight"] = -4 | |
152 rd = nx.resistance_distance(self.G, 1, 3, "weight", True) | |
153 test_data = 1 / (1 / (2 + -4) + 1 / (1 + 3)) | |
154 assert round(rd, 5) == round(test_data, 5) | |
155 | |
156 def test_multigraph(self): | |
157 G = nx.MultiGraph() | |
158 G.add_edge(1, 2, weight=2) | |
159 G.add_edge(2, 3, weight=4) | |
160 G.add_edge(3, 4, weight=1) | |
161 G.add_edge(1, 4, weight=3) | |
162 rd = nx.resistance_distance(G, 1, 3, "weight", True) | |
163 assert np.isclose(rd, 1 / (1 / (2 + 4) + 1 / (1 + 3))) | |
164 | |
165 def test_resistance_distance_div0(self): | |
166 with pytest.raises(ZeroDivisionError): | |
167 self.G[1][2]["weight"] = 0 | |
168 nx.resistance_distance(self.G, 1, 3, "weight") | |
169 | |
170 def test_resistance_distance_not_connected(self): | |
171 with pytest.raises(nx.NetworkXError): | |
172 self.G.add_node(5) | |
173 nx.resistance_distance(self.G, 1, 5) | |
174 | |
175 def test_resistance_distance_same_node(self): | |
176 with pytest.raises(nx.NetworkXError): | |
177 nx.resistance_distance(self.G, 1, 1) | |
178 | |
179 def test_resistance_distance_nodeA_not_in_graph(self): | |
180 with pytest.raises(nx.NetworkXError): | |
181 nx.resistance_distance(self.G, 9, 1) | |
182 | |
183 def test_resistance_distance_nodeB_not_in_graph(self): | |
184 with pytest.raises(nx.NetworkXError): | |
185 nx.resistance_distance(self.G, 1, 9) | |
186 | |
187 | |
188 class TestBarycenter: | |
189 """Test :func:`networkx.algorithms.distance_measures.barycenter`.""" | |
190 | |
191 def barycenter_as_subgraph(self, g, **kwargs): | |
192 """Return the subgraph induced on the barycenter of g""" | |
193 b = nx.barycenter(g, **kwargs) | |
194 assert isinstance(b, list) | |
195 assert set(b) <= set(g) | |
196 return g.subgraph(b) | |
197 | |
198 def test_must_be_connected(self): | |
199 pytest.raises(nx.NetworkXNoPath, nx.barycenter, nx.empty_graph(5)) | |
200 | |
201 def test_sp_kwarg(self): | |
202 # Complete graph K_5. Normally it works... | |
203 K_5 = nx.complete_graph(5) | |
204 sp = dict(nx.shortest_path_length(K_5)) | |
205 assert nx.barycenter(K_5, sp=sp) == list(K_5) | |
206 | |
207 # ...but not with the weight argument | |
208 for u, v, data in K_5.edges.data(): | |
209 data["weight"] = 1 | |
210 pytest.raises(ValueError, nx.barycenter, K_5, sp=sp, weight="weight") | |
211 | |
212 # ...and a corrupted sp can make it seem like K_5 is disconnected | |
213 del sp[0][1] | |
214 pytest.raises(nx.NetworkXNoPath, nx.barycenter, K_5, sp=sp) | |
215 | |
216 def test_trees(self): | |
217 """The barycenter of a tree is a single vertex or an edge. | |
218 | |
219 See [West01]_, p. 78. | |
220 """ | |
221 prng = Random(0xDEADBEEF) | |
222 for i in range(50): | |
223 RT = nx.random_tree(prng.randint(1, 75), prng) | |
224 b = self.barycenter_as_subgraph(RT) | |
225 if len(b) == 2: | |
226 assert b.size() == 1 | |
227 else: | |
228 assert len(b) == 1 | |
229 assert b.size() == 0 | |
230 | |
231 def test_this_one_specific_tree(self): | |
232 """Test the tree pictured at the bottom of [West01]_, p. 78.""" | |
233 g = nx.Graph( | |
234 { | |
235 "a": ["b"], | |
236 "b": ["a", "x"], | |
237 "x": ["b", "y"], | |
238 "y": ["x", "z"], | |
239 "z": ["y", 0, 1, 2, 3, 4], | |
240 0: ["z"], | |
241 1: ["z"], | |
242 2: ["z"], | |
243 3: ["z"], | |
244 4: ["z"], | |
245 } | |
246 ) | |
247 b = self.barycenter_as_subgraph(g, attr="barycentricity") | |
248 assert list(b) == ["z"] | |
249 assert not b.edges | |
250 expected_barycentricity = { | |
251 0: 23, | |
252 1: 23, | |
253 2: 23, | |
254 3: 23, | |
255 4: 23, | |
256 "a": 35, | |
257 "b": 27, | |
258 "x": 21, | |
259 "y": 17, | |
260 "z": 15, | |
261 } | |
262 for node, barycentricity in expected_barycentricity.items(): | |
263 assert g.nodes[node]["barycentricity"] == barycentricity | |
264 | |
265 # Doubling weights should do nothing but double the barycentricities | |
266 for edge in g.edges: | |
267 g.edges[edge]["weight"] = 2 | |
268 b = self.barycenter_as_subgraph(g, weight="weight", attr="barycentricity2") | |
269 assert list(b) == ["z"] | |
270 assert not b.edges | |
271 for node, barycentricity in expected_barycentricity.items(): | |
272 assert g.nodes[node]["barycentricity2"] == barycentricity * 2 |