### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/tests/test_connectivity.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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()
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):
46 G = nx.disjoint_union(G, nx.complete_graph(4))
47 G.remove_node(G.order() - 1)
48 for i in range(7, 10):
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)