Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/cuts.py: 40%
47 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Functions for finding and evaluating cuts in a graph.
3"""
5from itertools import chain
7import networkx as nx
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]
21# TODO STILL NEED TO UPDATE ALL THE DOCUMENTATION!
24@nx._dispatch(edge_attrs="weight")
25def cut_size(G, S, T=None, weight=None):
26 """Returns the size of the cut between two sets of nodes.
28 A *cut* is a partition of the nodes of a graph into two sets. The
29 *cut size* is the sum of the weights of the edges "between" the two
30 sets of nodes.
32 Parameters
33 ----------
34 G : NetworkX graph
36 S : collection
37 A collection of nodes in `G`.
39 T : collection
40 A collection of nodes in `G`. If not specified, this is taken to
41 be the set complement of `S`.
43 weight : object
44 Edge attribute key to use as weight. If not specified, edges
45 have weight one.
47 Returns
48 -------
49 number
50 Total weight of all edges from nodes in set `S` to nodes in
51 set `T` (and, in the case of directed graphs, all edges from
52 nodes in `T` to nodes in `S`).
54 Examples
55 --------
56 In the graph with two cliques joined by a single edges, the natural
57 bipartition of the graph into two blocks, one for each clique,
58 yields a cut of weight one::
60 >>> G = nx.barbell_graph(3, 0)
61 >>> S = {0, 1, 2}
62 >>> T = {3, 4, 5}
63 >>> nx.cut_size(G, S, T)
64 1
66 Each parallel edge in a multigraph is counted when determining the
67 cut size::
69 >>> G = nx.MultiGraph(["ab", "ab"])
70 >>> S = {"a"}
71 >>> T = {"b"}
72 >>> nx.cut_size(G, S, T)
73 2
75 Notes
76 -----
77 In a multigraph, the cut size is the total weight of edges including
78 multiplicity.
80 """
81 edges = nx.edge_boundary(G, S, T, data=weight, default=1)
82 if G.is_directed():
83 edges = chain(edges, nx.edge_boundary(G, T, S, data=weight, default=1))
84 return sum(weight for u, v, weight in edges)
87@nx._dispatch(edge_attrs="weight")
88def volume(G, S, weight=None):
89 """Returns the volume of a set of nodes.
91 The *volume* of a set *S* is the sum of the (out-)degrees of nodes
92 in *S* (taking into account parallel edges in multigraphs). [1]
94 Parameters
95 ----------
96 G : NetworkX graph
98 S : collection
99 A collection of nodes in `G`.
101 weight : object
102 Edge attribute key to use as weight. If not specified, edges
103 have weight one.
105 Returns
106 -------
107 number
108 The volume of the set of nodes represented by `S` in the graph
109 `G`.
111 See also
112 --------
113 conductance
114 cut_size
115 edge_expansion
116 edge_boundary
117 normalized_cut_size
119 References
120 ----------
121 .. [1] David Gleich.
122 *Hierarchical Directed Spectral Graph Partitioning*.
123 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
125 """
126 degree = G.out_degree if G.is_directed() else G.degree
127 return sum(d for v, d in degree(S, weight=weight))
130@nx._dispatch(edge_attrs="weight")
131def normalized_cut_size(G, S, T=None, weight=None):
132 """Returns the normalized size of the cut between two sets of nodes.
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]
137 Parameters
138 ----------
139 G : NetworkX graph
141 S : collection
142 A collection of nodes in `G`.
144 T : collection
145 A collection of nodes in `G`.
147 weight : object
148 Edge attribute key to use as weight. If not specified, edges
149 have weight one.
151 Returns
152 -------
153 number
154 The normalized cut size between the two sets `S` and `T`.
156 Notes
157 -----
158 In a multigraph, the cut size is the total weight of edges including
159 multiplicity.
161 See also
162 --------
163 conductance
164 cut_size
165 edge_expansion
166 volume
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>
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))
183@nx._dispatch(edge_attrs="weight")
184def conductance(G, S, T=None, weight=None):
185 """Returns the conductance of two sets of nodes.
187 The *conductance* is the quotient of the cut size and the smaller of
188 the volumes of the two sets. [1]
190 Parameters
191 ----------
192 G : NetworkX graph
194 S : collection
195 A collection of nodes in `G`.
197 T : collection
198 A collection of nodes in `G`.
200 weight : object
201 Edge attribute key to use as weight. If not specified, edges
202 have weight one.
204 Returns
205 -------
206 number
207 The conductance between the two sets `S` and `T`.
209 See also
210 --------
211 cut_size
212 edge_expansion
213 normalized_cut_size
214 volume
216 References
217 ----------
218 .. [1] David Gleich.
219 *Hierarchical Directed Spectral Graph Partitioning*.
220 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
222 """
223 if T is None:
224 T = set(G) - set(S)
225 num_cut_edges = cut_size(G, S, T, weight=weight)
226 volume_S = volume(G, S, weight=weight)
227 volume_T = volume(G, T, weight=weight)
228 return num_cut_edges / min(volume_S, volume_T)
231@nx._dispatch(edge_attrs="weight")
232def edge_expansion(G, S, T=None, weight=None):
233 """Returns the edge expansion between two node sets.
235 The *edge expansion* is the quotient of the cut size and the smaller
236 of the cardinalities of the two sets. [1]
238 Parameters
239 ----------
240 G : NetworkX graph
242 S : collection
243 A collection of nodes in `G`.
245 T : collection
246 A collection of nodes in `G`.
248 weight : object
249 Edge attribute key to use as weight. If not specified, edges
250 have weight one.
252 Returns
253 -------
254 number
255 The edge expansion between the two sets `S` and `T`.
257 See also
258 --------
259 boundary_expansion
260 mixing_expansion
261 node_expansion
263 References
264 ----------
265 .. [1] Fan Chung.
266 *Spectral Graph Theory*.
267 (CBMS Regional Conference Series in Mathematics, No. 92),
268 American Mathematical Society, 1997, ISBN 0-8218-0315-8
269 <http://www.math.ucsd.edu/~fan/research/revised.html>
271 """
272 if T is None:
273 T = set(G) - set(S)
274 num_cut_edges = cut_size(G, S, T=T, weight=weight)
275 return num_cut_edges / min(len(S), len(T))
278@nx._dispatch(edge_attrs="weight")
279def mixing_expansion(G, S, T=None, weight=None):
280 """Returns the mixing expansion between two node sets.
282 The *mixing expansion* is the quotient of the cut size and twice the
283 number of edges in the graph. [1]
285 Parameters
286 ----------
287 G : NetworkX graph
289 S : collection
290 A collection of nodes in `G`.
292 T : collection
293 A collection of nodes in `G`.
295 weight : object
296 Edge attribute key to use as weight. If not specified, edges
297 have weight one.
299 Returns
300 -------
301 number
302 The mixing expansion between the two sets `S` and `T`.
304 See also
305 --------
306 boundary_expansion
307 edge_expansion
308 node_expansion
310 References
311 ----------
312 .. [1] Vadhan, Salil P.
313 "Pseudorandomness."
314 *Foundations and Trends
315 in Theoretical Computer Science* 7.1–3 (2011): 1–336.
316 <https://doi.org/10.1561/0400000010>
318 """
319 num_cut_edges = cut_size(G, S, T=T, weight=weight)
320 num_total_edges = G.number_of_edges()
321 return num_cut_edges / (2 * num_total_edges)
324# TODO What is the generalization to two arguments, S and T? Does the
325# denominator become `min(len(S), len(T))`?
326@nx._dispatch
327def node_expansion(G, S):
328 """Returns the node expansion of the set `S`.
330 The *node expansion* is the quotient of the size of the node
331 boundary of *S* and the cardinality of *S*. [1]
333 Parameters
334 ----------
335 G : NetworkX graph
337 S : collection
338 A collection of nodes in `G`.
340 Returns
341 -------
342 number
343 The node expansion of the set `S`.
345 See also
346 --------
347 boundary_expansion
348 edge_expansion
349 mixing_expansion
351 References
352 ----------
353 .. [1] Vadhan, Salil P.
354 "Pseudorandomness."
355 *Foundations and Trends
356 in Theoretical Computer Science* 7.1–3 (2011): 1–336.
357 <https://doi.org/10.1561/0400000010>
359 """
360 neighborhood = set(chain.from_iterable(G.neighbors(v) for v in S))
361 return len(neighborhood) / len(S)
364# TODO What is the generalization to two arguments, S and T? Does the
365# denominator become `min(len(S), len(T))`?
366@nx._dispatch
367def boundary_expansion(G, S):
368 """Returns the boundary expansion of the set `S`.
370 The *boundary expansion* is the quotient of the size
371 of the node boundary and the cardinality of *S*. [1]
373 Parameters
374 ----------
375 G : NetworkX graph
377 S : collection
378 A collection of nodes in `G`.
380 Returns
381 -------
382 number
383 The boundary expansion of the set `S`.
385 See also
386 --------
387 edge_expansion
388 mixing_expansion
389 node_expansion
391 References
392 ----------
393 .. [1] Vadhan, Salil P.
394 "Pseudorandomness."
395 *Foundations and Trends in Theoretical Computer Science*
396 7.1–3 (2011): 1–336.
397 <https://doi.org/10.1561/0400000010>
399 """
400 return len(nx.node_boundary(G, S)) / len(S)