Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/components/tests/test_strongly_connected.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 class TestStronglyConnected: | |
7 @classmethod | |
8 def setup_class(cls): | |
9 cls.gc = [] | |
10 G = nx.DiGraph() | |
11 G.add_edges_from( | |
12 [ | |
13 (1, 2), | |
14 (2, 3), | |
15 (2, 8), | |
16 (3, 4), | |
17 (3, 7), | |
18 (4, 5), | |
19 (5, 3), | |
20 (5, 6), | |
21 (7, 4), | |
22 (7, 6), | |
23 (8, 1), | |
24 (8, 7), | |
25 ] | |
26 ) | |
27 C = {frozenset([3, 4, 5, 7]), frozenset([1, 2, 8]), frozenset([6])} | |
28 cls.gc.append((G, C)) | |
29 | |
30 G = nx.DiGraph() | |
31 G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)]) | |
32 C = {frozenset([2, 3, 4]), frozenset([1])} | |
33 cls.gc.append((G, C)) | |
34 | |
35 G = nx.DiGraph() | |
36 G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)]) | |
37 C = {frozenset([1, 2, 3])} | |
38 cls.gc.append((G, C)) | |
39 | |
40 # Eppstein's tests | |
41 G = nx.DiGraph({0: [1], 1: [2, 3], 2: [4, 5], 3: [4, 5], 4: [6], 5: [], 6: []}) | |
42 C = { | |
43 frozenset([0]), | |
44 frozenset([1]), | |
45 frozenset([2]), | |
46 frozenset([3]), | |
47 frozenset([4]), | |
48 frozenset([5]), | |
49 frozenset([6]), | |
50 } | |
51 cls.gc.append((G, C)) | |
52 | |
53 G = nx.DiGraph({0: [1], 1: [2, 3, 4], 2: [0, 3], 3: [4], 4: [3]}) | |
54 C = {frozenset([0, 1, 2]), frozenset([3, 4])} | |
55 cls.gc.append((G, C)) | |
56 | |
57 def test_tarjan(self): | |
58 scc = nx.strongly_connected_components | |
59 for G, C in self.gc: | |
60 assert {frozenset(g) for g in scc(G)} == C | |
61 | |
62 def test_tarjan_recursive(self): | |
63 scc = nx.strongly_connected_components_recursive | |
64 for G, C in self.gc: | |
65 assert {frozenset(g) for g in scc(G)} == C | |
66 | |
67 def test_kosaraju(self): | |
68 scc = nx.kosaraju_strongly_connected_components | |
69 for G, C in self.gc: | |
70 assert {frozenset(g) for g in scc(G)} == C | |
71 | |
72 def test_number_strongly_connected_components(self): | |
73 ncc = nx.number_strongly_connected_components | |
74 for G, C in self.gc: | |
75 assert ncc(G) == len(C) | |
76 | |
77 def test_is_strongly_connected(self): | |
78 for G, C in self.gc: | |
79 if len(C) == 1: | |
80 assert nx.is_strongly_connected(G) | |
81 else: | |
82 assert not nx.is_strongly_connected(G) | |
83 | |
84 def test_contract_scc1(self): | |
85 G = nx.DiGraph() | |
86 G.add_edges_from( | |
87 [ | |
88 (1, 2), | |
89 (2, 3), | |
90 (2, 11), | |
91 (2, 12), | |
92 (3, 4), | |
93 (4, 3), | |
94 (4, 5), | |
95 (5, 6), | |
96 (6, 5), | |
97 (6, 7), | |
98 (7, 8), | |
99 (7, 9), | |
100 (7, 10), | |
101 (8, 9), | |
102 (9, 7), | |
103 (10, 6), | |
104 (11, 2), | |
105 (11, 4), | |
106 (11, 6), | |
107 (12, 6), | |
108 (12, 11), | |
109 ] | |
110 ) | |
111 scc = list(nx.strongly_connected_components(G)) | |
112 cG = nx.condensation(G, scc) | |
113 # DAG | |
114 assert nx.is_directed_acyclic_graph(cG) | |
115 # nodes | |
116 assert sorted(cG.nodes()) == [0, 1, 2, 3] | |
117 # edges | |
118 mapping = {} | |
119 for i, component in enumerate(scc): | |
120 for n in component: | |
121 mapping[n] = i | |
122 edge = (mapping[2], mapping[3]) | |
123 assert cG.has_edge(*edge) | |
124 edge = (mapping[2], mapping[5]) | |
125 assert cG.has_edge(*edge) | |
126 edge = (mapping[3], mapping[5]) | |
127 assert cG.has_edge(*edge) | |
128 | |
129 def test_contract_scc_isolate(self): | |
130 # Bug found and fixed in [1687]. | |
131 G = nx.DiGraph() | |
132 G.add_edge(1, 2) | |
133 G.add_edge(2, 1) | |
134 scc = list(nx.strongly_connected_components(G)) | |
135 cG = nx.condensation(G, scc) | |
136 assert list(cG.nodes()) == [0] | |
137 assert list(cG.edges()) == [] | |
138 | |
139 def test_contract_scc_edge(self): | |
140 G = nx.DiGraph() | |
141 G.add_edge(1, 2) | |
142 G.add_edge(2, 1) | |
143 G.add_edge(2, 3) | |
144 G.add_edge(3, 4) | |
145 G.add_edge(4, 3) | |
146 scc = list(nx.strongly_connected_components(G)) | |
147 cG = nx.condensation(G, scc) | |
148 assert sorted(cG.nodes()) == [0, 1] | |
149 if 1 in scc[0]: | |
150 edge = (0, 1) | |
151 else: | |
152 edge = (1, 0) | |
153 assert list(cG.edges()) == [edge] | |
154 | |
155 def test_condensation_mapping_and_members(self): | |
156 G, C = self.gc[1] | |
157 C = sorted(C, key=len, reverse=True) | |
158 cG = nx.condensation(G) | |
159 mapping = cG.graph["mapping"] | |
160 assert all(n in G for n in mapping) | |
161 assert all(0 == cN for n, cN in mapping.items() if n in C[0]) | |
162 assert all(1 == cN for n, cN in mapping.items() if n in C[1]) | |
163 for n, d in cG.nodes(data=True): | |
164 assert set(C[n]) == cG.nodes[n]["members"] | |
165 | |
166 def test_null_graph(self): | |
167 G = nx.DiGraph() | |
168 assert list(nx.strongly_connected_components(G)) == [] | |
169 assert list(nx.kosaraju_strongly_connected_components(G)) == [] | |
170 assert list(nx.strongly_connected_components_recursive(G)) == [] | |
171 assert len(nx.condensation(G)) == 0 | |
172 pytest.raises( | |
173 nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph() | |
174 ) | |
175 | |
176 def test_connected_raise(self): | |
177 G = nx.Graph() | |
178 pytest.raises(NetworkXNotImplemented, nx.strongly_connected_components, G) | |
179 pytest.raises( | |
180 NetworkXNotImplemented, nx.kosaraju_strongly_connected_components, G | |
181 ) | |
182 pytest.raises( | |
183 NetworkXNotImplemented, nx.strongly_connected_components_recursive, G | |
184 ) | |
185 pytest.raises(NetworkXNotImplemented, nx.is_strongly_connected, G) | |
186 pytest.raises( | |
187 nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph() | |
188 ) | |
189 pytest.raises(NetworkXNotImplemented, nx.condensation, G) | |
190 | |
191 | |
192 # Commented out due to variability on Travis-CI hardware/operating systems | |
193 # def test_linear_time(self): | |
194 # # See Issue #2831 | |
195 # count = 100 # base case | |
196 # dg = nx.DiGraph() | |
197 # dg.add_nodes_from([0, 1]) | |
198 # for i in range(2, count): | |
199 # dg.add_node(i) | |
200 # dg.add_edge(i, 1) | |
201 # dg.add_edge(0, i) | |
202 # t = time.time() | |
203 # ret = tuple(nx.strongly_connected_components(dg)) | |
204 # dt = time.time() - t | |
205 # | |
206 # count = 200 | |
207 # dg = nx.DiGraph() | |
208 # dg.add_nodes_from([0, 1]) | |
209 # for i in range(2, count): | |
210 # dg.add_node(i) | |
211 # dg.add_edge(i, 1) | |
212 # dg.add_edge(0, i) | |
213 # t = time.time() | |
214 # ret = tuple(nx.strongly_connected_components(dg)) | |
215 # dt2 = time.time() - t | |
216 # assert_less(dt2, dt * 2.3) # should be 2 times longer for this graph |