Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/tests/test_connectivity.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 import pytest | |
2 | |
3 import networkx as nx | |
4 from networkx.algorithms import approximation as approx | |
5 | |
6 | |
7 def test_global_node_connectivity(): | |
8 # Figure 1 chapter on Connectivity | |
9 G = nx.Graph() | |
10 G.add_edges_from( | |
11 [ | |
12 (1, 2), | |
13 (1, 3), | |
14 (1, 4), | |
15 (1, 5), | |
16 (2, 3), | |
17 (2, 6), | |
18 (3, 4), | |
19 (3, 6), | |
20 (4, 6), | |
21 (4, 7), | |
22 (5, 7), | |
23 (6, 8), | |
24 (6, 9), | |
25 (7, 8), | |
26 (7, 10), | |
27 (8, 11), | |
28 (9, 10), | |
29 (9, 11), | |
30 (10, 11), | |
31 ] | |
32 ) | |
33 assert 2 == approx.local_node_connectivity(G, 1, 11) | |
34 assert 2 == approx.node_connectivity(G) | |
35 assert 2 == approx.node_connectivity(G, 1, 11) | |
36 | |
37 | |
38 def test_white_harary1(): | |
39 # Figure 1b white and harary (2001) | |
40 # A graph with high adhesion (edge connectivity) and low cohesion | |
41 # (node connectivity) | |
42 G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4)) | |
43 G.remove_node(7) | |
44 for i in range(4, 7): | |
45 G.add_edge(0, i) | |
46 G = nx.disjoint_union(G, nx.complete_graph(4)) | |
47 G.remove_node(G.order() - 1) | |
48 for i in range(7, 10): | |
49 G.add_edge(0, i) | |
50 assert 1 == approx.node_connectivity(G) | |
51 | |
52 | |
53 def test_complete_graphs(): | |
54 for n in range(5, 25, 5): | |
55 G = nx.complete_graph(n) | |
56 assert n - 1 == approx.node_connectivity(G) | |
57 assert n - 1 == approx.node_connectivity(G, 0, 3) | |
58 | |
59 | |
60 def test_empty_graphs(): | |
61 for k in range(5, 25, 5): | |
62 G = nx.empty_graph(k) | |
63 assert 0 == approx.node_connectivity(G) | |
64 assert 0 == approx.node_connectivity(G, 0, 3) | |
65 | |
66 | |
67 def test_petersen(): | |
68 G = nx.petersen_graph() | |
69 assert 3 == approx.node_connectivity(G) | |
70 assert 3 == approx.node_connectivity(G, 0, 5) | |
71 | |
72 | |
73 # Approximation fails with tutte graph | |
74 # def test_tutte(): | |
75 # G = nx.tutte_graph() | |
76 # assert_equal(3, approx.node_connectivity(G)) | |
77 | |
78 | |
79 def test_dodecahedral(): | |
80 G = nx.dodecahedral_graph() | |
81 assert 3 == approx.node_connectivity(G) | |
82 assert 3 == approx.node_connectivity(G, 0, 5) | |
83 | |
84 | |
85 def test_octahedral(): | |
86 G = nx.octahedral_graph() | |
87 assert 4 == approx.node_connectivity(G) | |
88 assert 4 == approx.node_connectivity(G, 0, 5) | |
89 | |
90 | |
91 # Approximation can fail with icosahedral graph depending | |
92 # on iteration order. | |
93 # def test_icosahedral(): | |
94 # G=nx.icosahedral_graph() | |
95 # assert_equal(5, approx.node_connectivity(G)) | |
96 # assert_equal(5, approx.node_connectivity(G, 0, 5)) | |
97 | |
98 | |
99 def test_only_source(): | |
100 G = nx.complete_graph(5) | |
101 pytest.raises(nx.NetworkXError, approx.node_connectivity, G, s=0) | |
102 | |
103 | |
104 def test_only_target(): | |
105 G = nx.complete_graph(5) | |
106 pytest.raises(nx.NetworkXError, approx.node_connectivity, G, t=0) | |
107 | |
108 | |
109 def test_missing_source(): | |
110 G = nx.path_graph(4) | |
111 pytest.raises(nx.NetworkXError, approx.node_connectivity, G, 10, 1) | |
112 | |
113 | |
114 def test_missing_target(): | |
115 G = nx.path_graph(4) | |
116 pytest.raises(nx.NetworkXError, approx.node_connectivity, G, 1, 10) | |
117 | |
118 | |
119 def test_source_equals_target(): | |
120 G = nx.complete_graph(5) | |
121 pytest.raises(nx.NetworkXError, approx.local_node_connectivity, G, 0, 0) | |
122 | |
123 | |
124 def test_directed_node_connectivity(): | |
125 G = nx.cycle_graph(10, create_using=nx.DiGraph()) # only one direction | |
126 D = nx.cycle_graph(10).to_directed() # 2 reciprocal edges | |
127 assert 1 == approx.node_connectivity(G) | |
128 assert 1 == approx.node_connectivity(G, 1, 4) | |
129 assert 2 == approx.node_connectivity(D) | |
130 assert 2 == approx.node_connectivity(D, 1, 4) | |
131 | |
132 | |
133 class TestAllPairsNodeConnectivityApprox: | |
134 @classmethod | |
135 def setup_class(cls): | |
136 cls.path = nx.path_graph(7) | |
137 cls.directed_path = nx.path_graph(7, create_using=nx.DiGraph()) | |
138 cls.cycle = nx.cycle_graph(7) | |
139 cls.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph()) | |
140 cls.gnp = nx.gnp_random_graph(30, 0.1) | |
141 cls.directed_gnp = nx.gnp_random_graph(30, 0.1, directed=True) | |
142 cls.K20 = nx.complete_graph(20) | |
143 cls.K10 = nx.complete_graph(10) | |
144 cls.K5 = nx.complete_graph(5) | |
145 cls.G_list = [ | |
146 cls.path, | |
147 cls.directed_path, | |
148 cls.cycle, | |
149 cls.directed_cycle, | |
150 cls.gnp, | |
151 cls.directed_gnp, | |
152 cls.K10, | |
153 cls.K5, | |
154 cls.K20, | |
155 ] | |
156 | |
157 def test_cycles(self): | |
158 K_undir = approx.all_pairs_node_connectivity(self.cycle) | |
159 for source in K_undir: | |
160 for target, k in K_undir[source].items(): | |
161 assert k == 2 | |
162 K_dir = approx.all_pairs_node_connectivity(self.directed_cycle) | |
163 for source in K_dir: | |
164 for target, k in K_dir[source].items(): | |
165 assert k == 1 | |
166 | |
167 def test_complete(self): | |
168 for G in [self.K10, self.K5, self.K20]: | |
169 K = approx.all_pairs_node_connectivity(G) | |
170 for source in K: | |
171 for target, k in K[source].items(): | |
172 assert k == len(G) - 1 | |
173 | |
174 def test_paths(self): | |
175 K_undir = approx.all_pairs_node_connectivity(self.path) | |
176 for source in K_undir: | |
177 for target, k in K_undir[source].items(): | |
178 assert k == 1 | |
179 K_dir = approx.all_pairs_node_connectivity(self.directed_path) | |
180 for source in K_dir: | |
181 for target, k in K_dir[source].items(): | |
182 if source < target: | |
183 assert k == 1 | |
184 else: | |
185 assert k == 0 | |
186 | |
187 def test_cutoff(self): | |
188 for G in [self.K10, self.K5, self.K20]: | |
189 for mp in [2, 3, 4]: | |
190 paths = approx.all_pairs_node_connectivity(G, cutoff=mp) | |
191 for source in paths: | |
192 for target, K in paths[source].items(): | |
193 assert K == mp | |
194 | |
195 def test_all_pairs_connectivity_nbunch(self): | |
196 G = nx.complete_graph(5) | |
197 nbunch = [0, 2, 3] | |
198 C = approx.all_pairs_node_connectivity(G, nbunch=nbunch) | |
199 assert len(C) == len(nbunch) |