Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/cuts.py @ 1:56ad4e20f292 draft

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