Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/components/tests/test_biconnected.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 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 | |
25 answer = [ | |
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 ] | |
38 assert_components_equal(list(nx.biconnected_components(G)), answer) | |
39 | |
40 G.add_edge(2, 17) | |
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) | |
53 nx.add_cycle(G, [1, 3, 4]) | |
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) | |
61 nx.add_cycle(G, [1, 3, 4]) | |
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) | |
68 G.add_edge(0, 1) | |
69 assert not nx.is_biconnected(G) | |
70 | |
71 | |
72 def test_biconnected_components_cycle(): | |
73 G = nx.cycle_graph(3) | |
74 nx.add_cycle(G, [1, 3, 4]) | |
75 answer = [{0, 1, 2}, {1, 3, 4}] | |
76 assert_components_equal(list(nx.biconnected_components(G)), answer) | |
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)) | |
112 answer = [ | |
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 ] | |
121 assert_components_edges_equal(comps, answer) | |
122 | |
123 | |
124 def test_biconnected_components2(): | |
125 G = nx.Graph() | |
126 nx.add_cycle(G, "ABC") | |
127 nx.add_cycle(G, "CDE") | |
128 nx.add_cycle(G, "FIJHG") | |
129 nx.add_cycle(G, "GIJ") | |
130 G.add_edge("E", "G") | |
131 comps = list(nx.biconnected_component_edges(G)) | |
132 answer = [ | |
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 ] | |
146 assert_components_edges_equal(comps, answer) | |
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() | |
159 answer = [ | |
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)) | |
194 assert_components_equal(bcc, answer) | |
195 assert set(nx.articulation_points(K)) == {0} | |
196 | |
197 | |
198 def test_biconnected_eppstein(): | |
199 # tests from http://www.ics.uci.edu/~eppstein/PADS/Biconnectivity.py | |
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)) | |
228 assert_components_equal(bcc, answer_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) |