Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/cuts.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 """Functions for finding and evaluating cuts in a graph. | |
2 | |
3 """ | |
4 | |
5 from itertools import chain | |
6 | |
7 import networkx as nx | |
8 | |
9 __all__ = [ | |
10 "boundary_expansion", | |
11 "conductance", | |
12 "cut_size", | |
13 "edge_expansion", | |
14 "mixing_expansion", | |
15 "node_expansion", | |
16 "normalized_cut_size", | |
17 "volume", | |
18 ] | |
19 | |
20 | |
21 # TODO STILL NEED TO UPDATE ALL THE DOCUMENTATION! | |
22 | |
23 | |
24 def cut_size(G, S, T=None, weight=None): | |
25 """Returns the size of the cut between two sets of nodes. | |
26 | |
27 A *cut* is a partition of the nodes of a graph into two sets. The | |
28 *cut size* is the sum of the weights of the edges "between" the two | |
29 sets of nodes. | |
30 | |
31 Parameters | |
32 ---------- | |
33 G : NetworkX graph | |
34 | |
35 S : sequence | |
36 A sequence of nodes in `G`. | |
37 | |
38 T : sequence | |
39 A sequence of nodes in `G`. If not specified, this is taken to | |
40 be the set complement of `S`. | |
41 | |
42 weight : object | |
43 Edge attribute key to use as weight. If not specified, edges | |
44 have weight one. | |
45 | |
46 Returns | |
47 ------- | |
48 number | |
49 Total weight of all edges from nodes in set `S` to nodes in | |
50 set `T` (and, in the case of directed graphs, all edges from | |
51 nodes in `T` to nodes in `S`). | |
52 | |
53 Examples | |
54 -------- | |
55 In the graph with two cliques joined by a single edges, the natural | |
56 bipartition of the graph into two blocks, one for each clique, | |
57 yields a cut of weight one:: | |
58 | |
59 >>> G = nx.barbell_graph(3, 0) | |
60 >>> S = {0, 1, 2} | |
61 >>> T = {3, 4, 5} | |
62 >>> nx.cut_size(G, S, T) | |
63 1 | |
64 | |
65 Each parallel edge in a multigraph is counted when determining the | |
66 cut size:: | |
67 | |
68 >>> G = nx.MultiGraph(["ab", "ab"]) | |
69 >>> S = {"a"} | |
70 >>> T = {"b"} | |
71 >>> nx.cut_size(G, S, T) | |
72 2 | |
73 | |
74 Notes | |
75 ----- | |
76 In a multigraph, the cut size is the total weight of edges including | |
77 multiplicity. | |
78 | |
79 """ | |
80 edges = nx.edge_boundary(G, S, T, data=weight, default=1) | |
81 if G.is_directed(): | |
82 edges = chain(edges, nx.edge_boundary(G, T, S, data=weight, default=1)) | |
83 return sum(weight for u, v, weight in edges) | |
84 | |
85 | |
86 def volume(G, S, weight=None): | |
87 """Returns the volume of a set of nodes. | |
88 | |
89 The *volume* of a set *S* is the sum of the (out-)degrees of nodes | |
90 in *S* (taking into account parallel edges in multigraphs). [1] | |
91 | |
92 Parameters | |
93 ---------- | |
94 G : NetworkX graph | |
95 | |
96 S : sequence | |
97 A sequence of nodes in `G`. | |
98 | |
99 weight : object | |
100 Edge attribute key to use as weight. If not specified, edges | |
101 have weight one. | |
102 | |
103 Returns | |
104 ------- | |
105 number | |
106 The volume of the set of nodes represented by `S` in the graph | |
107 `G`. | |
108 | |
109 See also | |
110 -------- | |
111 conductance | |
112 cut_size | |
113 edge_expansion | |
114 edge_boundary | |
115 normalized_cut_size | |
116 | |
117 References | |
118 ---------- | |
119 .. [1] David Gleich. | |
120 *Hierarchical Directed Spectral Graph Partitioning*. | |
121 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf> | |
122 | |
123 """ | |
124 degree = G.out_degree if G.is_directed() else G.degree | |
125 return sum(d for v, d in degree(S, weight=weight)) | |
126 | |
127 | |
128 def normalized_cut_size(G, S, T=None, weight=None): | |
129 """Returns the normalized size of the cut between two sets of nodes. | |
130 | |
131 The *normalized cut size* is the cut size times the sum of the | |
132 reciprocal sizes of the volumes of the two sets. [1] | |
133 | |
134 Parameters | |
135 ---------- | |
136 G : NetworkX graph | |
137 | |
138 S : sequence | |
139 A sequence of nodes in `G`. | |
140 | |
141 T : sequence | |
142 A sequence of nodes in `G`. | |
143 | |
144 weight : object | |
145 Edge attribute key to use as weight. If not specified, edges | |
146 have weight one. | |
147 | |
148 Returns | |
149 ------- | |
150 number | |
151 The normalized cut size between the two sets `S` and `T`. | |
152 | |
153 Notes | |
154 ----- | |
155 In a multigraph, the cut size is the total weight of edges including | |
156 multiplicity. | |
157 | |
158 See also | |
159 -------- | |
160 conductance | |
161 cut_size | |
162 edge_expansion | |
163 volume | |
164 | |
165 References | |
166 ---------- | |
167 .. [1] David Gleich. | |
168 *Hierarchical Directed Spectral Graph Partitioning*. | |
169 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf> | |
170 | |
171 """ | |
172 if T is None: | |
173 T = set(G) - set(S) | |
174 num_cut_edges = cut_size(G, S, T=T, weight=weight) | |
175 volume_S = volume(G, S, weight=weight) | |
176 volume_T = volume(G, T, weight=weight) | |
177 return num_cut_edges * ((1 / volume_S) + (1 / volume_T)) | |
178 | |
179 | |
180 def conductance(G, S, T=None, weight=None): | |
181 """Returns the conductance of two sets of nodes. | |
182 | |
183 The *conductance* is the quotient of the cut size and the smaller of | |
184 the volumes of the two sets. [1] | |
185 | |
186 Parameters | |
187 ---------- | |
188 G : NetworkX graph | |
189 | |
190 S : sequence | |
191 A sequence of nodes in `G`. | |
192 | |
193 T : sequence | |
194 A sequence of nodes in `G`. | |
195 | |
196 weight : object | |
197 Edge attribute key to use as weight. If not specified, edges | |
198 have weight one. | |
199 | |
200 Returns | |
201 ------- | |
202 number | |
203 The conductance between the two sets `S` and `T`. | |
204 | |
205 See also | |
206 -------- | |
207 cut_size | |
208 edge_expansion | |
209 normalized_cut_size | |
210 volume | |
211 | |
212 References | |
213 ---------- | |
214 .. [1] David Gleich. | |
215 *Hierarchical Directed Spectral Graph Partitioning*. | |
216 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf> | |
217 | |
218 """ | |
219 if T is None: | |
220 T = set(G) - set(S) | |
221 num_cut_edges = cut_size(G, S, T, weight=weight) | |
222 volume_S = volume(G, S, weight=weight) | |
223 volume_T = volume(G, T, weight=weight) | |
224 return num_cut_edges / min(volume_S, volume_T) | |
225 | |
226 | |
227 def edge_expansion(G, S, T=None, weight=None): | |
228 """Returns the edge expansion between two node sets. | |
229 | |
230 The *edge expansion* is the quotient of the cut size and the smaller | |
231 of the cardinalities of the two sets. [1] | |
232 | |
233 Parameters | |
234 ---------- | |
235 G : NetworkX graph | |
236 | |
237 S : sequence | |
238 A sequence of nodes in `G`. | |
239 | |
240 T : sequence | |
241 A sequence of nodes in `G`. | |
242 | |
243 weight : object | |
244 Edge attribute key to use as weight. If not specified, edges | |
245 have weight one. | |
246 | |
247 Returns | |
248 ------- | |
249 number | |
250 The edge expansion between the two sets `S` and `T`. | |
251 | |
252 See also | |
253 -------- | |
254 boundary_expansion | |
255 mixing_expansion | |
256 node_expansion | |
257 | |
258 References | |
259 ---------- | |
260 .. [1] Fan Chung. | |
261 *Spectral Graph Theory*. | |
262 (CBMS Regional Conference Series in Mathematics, No. 92), | |
263 American Mathematical Society, 1997, ISBN 0-8218-0315-8 | |
264 <http://www.math.ucsd.edu/~fan/research/revised.html> | |
265 | |
266 """ | |
267 if T is None: | |
268 T = set(G) - set(S) | |
269 num_cut_edges = cut_size(G, S, T=T, weight=weight) | |
270 return num_cut_edges / min(len(S), len(T)) | |
271 | |
272 | |
273 def mixing_expansion(G, S, T=None, weight=None): | |
274 """Returns the mixing expansion between two node sets. | |
275 | |
276 The *mixing expansion* is the quotient of the cut size and twice the | |
277 number of edges in the graph. [1] | |
278 | |
279 Parameters | |
280 ---------- | |
281 G : NetworkX graph | |
282 | |
283 S : sequence | |
284 A sequence of nodes in `G`. | |
285 | |
286 T : sequence | |
287 A sequence of nodes in `G`. | |
288 | |
289 weight : object | |
290 Edge attribute key to use as weight. If not specified, edges | |
291 have weight one. | |
292 | |
293 Returns | |
294 ------- | |
295 number | |
296 The mixing expansion between the two sets `S` and `T`. | |
297 | |
298 See also | |
299 -------- | |
300 boundary_expansion | |
301 edge_expansion | |
302 node_expansion | |
303 | |
304 References | |
305 ---------- | |
306 .. [1] Vadhan, Salil P. | |
307 "Pseudorandomness." | |
308 *Foundations and Trends | |
309 in Theoretical Computer Science* 7.1–3 (2011): 1–336. | |
310 <https://doi.org/10.1561/0400000010> | |
311 | |
312 """ | |
313 num_cut_edges = cut_size(G, S, T=T, weight=weight) | |
314 num_total_edges = G.number_of_edges() | |
315 return num_cut_edges / (2 * num_total_edges) | |
316 | |
317 | |
318 # TODO What is the generalization to two arguments, S and T? Does the | |
319 # denominator become `min(len(S), len(T))`? | |
320 def node_expansion(G, S): | |
321 """Returns the node expansion of the set `S`. | |
322 | |
323 The *node expansion* is the quotient of the size of the node | |
324 boundary of *S* and the cardinality of *S*. [1] | |
325 | |
326 Parameters | |
327 ---------- | |
328 G : NetworkX graph | |
329 | |
330 S : sequence | |
331 A sequence of nodes in `G`. | |
332 | |
333 Returns | |
334 ------- | |
335 number | |
336 The node expansion of the set `S`. | |
337 | |
338 See also | |
339 -------- | |
340 boundary_expansion | |
341 edge_expansion | |
342 mixing_expansion | |
343 | |
344 References | |
345 ---------- | |
346 .. [1] Vadhan, Salil P. | |
347 "Pseudorandomness." | |
348 *Foundations and Trends | |
349 in Theoretical Computer Science* 7.1–3 (2011): 1–336. | |
350 <https://doi.org/10.1561/0400000010> | |
351 | |
352 """ | |
353 neighborhood = set(chain.from_iterable(G.neighbors(v) for v in S)) | |
354 return len(neighborhood) / len(S) | |
355 | |
356 | |
357 # TODO What is the generalization to two arguments, S and T? Does the | |
358 # denominator become `min(len(S), len(T))`? | |
359 def boundary_expansion(G, S): | |
360 """Returns the boundary expansion of the set `S`. | |
361 | |
362 The *boundary expansion* is the quotient of the size | |
363 of the node boundary and the cardinality of *S*. [1] | |
364 | |
365 Parameters | |
366 ---------- | |
367 G : NetworkX graph | |
368 | |
369 S : sequence | |
370 A sequence of nodes in `G`. | |
371 | |
372 Returns | |
373 ------- | |
374 number | |
375 The boundary expansion of the set `S`. | |
376 | |
377 See also | |
378 -------- | |
379 edge_expansion | |
380 mixing_expansion | |
381 node_expansion | |
382 | |
383 References | |
384 ---------- | |
385 .. [1] Vadhan, Salil P. | |
386 "Pseudorandomness." | |
387 *Foundations and Trends in Theoretical Computer Science* | |
388 7.1–3 (2011): 1–336. | |
389 <https://doi.org/10.1561/0400000010> | |
390 | |
391 """ | |
392 return len(nx.node_boundary(G, S)) / len(S) |