### comparison env/lib/python3.9/site-packages/networkx/algorithms/components/tests/test_biconnected.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 import networkx as nx
3 from networkx import NetworkXNotImplemented
4
5
6 def assert_components_edges_equal(x, y):
7 sx = {frozenset([frozenset(e) for e in c]) for c in x}
8 sy = {frozenset([frozenset(e) for e in c]) for c in y}
9 assert sx == sy
10
11
12 def assert_components_equal(x, y):
13 sx = {frozenset(c) for c in x}
14 sy = {frozenset(c) for c in y}
15 assert sx == sy
16
17
18 def test_barbell():
19 G = nx.barbell_graph(8, 4)
20 nx.add_path(G, [7, 20, 21, 22])
21 nx.add_cycle(G, [22, 23, 24, 25])
22 pts = set(nx.articulation_points(G))
23 assert pts == {7, 8, 9, 10, 11, 12, 20, 21, 22}
24
26 {12, 13, 14, 15, 16, 17, 18, 19},
27 {0, 1, 2, 3, 4, 5, 6, 7},
28 {22, 23, 24, 25},
29 {11, 12},
30 {10, 11},
31 {9, 10},
32 {8, 9},
33 {7, 8},
34 {21, 22},
35 {20, 21},
36 {7, 20},
37 ]
39
41 pts = set(nx.articulation_points(G))
42 assert pts == {7, 20, 21, 22}
43
44
45 def test_articulation_points_repetitions():
46 G = nx.Graph()
47 G.add_edges_from([(0, 1), (1, 2), (1, 3)])
48 assert list(nx.articulation_points(G)) == [1]
49
50
51 def test_articulation_points_cycle():
52 G = nx.cycle_graph(3)
54 pts = set(nx.articulation_points(G))
55 assert pts == {1}
56
57
58 def test_is_biconnected():
59 G = nx.cycle_graph(3)
60 assert nx.is_biconnected(G)
62 assert not nx.is_biconnected(G)
63
64
65 def test_empty_is_biconnected():
66 G = nx.empty_graph(5)
67 assert not nx.is_biconnected(G)
69 assert not nx.is_biconnected(G)
70
71
72 def test_biconnected_components_cycle():
73 G = nx.cycle_graph(3)
75 answer = [{0, 1, 2}, {1, 3, 4}]
77
78
79 def test_biconnected_components1():
80 # graph example from
81 # http://www.ibluemojo.com/school/articul_algorithm.html
82 edges = [
83 (0, 1),
84 (0, 5),
85 (0, 6),
86 (0, 14),
87 (1, 5),
88 (1, 6),
89 (1, 14),
90 (2, 4),
91 (2, 10),
92 (3, 4),
93 (3, 15),
94 (4, 6),
95 (4, 7),
96 (4, 10),
97 (5, 14),
98 (6, 14),
99 (7, 9),
100 (8, 9),
101 (8, 12),
102 (8, 13),
103 (10, 15),
104 (11, 12),
105 (11, 13),
106 (12, 13),
107 ]
108 G = nx.Graph(edges)
109 pts = set(nx.articulation_points(G))
110 assert pts == {4, 6, 7, 8, 9}
111 comps = list(nx.biconnected_component_edges(G))
113 [(3, 4), (15, 3), (10, 15), (10, 4), (2, 10), (4, 2)],
114 [(13, 12), (13, 8), (11, 13), (12, 11), (8, 12)],
115 [(9, 8)],
116 [(7, 9)],
117 [(4, 7)],
118 [(6, 4)],
119 [(14, 0), (5, 1), (5, 0), (14, 5), (14, 1), (6, 14), (6, 0), (1, 6), (0, 1)],
120 ]
122
123
124 def test_biconnected_components2():
125 G = nx.Graph()
131 comps = list(nx.biconnected_component_edges(G))
133 [
134 tuple("GF"),
135 tuple("FI"),
136 tuple("IG"),
137 tuple("IJ"),
138 tuple("JG"),
139 tuple("JH"),
140 tuple("HG"),
141 ],
142 [tuple("EG")],
143 [tuple("CD"), tuple("DE"), tuple("CE")],
144 [tuple("AB"), tuple("BC"), tuple("AC")],
145 ]
147
148
149 def test_biconnected_davis():
150 D = nx.davis_southern_women_graph()
151 bcc = list(nx.biconnected_components(D))[0]
152 assert set(D) == bcc # All nodes in a giant bicomponent
153 # So no articulation points
154 assert len(list(nx.articulation_points(D))) == 0
155
156
157 def test_biconnected_karate():
158 K = nx.karate_club_graph()
160 {
161 0,
162 1,
163 2,
164 3,
165 7,
166 8,
167 9,
168 12,
169 13,
170 14,
171 15,
172 17,
173 18,
174 19,
175 20,
176 21,
177 22,
178 23,
179 24,
180 25,
181 26,
182 27,
183 28,
184 29,
185 30,
186 31,
187 32,
188 33,
189 },
190 {0, 4, 5, 6, 10, 16},
191 {0, 11},
192 ]
193 bcc = list(nx.biconnected_components(K))
195 assert set(nx.articulation_points(K)) == {0}
196
197
198 def test_biconnected_eppstein():
200 G1 = nx.Graph(
201 {
202 0: [1, 2, 5],
203 1: [0, 5],
204 2: [0, 3, 4],
205 3: [2, 4, 5, 6],
206 4: [2, 3, 5, 6],
207 5: [0, 1, 3, 4],
208 6: [3, 4],
209 }
210 )
211 G2 = nx.Graph(
212 {
213 0: [2, 5],
214 1: [3, 8],
215 2: [0, 3, 5],
216 3: [1, 2, 6, 8],
217 4: [7],
218 5: [0, 2],
219 6: [3, 8],
220 7: [4],
221 8: [1, 3, 6],
222 }
223 )
224 assert nx.is_biconnected(G1)
225 assert not nx.is_biconnected(G2)
226 answer_G2 = [{1, 3, 6, 8}, {0, 2, 5}, {2, 3}, {4, 7}]
227 bcc = list(nx.biconnected_components(G2))
229
230
231 def test_null_graph():
232 G = nx.Graph()
233 assert not nx.is_biconnected(G)
234 assert list(nx.biconnected_components(G)) == []
235 assert list(nx.biconnected_component_edges(G)) == []
236 assert list(nx.articulation_points(G)) == []
237
238
239 def test_connected_raise():
240 DG = nx.DiGraph()
241 pytest.raises(NetworkXNotImplemented, nx.biconnected_components, DG)
242 pytest.raises(NetworkXNotImplemented, nx.biconnected_component_edges, DG)
243 pytest.raises(NetworkXNotImplemented, nx.articulation_points, DG)
244 pytest.raises(NetworkXNotImplemented, nx.is_biconnected, DG)