Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_clique.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 convert_node_labels_to_integers as cnlti | |
4 | |
5 | |
6 class TestCliques: | |
7 def setup_method(self): | |
8 z = [3, 4, 3, 4, 2, 4, 2, 1, 1, 1, 1] | |
9 self.G = cnlti(nx.generators.havel_hakimi_graph(z), first_label=1) | |
10 self.cl = list(nx.find_cliques(self.G)) | |
11 H = nx.complete_graph(6) | |
12 H = nx.relabel_nodes(H, {i: i + 1 for i in range(6)}) | |
13 H.remove_edges_from([(2, 6), (2, 5), (2, 4), (1, 3), (5, 3)]) | |
14 self.H = H | |
15 | |
16 def test_find_cliques1(self): | |
17 cl = list(nx.find_cliques(self.G)) | |
18 rcl = nx.find_cliques_recursive(self.G) | |
19 expected = [[2, 6, 1, 3], [2, 6, 4], [5, 4, 7], [8, 9], [10, 11]] | |
20 assert sorted(map(sorted, cl)) == sorted(map(sorted, rcl)) | |
21 assert sorted(map(sorted, cl)) == sorted(map(sorted, expected)) | |
22 | |
23 def test_selfloops(self): | |
24 self.G.add_edge(1, 1) | |
25 cl = list(nx.find_cliques(self.G)) | |
26 rcl = list(nx.find_cliques_recursive(self.G)) | |
27 assert set(map(frozenset, cl)) == set(map(frozenset, rcl)) | |
28 answer = [{2, 6, 1, 3}, {2, 6, 4}, {5, 4, 7}, {8, 9}, {10, 11}] | |
29 assert len(answer) == len(cl) | |
30 assert all(set(c) in answer for c in cl) | |
31 | |
32 def test_find_cliques2(self): | |
33 hcl = list(nx.find_cliques(self.H)) | |
34 assert sorted(map(sorted, hcl)) == [[1, 2], [1, 4, 5, 6], [2, 3], [3, 4, 6]] | |
35 | |
36 def test_clique_number(self): | |
37 G = self.G | |
38 assert nx.graph_clique_number(G) == 4 | |
39 assert nx.graph_clique_number(G, cliques=self.cl) == 4 | |
40 | |
41 def test_clique_number2(self): | |
42 G = nx.Graph() | |
43 G.add_nodes_from([1, 2, 3]) | |
44 assert nx.graph_clique_number(G) == 1 | |
45 | |
46 def test_clique_number3(self): | |
47 G = nx.Graph() | |
48 assert nx.graph_clique_number(G) == 0 | |
49 | |
50 def test_number_of_cliques(self): | |
51 G = self.G | |
52 assert nx.graph_number_of_cliques(G) == 5 | |
53 assert nx.graph_number_of_cliques(G, cliques=self.cl) == 5 | |
54 assert nx.number_of_cliques(G, 1) == 1 | |
55 assert list(nx.number_of_cliques(G, [1]).values()) == [1] | |
56 assert list(nx.number_of_cliques(G, [1, 2]).values()) == [1, 2] | |
57 assert nx.number_of_cliques(G, [1, 2]) == {1: 1, 2: 2} | |
58 assert nx.number_of_cliques(G, 2) == 2 | |
59 assert nx.number_of_cliques(G) == { | |
60 1: 1, | |
61 2: 2, | |
62 3: 1, | |
63 4: 2, | |
64 5: 1, | |
65 6: 2, | |
66 7: 1, | |
67 8: 1, | |
68 9: 1, | |
69 10: 1, | |
70 11: 1, | |
71 } | |
72 assert nx.number_of_cliques(G, nodes=list(G)) == { | |
73 1: 1, | |
74 2: 2, | |
75 3: 1, | |
76 4: 2, | |
77 5: 1, | |
78 6: 2, | |
79 7: 1, | |
80 8: 1, | |
81 9: 1, | |
82 10: 1, | |
83 11: 1, | |
84 } | |
85 assert nx.number_of_cliques(G, nodes=[2, 3, 4]) == {2: 2, 3: 1, 4: 2} | |
86 assert nx.number_of_cliques(G, cliques=self.cl) == { | |
87 1: 1, | |
88 2: 2, | |
89 3: 1, | |
90 4: 2, | |
91 5: 1, | |
92 6: 2, | |
93 7: 1, | |
94 8: 1, | |
95 9: 1, | |
96 10: 1, | |
97 11: 1, | |
98 } | |
99 assert nx.number_of_cliques(G, list(G), cliques=self.cl) == { | |
100 1: 1, | |
101 2: 2, | |
102 3: 1, | |
103 4: 2, | |
104 5: 1, | |
105 6: 2, | |
106 7: 1, | |
107 8: 1, | |
108 9: 1, | |
109 10: 1, | |
110 11: 1, | |
111 } | |
112 | |
113 def test_node_clique_number(self): | |
114 G = self.G | |
115 assert nx.node_clique_number(G, 1) == 4 | |
116 assert list(nx.node_clique_number(G, [1]).values()) == [4] | |
117 assert list(nx.node_clique_number(G, [1, 2]).values()) == [4, 4] | |
118 assert nx.node_clique_number(G, [1, 2]) == {1: 4, 2: 4} | |
119 assert nx.node_clique_number(G, 1) == 4 | |
120 assert nx.node_clique_number(G) == { | |
121 1: 4, | |
122 2: 4, | |
123 3: 4, | |
124 4: 3, | |
125 5: 3, | |
126 6: 4, | |
127 7: 3, | |
128 8: 2, | |
129 9: 2, | |
130 10: 2, | |
131 11: 2, | |
132 } | |
133 assert nx.node_clique_number(G, cliques=self.cl) == { | |
134 1: 4, | |
135 2: 4, | |
136 3: 4, | |
137 4: 3, | |
138 5: 3, | |
139 6: 4, | |
140 7: 3, | |
141 8: 2, | |
142 9: 2, | |
143 10: 2, | |
144 11: 2, | |
145 } | |
146 | |
147 def test_cliques_containing_node(self): | |
148 G = self.G | |
149 assert nx.cliques_containing_node(G, 1) == [[2, 6, 1, 3]] | |
150 assert list(nx.cliques_containing_node(G, [1]).values()) == [[[2, 6, 1, 3]]] | |
151 assert [ | |
152 sorted(c) for c in list(nx.cliques_containing_node(G, [1, 2]).values()) | |
153 ] == [[[2, 6, 1, 3]], [[2, 6, 1, 3], [2, 6, 4]]] | |
154 result = nx.cliques_containing_node(G, [1, 2]) | |
155 for k, v in result.items(): | |
156 result[k] = sorted(v) | |
157 assert result == {1: [[2, 6, 1, 3]], 2: [[2, 6, 1, 3], [2, 6, 4]]} | |
158 assert nx.cliques_containing_node(G, 1) == [[2, 6, 1, 3]] | |
159 expected = [{2, 6, 1, 3}, {2, 6, 4}] | |
160 answer = [set(c) for c in nx.cliques_containing_node(G, 2)] | |
161 assert answer in (expected, list(reversed(expected))) | |
162 | |
163 answer = [set(c) for c in nx.cliques_containing_node(G, 2, cliques=self.cl)] | |
164 assert answer in (expected, list(reversed(expected))) | |
165 assert len(nx.cliques_containing_node(G)) == 11 | |
166 | |
167 def test_make_clique_bipartite(self): | |
168 G = self.G | |
169 B = nx.make_clique_bipartite(G) | |
170 assert sorted(B) == [-5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] | |
171 # Project onto the nodes of the original graph. | |
172 H = nx.project(B, range(1, 12)) | |
173 assert H.adj == G.adj | |
174 # Project onto the nodes representing the cliques. | |
175 H1 = nx.project(B, range(-5, 0)) | |
176 # Relabel the negative numbers as positive ones. | |
177 H1 = nx.relabel_nodes(H1, {-v: v for v in range(1, 6)}) | |
178 assert sorted(H1) == [1, 2, 3, 4, 5] | |
179 | |
180 def test_make_max_clique_graph(self): | |
181 """Tests that the maximal clique graph is the same as the bipartite | |
182 clique graph after being projected onto the nodes representing the | |
183 cliques. | |
184 | |
185 """ | |
186 G = self.G | |
187 B = nx.make_clique_bipartite(G) | |
188 # Project onto the nodes representing the cliques. | |
189 H1 = nx.project(B, range(-5, 0)) | |
190 # Relabel the negative numbers as nonnegative ones, starting at | |
191 # 0. | |
192 H1 = nx.relabel_nodes(H1, {-v: v - 1 for v in range(1, 6)}) | |
193 H2 = nx.make_max_clique_graph(G) | |
194 assert H1.adj == H2.adj | |
195 | |
196 def test_directed(self): | |
197 with pytest.raises(nx.NetworkXNotImplemented): | |
198 cliques = nx.find_cliques(nx.DiGraph()) | |
199 | |
200 | |
201 class TestEnumerateAllCliques: | |
202 def test_paper_figure_4(self): | |
203 # Same graph as given in Fig. 4 of paper enumerate_all_cliques is | |
204 # based on. | |
205 # http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1559964&isnumber=33129 | |
206 G = nx.Graph() | |
207 edges_fig_4 = [ | |
208 ("a", "b"), | |
209 ("a", "c"), | |
210 ("a", "d"), | |
211 ("a", "e"), | |
212 ("b", "c"), | |
213 ("b", "d"), | |
214 ("b", "e"), | |
215 ("c", "d"), | |
216 ("c", "e"), | |
217 ("d", "e"), | |
218 ("f", "b"), | |
219 ("f", "c"), | |
220 ("f", "g"), | |
221 ("g", "f"), | |
222 ("g", "c"), | |
223 ("g", "d"), | |
224 ("g", "e"), | |
225 ] | |
226 G.add_edges_from(edges_fig_4) | |
227 | |
228 cliques = list(nx.enumerate_all_cliques(G)) | |
229 clique_sizes = list(map(len, cliques)) | |
230 assert sorted(clique_sizes) == clique_sizes | |
231 | |
232 expected_cliques = [ | |
233 ["a"], | |
234 ["b"], | |
235 ["c"], | |
236 ["d"], | |
237 ["e"], | |
238 ["f"], | |
239 ["g"], | |
240 ["a", "b"], | |
241 ["a", "b", "d"], | |
242 ["a", "b", "d", "e"], | |
243 ["a", "b", "e"], | |
244 ["a", "c"], | |
245 ["a", "c", "d"], | |
246 ["a", "c", "d", "e"], | |
247 ["a", "c", "e"], | |
248 ["a", "d"], | |
249 ["a", "d", "e"], | |
250 ["a", "e"], | |
251 ["b", "c"], | |
252 ["b", "c", "d"], | |
253 ["b", "c", "d", "e"], | |
254 ["b", "c", "e"], | |
255 ["b", "c", "f"], | |
256 ["b", "d"], | |
257 ["b", "d", "e"], | |
258 ["b", "e"], | |
259 ["b", "f"], | |
260 ["c", "d"], | |
261 ["c", "d", "e"], | |
262 ["c", "d", "e", "g"], | |
263 ["c", "d", "g"], | |
264 ["c", "e"], | |
265 ["c", "e", "g"], | |
266 ["c", "f"], | |
267 ["c", "f", "g"], | |
268 ["c", "g"], | |
269 ["d", "e"], | |
270 ["d", "e", "g"], | |
271 ["d", "g"], | |
272 ["e", "g"], | |
273 ["f", "g"], | |
274 ["a", "b", "c"], | |
275 ["a", "b", "c", "d"], | |
276 ["a", "b", "c", "d", "e"], | |
277 ["a", "b", "c", "e"], | |
278 ] | |
279 | |
280 assert sorted(map(sorted, cliques)) == sorted(map(sorted, expected_cliques)) |