Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/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 """ | |
2 Flow based cut algorithms | |
3 """ | |
4 import itertools | |
5 import networkx as nx | |
6 | |
7 # Define the default maximum flow function to use in all flow based | |
8 # cut algorithms. | |
9 from networkx.algorithms.flow import edmonds_karp | |
10 from networkx.algorithms.flow import build_residual_network | |
11 | |
12 default_flow_func = edmonds_karp | |
13 | |
14 from .utils import build_auxiliary_node_connectivity, build_auxiliary_edge_connectivity | |
15 | |
16 __all__ = [ | |
17 "minimum_st_node_cut", | |
18 "minimum_node_cut", | |
19 "minimum_st_edge_cut", | |
20 "minimum_edge_cut", | |
21 ] | |
22 | |
23 | |
24 def minimum_st_edge_cut(G, s, t, flow_func=None, auxiliary=None, residual=None): | |
25 """Returns the edges of the cut-set of a minimum (s, t)-cut. | |
26 | |
27 This function returns the set of edges of minimum cardinality that, | |
28 if removed, would destroy all paths among source and target in G. | |
29 Edge weights are not considered. See :meth:`minimum_cut` for | |
30 computing minimum cuts considering edge weights. | |
31 | |
32 Parameters | |
33 ---------- | |
34 G : NetworkX graph | |
35 | |
36 s : node | |
37 Source node for the flow. | |
38 | |
39 t : node | |
40 Sink node for the flow. | |
41 | |
42 auxiliary : NetworkX DiGraph | |
43 Auxiliary digraph to compute flow based node connectivity. It has | |
44 to have a graph attribute called mapping with a dictionary mapping | |
45 node names in G and in the auxiliary digraph. If provided | |
46 it will be reused instead of recreated. Default value: None. | |
47 | |
48 flow_func : function | |
49 A function for computing the maximum flow among a pair of nodes. | |
50 The function has to accept at least three parameters: a Digraph, | |
51 a source node, and a target node. And return a residual network | |
52 that follows NetworkX conventions (see :meth:`maximum_flow` for | |
53 details). If flow_func is None, the default maximum flow function | |
54 (:meth:`edmonds_karp`) is used. See :meth:`node_connectivity` for | |
55 details. The choice of the default function may change from version | |
56 to version and should not be relied on. Default value: None. | |
57 | |
58 residual : NetworkX DiGraph | |
59 Residual network to compute maximum flow. If provided it will be | |
60 reused instead of recreated. Default value: None. | |
61 | |
62 Returns | |
63 ------- | |
64 cutset : set | |
65 Set of edges that, if removed from the graph, will disconnect it. | |
66 | |
67 See also | |
68 -------- | |
69 :meth:`minimum_cut` | |
70 :meth:`minimum_node_cut` | |
71 :meth:`minimum_edge_cut` | |
72 :meth:`stoer_wagner` | |
73 :meth:`node_connectivity` | |
74 :meth:`edge_connectivity` | |
75 :meth:`maximum_flow` | |
76 :meth:`edmonds_karp` | |
77 :meth:`preflow_push` | |
78 :meth:`shortest_augmenting_path` | |
79 | |
80 Examples | |
81 -------- | |
82 This function is not imported in the base NetworkX namespace, so you | |
83 have to explicitly import it from the connectivity package: | |
84 | |
85 >>> from networkx.algorithms.connectivity import minimum_st_edge_cut | |
86 | |
87 We use in this example the platonic icosahedral graph, which has edge | |
88 connectivity 5. | |
89 | |
90 >>> G = nx.icosahedral_graph() | |
91 >>> len(minimum_st_edge_cut(G, 0, 6)) | |
92 5 | |
93 | |
94 If you need to compute local edge cuts on several pairs of | |
95 nodes in the same graph, it is recommended that you reuse the | |
96 data structures that NetworkX uses in the computation: the | |
97 auxiliary digraph for edge connectivity, and the residual | |
98 network for the underlying maximum flow computation. | |
99 | |
100 Example of how to compute local edge cuts among all pairs of | |
101 nodes of the platonic icosahedral graph reusing the data | |
102 structures. | |
103 | |
104 >>> import itertools | |
105 >>> # You also have to explicitly import the function for | |
106 >>> # building the auxiliary digraph from the connectivity package | |
107 >>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity | |
108 >>> H = build_auxiliary_edge_connectivity(G) | |
109 >>> # And the function for building the residual network from the | |
110 >>> # flow package | |
111 >>> from networkx.algorithms.flow import build_residual_network | |
112 >>> # Note that the auxiliary digraph has an edge attribute named capacity | |
113 >>> R = build_residual_network(H, "capacity") | |
114 >>> result = dict.fromkeys(G, dict()) | |
115 >>> # Reuse the auxiliary digraph and the residual network by passing them | |
116 >>> # as parameters | |
117 >>> for u, v in itertools.combinations(G, 2): | |
118 ... k = len(minimum_st_edge_cut(G, u, v, auxiliary=H, residual=R)) | |
119 ... result[u][v] = k | |
120 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2)) | |
121 True | |
122 | |
123 You can also use alternative flow algorithms for computing edge | |
124 cuts. For instance, in dense networks the algorithm | |
125 :meth:`shortest_augmenting_path` will usually perform better than | |
126 the default :meth:`edmonds_karp` which is faster for sparse | |
127 networks with highly skewed degree distributions. Alternative flow | |
128 functions have to be explicitly imported from the flow package. | |
129 | |
130 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
131 >>> len(minimum_st_edge_cut(G, 0, 6, flow_func=shortest_augmenting_path)) | |
132 5 | |
133 | |
134 """ | |
135 if flow_func is None: | |
136 flow_func = default_flow_func | |
137 | |
138 if auxiliary is None: | |
139 H = build_auxiliary_edge_connectivity(G) | |
140 else: | |
141 H = auxiliary | |
142 | |
143 kwargs = dict(capacity="capacity", flow_func=flow_func, residual=residual) | |
144 | |
145 cut_value, partition = nx.minimum_cut(H, s, t, **kwargs) | |
146 reachable, non_reachable = partition | |
147 # Any edge in the original graph linking the two sets in the | |
148 # partition is part of the edge cutset | |
149 cutset = set() | |
150 for u, nbrs in ((n, G[n]) for n in reachable): | |
151 cutset.update((u, v) for v in nbrs if v in non_reachable) | |
152 | |
153 return cutset | |
154 | |
155 | |
156 def minimum_st_node_cut(G, s, t, flow_func=None, auxiliary=None, residual=None): | |
157 r"""Returns a set of nodes of minimum cardinality that disconnect source | |
158 from target in G. | |
159 | |
160 This function returns the set of nodes of minimum cardinality that, | |
161 if removed, would destroy all paths among source and target in G. | |
162 | |
163 Parameters | |
164 ---------- | |
165 G : NetworkX graph | |
166 | |
167 s : node | |
168 Source node. | |
169 | |
170 t : node | |
171 Target node. | |
172 | |
173 flow_func : function | |
174 A function for computing the maximum flow among a pair of nodes. | |
175 The function has to accept at least three parameters: a Digraph, | |
176 a source node, and a target node. And return a residual network | |
177 that follows NetworkX conventions (see :meth:`maximum_flow` for | |
178 details). If flow_func is None, the default maximum flow function | |
179 (:meth:`edmonds_karp`) is used. See below for details. The choice | |
180 of the default function may change from version to version and | |
181 should not be relied on. Default value: None. | |
182 | |
183 auxiliary : NetworkX DiGraph | |
184 Auxiliary digraph to compute flow based node connectivity. It has | |
185 to have a graph attribute called mapping with a dictionary mapping | |
186 node names in G and in the auxiliary digraph. If provided | |
187 it will be reused instead of recreated. Default value: None. | |
188 | |
189 residual : NetworkX DiGraph | |
190 Residual network to compute maximum flow. If provided it will be | |
191 reused instead of recreated. Default value: None. | |
192 | |
193 Returns | |
194 ------- | |
195 cutset : set | |
196 Set of nodes that, if removed, would destroy all paths between | |
197 source and target in G. | |
198 | |
199 Examples | |
200 -------- | |
201 This function is not imported in the base NetworkX namespace, so you | |
202 have to explicitly import it from the connectivity package: | |
203 | |
204 >>> from networkx.algorithms.connectivity import minimum_st_node_cut | |
205 | |
206 We use in this example the platonic icosahedral graph, which has node | |
207 connectivity 5. | |
208 | |
209 >>> G = nx.icosahedral_graph() | |
210 >>> len(minimum_st_node_cut(G, 0, 6)) | |
211 5 | |
212 | |
213 If you need to compute local st cuts between several pairs of | |
214 nodes in the same graph, it is recommended that you reuse the | |
215 data structures that NetworkX uses in the computation: the | |
216 auxiliary digraph for node connectivity and node cuts, and the | |
217 residual network for the underlying maximum flow computation. | |
218 | |
219 Example of how to compute local st node cuts reusing the data | |
220 structures: | |
221 | |
222 >>> # You also have to explicitly import the function for | |
223 >>> # building the auxiliary digraph from the connectivity package | |
224 >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity | |
225 >>> H = build_auxiliary_node_connectivity(G) | |
226 >>> # And the function for building the residual network from the | |
227 >>> # flow package | |
228 >>> from networkx.algorithms.flow import build_residual_network | |
229 >>> # Note that the auxiliary digraph has an edge attribute named capacity | |
230 >>> R = build_residual_network(H, "capacity") | |
231 >>> # Reuse the auxiliary digraph and the residual network by passing them | |
232 >>> # as parameters | |
233 >>> len(minimum_st_node_cut(G, 0, 6, auxiliary=H, residual=R)) | |
234 5 | |
235 | |
236 You can also use alternative flow algorithms for computing minimum st | |
237 node cuts. For instance, in dense networks the algorithm | |
238 :meth:`shortest_augmenting_path` will usually perform better than | |
239 the default :meth:`edmonds_karp` which is faster for sparse | |
240 networks with highly skewed degree distributions. Alternative flow | |
241 functions have to be explicitly imported from the flow package. | |
242 | |
243 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
244 >>> len(minimum_st_node_cut(G, 0, 6, flow_func=shortest_augmenting_path)) | |
245 5 | |
246 | |
247 Notes | |
248 ----- | |
249 This is a flow based implementation of minimum node cut. The algorithm | |
250 is based in solving a number of maximum flow computations to determine | |
251 the capacity of the minimum cut on an auxiliary directed network that | |
252 corresponds to the minimum node cut of G. It handles both directed | |
253 and undirected graphs. This implementation is based on algorithm 11 | |
254 in [1]_. | |
255 | |
256 See also | |
257 -------- | |
258 :meth:`minimum_node_cut` | |
259 :meth:`minimum_edge_cut` | |
260 :meth:`stoer_wagner` | |
261 :meth:`node_connectivity` | |
262 :meth:`edge_connectivity` | |
263 :meth:`maximum_flow` | |
264 :meth:`edmonds_karp` | |
265 :meth:`preflow_push` | |
266 :meth:`shortest_augmenting_path` | |
267 | |
268 References | |
269 ---------- | |
270 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. | |
271 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf | |
272 | |
273 """ | |
274 if auxiliary is None: | |
275 H = build_auxiliary_node_connectivity(G) | |
276 else: | |
277 H = auxiliary | |
278 | |
279 mapping = H.graph.get("mapping", None) | |
280 if mapping is None: | |
281 raise nx.NetworkXError("Invalid auxiliary digraph.") | |
282 if G.has_edge(s, t) or G.has_edge(t, s): | |
283 return {} | |
284 kwargs = dict(flow_func=flow_func, residual=residual, auxiliary=H) | |
285 | |
286 # The edge cut in the auxiliary digraph corresponds to the node cut in the | |
287 # original graph. | |
288 edge_cut = minimum_st_edge_cut(H, f"{mapping[s]}B", f"{mapping[t]}A", **kwargs) | |
289 # Each node in the original graph maps to two nodes of the auxiliary graph | |
290 node_cut = {H.nodes[node]["id"] for edge in edge_cut for node in edge} | |
291 return node_cut - {s, t} | |
292 | |
293 | |
294 def minimum_node_cut(G, s=None, t=None, flow_func=None): | |
295 r"""Returns a set of nodes of minimum cardinality that disconnects G. | |
296 | |
297 If source and target nodes are provided, this function returns the | |
298 set of nodes of minimum cardinality that, if removed, would destroy | |
299 all paths among source and target in G. If not, it returns a set | |
300 of nodes of minimum cardinality that disconnects G. | |
301 | |
302 Parameters | |
303 ---------- | |
304 G : NetworkX graph | |
305 | |
306 s : node | |
307 Source node. Optional. Default value: None. | |
308 | |
309 t : node | |
310 Target node. Optional. Default value: None. | |
311 | |
312 flow_func : function | |
313 A function for computing the maximum flow among a pair of nodes. | |
314 The function has to accept at least three parameters: a Digraph, | |
315 a source node, and a target node. And return a residual network | |
316 that follows NetworkX conventions (see :meth:`maximum_flow` for | |
317 details). If flow_func is None, the default maximum flow function | |
318 (:meth:`edmonds_karp`) is used. See below for details. The | |
319 choice of the default function may change from version | |
320 to version and should not be relied on. Default value: None. | |
321 | |
322 Returns | |
323 ------- | |
324 cutset : set | |
325 Set of nodes that, if removed, would disconnect G. If source | |
326 and target nodes are provided, the set contains the nodes that | |
327 if removed, would destroy all paths between source and target. | |
328 | |
329 Examples | |
330 -------- | |
331 >>> # Platonic icosahedral graph has node connectivity 5 | |
332 >>> G = nx.icosahedral_graph() | |
333 >>> node_cut = nx.minimum_node_cut(G) | |
334 >>> len(node_cut) | |
335 5 | |
336 | |
337 You can use alternative flow algorithms for the underlying maximum | |
338 flow computation. In dense networks the algorithm | |
339 :meth:`shortest_augmenting_path` will usually perform better | |
340 than the default :meth:`edmonds_karp`, which is faster for | |
341 sparse networks with highly skewed degree distributions. Alternative | |
342 flow functions have to be explicitly imported from the flow package. | |
343 | |
344 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
345 >>> node_cut == nx.minimum_node_cut(G, flow_func=shortest_augmenting_path) | |
346 True | |
347 | |
348 If you specify a pair of nodes (source and target) as parameters, | |
349 this function returns a local st node cut. | |
350 | |
351 >>> len(nx.minimum_node_cut(G, 3, 7)) | |
352 5 | |
353 | |
354 If you need to perform several local st cuts among different | |
355 pairs of nodes on the same graph, it is recommended that you reuse | |
356 the data structures used in the maximum flow computations. See | |
357 :meth:`minimum_st_node_cut` for details. | |
358 | |
359 Notes | |
360 ----- | |
361 This is a flow based implementation of minimum node cut. The algorithm | |
362 is based in solving a number of maximum flow computations to determine | |
363 the capacity of the minimum cut on an auxiliary directed network that | |
364 corresponds to the minimum node cut of G. It handles both directed | |
365 and undirected graphs. This implementation is based on algorithm 11 | |
366 in [1]_. | |
367 | |
368 See also | |
369 -------- | |
370 :meth:`minimum_st_node_cut` | |
371 :meth:`minimum_cut` | |
372 :meth:`minimum_edge_cut` | |
373 :meth:`stoer_wagner` | |
374 :meth:`node_connectivity` | |
375 :meth:`edge_connectivity` | |
376 :meth:`maximum_flow` | |
377 :meth:`edmonds_karp` | |
378 :meth:`preflow_push` | |
379 :meth:`shortest_augmenting_path` | |
380 | |
381 References | |
382 ---------- | |
383 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. | |
384 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf | |
385 | |
386 """ | |
387 if (s is not None and t is None) or (s is None and t is not None): | |
388 raise nx.NetworkXError("Both source and target must be specified.") | |
389 | |
390 # Local minimum node cut. | |
391 if s is not None and t is not None: | |
392 if s not in G: | |
393 raise nx.NetworkXError(f"node {s} not in graph") | |
394 if t not in G: | |
395 raise nx.NetworkXError(f"node {t} not in graph") | |
396 return minimum_st_node_cut(G, s, t, flow_func=flow_func) | |
397 | |
398 # Global minimum node cut. | |
399 # Analog to the algorithm 11 for global node connectivity in [1]. | |
400 if G.is_directed(): | |
401 if not nx.is_weakly_connected(G): | |
402 raise nx.NetworkXError("Input graph is not connected") | |
403 iter_func = itertools.permutations | |
404 | |
405 def neighbors(v): | |
406 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)]) | |
407 | |
408 else: | |
409 if not nx.is_connected(G): | |
410 raise nx.NetworkXError("Input graph is not connected") | |
411 iter_func = itertools.combinations | |
412 neighbors = G.neighbors | |
413 | |
414 # Reuse the auxiliary digraph and the residual network. | |
415 H = build_auxiliary_node_connectivity(G) | |
416 R = build_residual_network(H, "capacity") | |
417 kwargs = dict(flow_func=flow_func, auxiliary=H, residual=R) | |
418 | |
419 # Choose a node with minimum degree. | |
420 v = min(G, key=G.degree) | |
421 # Initial node cutset is all neighbors of the node with minimum degree. | |
422 min_cut = set(G[v]) | |
423 # Compute st node cuts between v and all its non-neighbors nodes in G. | |
424 for w in set(G) - set(neighbors(v)) - {v}: | |
425 this_cut = minimum_st_node_cut(G, v, w, **kwargs) | |
426 if len(min_cut) >= len(this_cut): | |
427 min_cut = this_cut | |
428 # Also for non adjacent pairs of neighbors of v. | |
429 for x, y in iter_func(neighbors(v), 2): | |
430 if y in G[x]: | |
431 continue | |
432 this_cut = minimum_st_node_cut(G, x, y, **kwargs) | |
433 if len(min_cut) >= len(this_cut): | |
434 min_cut = this_cut | |
435 | |
436 return min_cut | |
437 | |
438 | |
439 def minimum_edge_cut(G, s=None, t=None, flow_func=None): | |
440 r"""Returns a set of edges of minimum cardinality that disconnects G. | |
441 | |
442 If source and target nodes are provided, this function returns the | |
443 set of edges of minimum cardinality that, if removed, would break | |
444 all paths among source and target in G. If not, it returns a set of | |
445 edges of minimum cardinality that disconnects G. | |
446 | |
447 Parameters | |
448 ---------- | |
449 G : NetworkX graph | |
450 | |
451 s : node | |
452 Source node. Optional. Default value: None. | |
453 | |
454 t : node | |
455 Target node. Optional. Default value: None. | |
456 | |
457 flow_func : function | |
458 A function for computing the maximum flow among a pair of nodes. | |
459 The function has to accept at least three parameters: a Digraph, | |
460 a source node, and a target node. And return a residual network | |
461 that follows NetworkX conventions (see :meth:`maximum_flow` for | |
462 details). If flow_func is None, the default maximum flow function | |
463 (:meth:`edmonds_karp`) is used. See below for details. The | |
464 choice of the default function may change from version | |
465 to version and should not be relied on. Default value: None. | |
466 | |
467 Returns | |
468 ------- | |
469 cutset : set | |
470 Set of edges that, if removed, would disconnect G. If source | |
471 and target nodes are provided, the set contains the edges that | |
472 if removed, would destroy all paths between source and target. | |
473 | |
474 Examples | |
475 -------- | |
476 >>> # Platonic icosahedral graph has edge connectivity 5 | |
477 >>> G = nx.icosahedral_graph() | |
478 >>> len(nx.minimum_edge_cut(G)) | |
479 5 | |
480 | |
481 You can use alternative flow algorithms for the underlying | |
482 maximum flow computation. In dense networks the algorithm | |
483 :meth:`shortest_augmenting_path` will usually perform better | |
484 than the default :meth:`edmonds_karp`, which is faster for | |
485 sparse networks with highly skewed degree distributions. | |
486 Alternative flow functions have to be explicitly imported | |
487 from the flow package. | |
488 | |
489 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
490 >>> len(nx.minimum_edge_cut(G, flow_func=shortest_augmenting_path)) | |
491 5 | |
492 | |
493 If you specify a pair of nodes (source and target) as parameters, | |
494 this function returns the value of local edge connectivity. | |
495 | |
496 >>> nx.edge_connectivity(G, 3, 7) | |
497 5 | |
498 | |
499 If you need to perform several local computations among different | |
500 pairs of nodes on the same graph, it is recommended that you reuse | |
501 the data structures used in the maximum flow computations. See | |
502 :meth:`local_edge_connectivity` for details. | |
503 | |
504 Notes | |
505 ----- | |
506 This is a flow based implementation of minimum edge cut. For | |
507 undirected graphs the algorithm works by finding a 'small' dominating | |
508 set of nodes of G (see algorithm 7 in [1]_) and computing the maximum | |
509 flow between an arbitrary node in the dominating set and the rest of | |
510 nodes in it. This is an implementation of algorithm 6 in [1]_. For | |
511 directed graphs, the algorithm does n calls to the max flow function. | |
512 The function raises an error if the directed graph is not weakly | |
513 connected and returns an empty set if it is weakly connected. | |
514 It is an implementation of algorithm 8 in [1]_. | |
515 | |
516 See also | |
517 -------- | |
518 :meth:`minimum_st_edge_cut` | |
519 :meth:`minimum_node_cut` | |
520 :meth:`stoer_wagner` | |
521 :meth:`node_connectivity` | |
522 :meth:`edge_connectivity` | |
523 :meth:`maximum_flow` | |
524 :meth:`edmonds_karp` | |
525 :meth:`preflow_push` | |
526 :meth:`shortest_augmenting_path` | |
527 | |
528 References | |
529 ---------- | |
530 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. | |
531 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf | |
532 | |
533 """ | |
534 if (s is not None and t is None) or (s is None and t is not None): | |
535 raise nx.NetworkXError("Both source and target must be specified.") | |
536 | |
537 # reuse auxiliary digraph and residual network | |
538 H = build_auxiliary_edge_connectivity(G) | |
539 R = build_residual_network(H, "capacity") | |
540 kwargs = dict(flow_func=flow_func, residual=R, auxiliary=H) | |
541 | |
542 # Local minimum edge cut if s and t are not None | |
543 if s is not None and t is not None: | |
544 if s not in G: | |
545 raise nx.NetworkXError(f"node {s} not in graph") | |
546 if t not in G: | |
547 raise nx.NetworkXError(f"node {t} not in graph") | |
548 return minimum_st_edge_cut(H, s, t, **kwargs) | |
549 | |
550 # Global minimum edge cut | |
551 # Analog to the algorithm for global edge connectivity | |
552 if G.is_directed(): | |
553 # Based on algorithm 8 in [1] | |
554 if not nx.is_weakly_connected(G): | |
555 raise nx.NetworkXError("Input graph is not connected") | |
556 | |
557 # Initial cutset is all edges of a node with minimum degree | |
558 node = min(G, key=G.degree) | |
559 min_cut = set(G.edges(node)) | |
560 nodes = list(G) | |
561 n = len(nodes) | |
562 for i in range(n): | |
563 try: | |
564 this_cut = minimum_st_edge_cut(H, nodes[i], nodes[i + 1], **kwargs) | |
565 if len(this_cut) <= len(min_cut): | |
566 min_cut = this_cut | |
567 except IndexError: # Last node! | |
568 this_cut = minimum_st_edge_cut(H, nodes[i], nodes[0], **kwargs) | |
569 if len(this_cut) <= len(min_cut): | |
570 min_cut = this_cut | |
571 | |
572 return min_cut | |
573 | |
574 else: # undirected | |
575 # Based on algorithm 6 in [1] | |
576 if not nx.is_connected(G): | |
577 raise nx.NetworkXError("Input graph is not connected") | |
578 | |
579 # Initial cutset is all edges of a node with minimum degree | |
580 node = min(G, key=G.degree) | |
581 min_cut = set(G.edges(node)) | |
582 # A dominating set is \lambda-covering | |
583 # We need a dominating set with at least two nodes | |
584 for node in G: | |
585 D = nx.dominating_set(G, start_with=node) | |
586 v = D.pop() | |
587 if D: | |
588 break | |
589 else: | |
590 # in complete graphs the dominating set will always be of one node | |
591 # thus we return min_cut, which now contains the edges of a node | |
592 # with minimum degree | |
593 return min_cut | |
594 for w in D: | |
595 this_cut = minimum_st_edge_cut(H, v, w, **kwargs) | |
596 if len(this_cut) <= len(min_cut): | |
597 min_cut = this_cut | |
598 | |
599 return min_cut |