Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/connectivity/connectivity.py: 12%
157 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Flow based connectivity algorithms
3"""
5import itertools
6from operator import itemgetter
8import networkx as nx
10# Define the default maximum flow function to use in all flow based
11# connectivity algorithms.
12from networkx.algorithms.flow import (
13 boykov_kolmogorov,
14 build_residual_network,
15 dinitz,
16 edmonds_karp,
17 shortest_augmenting_path,
18)
20default_flow_func = edmonds_karp
22from .utils import build_auxiliary_edge_connectivity, build_auxiliary_node_connectivity
24__all__ = [
25 "average_node_connectivity",
26 "local_node_connectivity",
27 "node_connectivity",
28 "local_edge_connectivity",
29 "edge_connectivity",
30 "all_pairs_node_connectivity",
31]
34@nx._dispatch(
35 graphs={"G": 0, "auxiliary?": 4, "residual?": 5},
36 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
37 preserve_graph_attrs={"auxiliary", "residual"},
38)
39def local_node_connectivity(
40 G, s, t, flow_func=None, auxiliary=None, residual=None, cutoff=None
41):
42 r"""Computes local node connectivity for nodes s and t.
44 Local node connectivity for two non adjacent nodes s and t is the
45 minimum number of nodes that must be removed (along with their incident
46 edges) to disconnect them.
48 This is a flow based implementation of node connectivity. We compute the
49 maximum flow on an auxiliary digraph build from the original input
50 graph (see below for details).
52 Parameters
53 ----------
54 G : NetworkX graph
55 Undirected graph
57 s : node
58 Source node
60 t : node
61 Target node
63 flow_func : function
64 A function for computing the maximum flow among a pair of nodes.
65 The function has to accept at least three parameters: a Digraph,
66 a source node, and a target node. And return a residual network
67 that follows NetworkX conventions (see :meth:`maximum_flow` for
68 details). If flow_func is None, the default maximum flow function
69 (:meth:`edmonds_karp`) is used. See below for details. The choice
70 of the default function may change from version to version and
71 should not be relied on. Default value: None.
73 auxiliary : NetworkX DiGraph
74 Auxiliary digraph to compute flow based node connectivity. It has
75 to have a graph attribute called mapping with a dictionary mapping
76 node names in G and in the auxiliary digraph. If provided
77 it will be reused instead of recreated. Default value: None.
79 residual : NetworkX DiGraph
80 Residual network to compute maximum flow. If provided it will be
81 reused instead of recreated. Default value: None.
83 cutoff : integer, float, or None (default: None)
84 If specified, the maximum flow algorithm will terminate when the
85 flow value reaches or exceeds the cutoff. This only works for flows
86 that support the cutoff parameter (most do) and is ignored otherwise.
88 Returns
89 -------
90 K : integer
91 local node connectivity for nodes s and t
93 Examples
94 --------
95 This function is not imported in the base NetworkX namespace, so you
96 have to explicitly import it from the connectivity package:
98 >>> from networkx.algorithms.connectivity import local_node_connectivity
100 We use in this example the platonic icosahedral graph, which has node
101 connectivity 5.
103 >>> G = nx.icosahedral_graph()
104 >>> local_node_connectivity(G, 0, 6)
105 5
107 If you need to compute local connectivity on several pairs of
108 nodes in the same graph, it is recommended that you reuse the
109 data structures that NetworkX uses in the computation: the
110 auxiliary digraph for node connectivity, and the residual
111 network for the underlying maximum flow computation.
113 Example of how to compute local node connectivity among
114 all pairs of nodes of the platonic icosahedral graph reusing
115 the data structures.
117 >>> import itertools
118 >>> # You also have to explicitly import the function for
119 >>> # building the auxiliary digraph from the connectivity package
120 >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity
121 ...
122 >>> H = build_auxiliary_node_connectivity(G)
123 >>> # And the function for building the residual network from the
124 >>> # flow package
125 >>> from networkx.algorithms.flow import build_residual_network
126 >>> # Note that the auxiliary digraph has an edge attribute named capacity
127 >>> R = build_residual_network(H, "capacity")
128 >>> result = dict.fromkeys(G, dict())
129 >>> # Reuse the auxiliary digraph and the residual network by passing them
130 >>> # as parameters
131 >>> for u, v in itertools.combinations(G, 2):
132 ... k = local_node_connectivity(G, u, v, auxiliary=H, residual=R)
133 ... result[u][v] = k
134 ...
135 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
136 True
138 You can also use alternative flow algorithms for computing node
139 connectivity. For instance, in dense networks the algorithm
140 :meth:`shortest_augmenting_path` will usually perform better than
141 the default :meth:`edmonds_karp` which is faster for sparse
142 networks with highly skewed degree distributions. Alternative flow
143 functions have to be explicitly imported from the flow package.
145 >>> from networkx.algorithms.flow import shortest_augmenting_path
146 >>> local_node_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
147 5
149 Notes
150 -----
151 This is a flow based implementation of node connectivity. We compute the
152 maximum flow using, by default, the :meth:`edmonds_karp` algorithm (see:
153 :meth:`maximum_flow`) on an auxiliary digraph build from the original
154 input graph:
156 For an undirected graph G having `n` nodes and `m` edges we derive a
157 directed graph H with `2n` nodes and `2m+n` arcs by replacing each
158 original node `v` with two nodes `v_A`, `v_B` linked by an (internal)
159 arc in H. Then for each edge (`u`, `v`) in G we add two arcs
160 (`u_B`, `v_A`) and (`v_B`, `u_A`) in H. Finally we set the attribute
161 capacity = 1 for each arc in H [1]_ .
163 For a directed graph G having `n` nodes and `m` arcs we derive a
164 directed graph H with `2n` nodes and `m+n` arcs by replacing each
165 original node `v` with two nodes `v_A`, `v_B` linked by an (internal)
166 arc (`v_A`, `v_B`) in H. Then for each arc (`u`, `v`) in G we add one arc
167 (`u_B`, `v_A`) in H. Finally we set the attribute capacity = 1 for
168 each arc in H.
170 This is equal to the local node connectivity because the value of
171 a maximum s-t-flow is equal to the capacity of a minimum s-t-cut.
173 See also
174 --------
175 :meth:`local_edge_connectivity`
176 :meth:`node_connectivity`
177 :meth:`minimum_node_cut`
178 :meth:`maximum_flow`
179 :meth:`edmonds_karp`
180 :meth:`preflow_push`
181 :meth:`shortest_augmenting_path`
183 References
184 ----------
185 .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and
186 Erlebach, 'Network Analysis: Methodological Foundations', Lecture
187 Notes in Computer Science, Volume 3418, Springer-Verlag, 2005.
188 http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
190 """
191 if flow_func is None:
192 flow_func = default_flow_func
194 if auxiliary is None:
195 H = build_auxiliary_node_connectivity(G)
196 else:
197 H = auxiliary
199 mapping = H.graph.get("mapping", None)
200 if mapping is None:
201 raise nx.NetworkXError("Invalid auxiliary digraph.")
203 kwargs = {"flow_func": flow_func, "residual": residual}
204 if flow_func is shortest_augmenting_path:
205 kwargs["cutoff"] = cutoff
206 kwargs["two_phase"] = True
207 elif flow_func is edmonds_karp:
208 kwargs["cutoff"] = cutoff
209 elif flow_func is dinitz:
210 kwargs["cutoff"] = cutoff
211 elif flow_func is boykov_kolmogorov:
212 kwargs["cutoff"] = cutoff
214 return nx.maximum_flow_value(H, f"{mapping[s]}B", f"{mapping[t]}A", **kwargs)
217@nx._dispatch
218def node_connectivity(G, s=None, t=None, flow_func=None):
219 r"""Returns node connectivity for a graph or digraph G.
221 Node connectivity is equal to the minimum number of nodes that
222 must be removed to disconnect G or render it trivial. If source
223 and target nodes are provided, this function returns the local node
224 connectivity: the minimum number of nodes that must be removed to break
225 all paths from source to target in G.
227 Parameters
228 ----------
229 G : NetworkX graph
230 Undirected graph
232 s : node
233 Source node. Optional. Default value: None.
235 t : node
236 Target node. Optional. Default value: None.
238 flow_func : function
239 A function for computing the maximum flow among a pair of nodes.
240 The function has to accept at least three parameters: a Digraph,
241 a source node, and a target node. And return a residual network
242 that follows NetworkX conventions (see :meth:`maximum_flow` for
243 details). If flow_func is None, the default maximum flow function
244 (:meth:`edmonds_karp`) is used. See below for details. The
245 choice of the default function may change from version
246 to version and should not be relied on. Default value: None.
248 Returns
249 -------
250 K : integer
251 Node connectivity of G, or local node connectivity if source
252 and target are provided.
254 Examples
255 --------
256 >>> # Platonic icosahedral graph is 5-node-connected
257 >>> G = nx.icosahedral_graph()
258 >>> nx.node_connectivity(G)
259 5
261 You can use alternative flow algorithms for the underlying maximum
262 flow computation. In dense networks the algorithm
263 :meth:`shortest_augmenting_path` will usually perform better
264 than the default :meth:`edmonds_karp`, which is faster for
265 sparse networks with highly skewed degree distributions. Alternative
266 flow functions have to be explicitly imported from the flow package.
268 >>> from networkx.algorithms.flow import shortest_augmenting_path
269 >>> nx.node_connectivity(G, flow_func=shortest_augmenting_path)
270 5
272 If you specify a pair of nodes (source and target) as parameters,
273 this function returns the value of local node connectivity.
275 >>> nx.node_connectivity(G, 3, 7)
276 5
278 If you need to perform several local computations among different
279 pairs of nodes on the same graph, it is recommended that you reuse
280 the data structures used in the maximum flow computations. See
281 :meth:`local_node_connectivity` for details.
283 Notes
284 -----
285 This is a flow based implementation of node connectivity. The
286 algorithm works by solving $O((n-\delta-1+\delta(\delta-1)/2))$
287 maximum flow problems on an auxiliary digraph. Where $\delta$
288 is the minimum degree of G. For details about the auxiliary
289 digraph and the computation of local node connectivity see
290 :meth:`local_node_connectivity`. This implementation is based
291 on algorithm 11 in [1]_.
293 See also
294 --------
295 :meth:`local_node_connectivity`
296 :meth:`edge_connectivity`
297 :meth:`maximum_flow`
298 :meth:`edmonds_karp`
299 :meth:`preflow_push`
300 :meth:`shortest_augmenting_path`
302 References
303 ----------
304 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
305 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
307 """
308 if (s is not None and t is None) or (s is None and t is not None):
309 raise nx.NetworkXError("Both source and target must be specified.")
311 # Local node connectivity
312 if s is not None and t is not None:
313 if s not in G:
314 raise nx.NetworkXError(f"node {s} not in graph")
315 if t not in G:
316 raise nx.NetworkXError(f"node {t} not in graph")
317 return local_node_connectivity(G, s, t, flow_func=flow_func)
319 # Global node connectivity
320 if G.is_directed():
321 if not nx.is_weakly_connected(G):
322 return 0
323 iter_func = itertools.permutations
324 # It is necessary to consider both predecessors
325 # and successors for directed graphs
327 def neighbors(v):
328 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)])
330 else:
331 if not nx.is_connected(G):
332 return 0
333 iter_func = itertools.combinations
334 neighbors = G.neighbors
336 # Reuse the auxiliary digraph and the residual network
337 H = build_auxiliary_node_connectivity(G)
338 R = build_residual_network(H, "capacity")
339 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
341 # Pick a node with minimum degree
342 # Node connectivity is bounded by degree.
343 v, K = min(G.degree(), key=itemgetter(1))
344 # compute local node connectivity with all its non-neighbors nodes
345 for w in set(G) - set(neighbors(v)) - {v}:
346 kwargs["cutoff"] = K
347 K = min(K, local_node_connectivity(G, v, w, **kwargs))
348 # Also for non adjacent pairs of neighbors of v
349 for x, y in iter_func(neighbors(v), 2):
350 if y in G[x]:
351 continue
352 kwargs["cutoff"] = K
353 K = min(K, local_node_connectivity(G, x, y, **kwargs))
355 return K
358@nx._dispatch
359def average_node_connectivity(G, flow_func=None):
360 r"""Returns the average connectivity of a graph G.
362 The average connectivity `\bar{\kappa}` of a graph G is the average
363 of local node connectivity over all pairs of nodes of G [1]_ .
365 .. math::
367 \bar{\kappa}(G) = \frac{\sum_{u,v} \kappa_{G}(u,v)}{{n \choose 2}}
369 Parameters
370 ----------
372 G : NetworkX graph
373 Undirected graph
375 flow_func : function
376 A function for computing the maximum flow among a pair of nodes.
377 The function has to accept at least three parameters: a Digraph,
378 a source node, and a target node. And return a residual network
379 that follows NetworkX conventions (see :meth:`maximum_flow` for
380 details). If flow_func is None, the default maximum flow function
381 (:meth:`edmonds_karp`) is used. See :meth:`local_node_connectivity`
382 for details. The choice of the default function may change from
383 version to version and should not be relied on. Default value: None.
385 Returns
386 -------
387 K : float
388 Average node connectivity
390 See also
391 --------
392 :meth:`local_node_connectivity`
393 :meth:`node_connectivity`
394 :meth:`edge_connectivity`
395 :meth:`maximum_flow`
396 :meth:`edmonds_karp`
397 :meth:`preflow_push`
398 :meth:`shortest_augmenting_path`
400 References
401 ----------
402 .. [1] Beineke, L., O. Oellermann, and R. Pippert (2002). The average
403 connectivity of a graph. Discrete mathematics 252(1-3), 31-45.
404 http://www.sciencedirect.com/science/article/pii/S0012365X01001807
406 """
407 if G.is_directed():
408 iter_func = itertools.permutations
409 else:
410 iter_func = itertools.combinations
412 # Reuse the auxiliary digraph and the residual network
413 H = build_auxiliary_node_connectivity(G)
414 R = build_residual_network(H, "capacity")
415 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
417 num, den = 0, 0
418 for u, v in iter_func(G, 2):
419 num += local_node_connectivity(G, u, v, **kwargs)
420 den += 1
422 if den == 0: # Null Graph
423 return 0
424 return num / den
427@nx._dispatch
428def all_pairs_node_connectivity(G, nbunch=None, flow_func=None):
429 """Compute node connectivity between all pairs of nodes of G.
431 Parameters
432 ----------
433 G : NetworkX graph
434 Undirected graph
436 nbunch: container
437 Container of nodes. If provided node connectivity will be computed
438 only over pairs of nodes in nbunch.
440 flow_func : function
441 A function for computing the maximum flow among a pair of nodes.
442 The function has to accept at least three parameters: a Digraph,
443 a source node, and a target node. And return a residual network
444 that follows NetworkX conventions (see :meth:`maximum_flow` for
445 details). If flow_func is None, the default maximum flow function
446 (:meth:`edmonds_karp`) is used. See below for details. The
447 choice of the default function may change from version
448 to version and should not be relied on. Default value: None.
450 Returns
451 -------
452 all_pairs : dict
453 A dictionary with node connectivity between all pairs of nodes
454 in G, or in nbunch if provided.
456 See also
457 --------
458 :meth:`local_node_connectivity`
459 :meth:`edge_connectivity`
460 :meth:`local_edge_connectivity`
461 :meth:`maximum_flow`
462 :meth:`edmonds_karp`
463 :meth:`preflow_push`
464 :meth:`shortest_augmenting_path`
466 """
467 if nbunch is None:
468 nbunch = G
469 else:
470 nbunch = set(nbunch)
472 directed = G.is_directed()
473 if directed:
474 iter_func = itertools.permutations
475 else:
476 iter_func = itertools.combinations
478 all_pairs = {n: {} for n in nbunch}
480 # Reuse auxiliary digraph and residual network
481 H = build_auxiliary_node_connectivity(G)
482 mapping = H.graph["mapping"]
483 R = build_residual_network(H, "capacity")
484 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
486 for u, v in iter_func(nbunch, 2):
487 K = local_node_connectivity(G, u, v, **kwargs)
488 all_pairs[u][v] = K
489 if not directed:
490 all_pairs[v][u] = K
492 return all_pairs
495@nx._dispatch(
496 graphs={"G": 0, "auxiliary?": 4, "residual?": 5},
497 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
498 preserve_graph_attrs={"residual"},
499)
500def local_edge_connectivity(
501 G, s, t, flow_func=None, auxiliary=None, residual=None, cutoff=None
502):
503 r"""Returns local edge connectivity for nodes s and t in G.
505 Local edge connectivity for two nodes s and t is the minimum number
506 of edges that must be removed to disconnect them.
508 This is a flow based implementation of edge connectivity. We compute the
509 maximum flow on an auxiliary digraph build from the original
510 network (see below for details). This is equal to the local edge
511 connectivity because the value of a maximum s-t-flow is equal to the
512 capacity of a minimum s-t-cut (Ford and Fulkerson theorem) [1]_ .
514 Parameters
515 ----------
516 G : NetworkX graph
517 Undirected or directed graph
519 s : node
520 Source node
522 t : node
523 Target node
525 flow_func : function
526 A function for computing the maximum flow among a pair of nodes.
527 The function has to accept at least three parameters: a Digraph,
528 a source node, and a target node. And return a residual network
529 that follows NetworkX conventions (see :meth:`maximum_flow` for
530 details). If flow_func is None, the default maximum flow function
531 (:meth:`edmonds_karp`) is used. See below for details. The
532 choice of the default function may change from version
533 to version and should not be relied on. Default value: None.
535 auxiliary : NetworkX DiGraph
536 Auxiliary digraph for computing flow based edge connectivity. If
537 provided it will be reused instead of recreated. Default value: None.
539 residual : NetworkX DiGraph
540 Residual network to compute maximum flow. If provided it will be
541 reused instead of recreated. Default value: None.
543 cutoff : integer, float, or None (default: None)
544 If specified, the maximum flow algorithm will terminate when the
545 flow value reaches or exceeds the cutoff. This only works for flows
546 that support the cutoff parameter (most do) and is ignored otherwise.
548 Returns
549 -------
550 K : integer
551 local edge connectivity for nodes s and t.
553 Examples
554 --------
555 This function is not imported in the base NetworkX namespace, so you
556 have to explicitly import it from the connectivity package:
558 >>> from networkx.algorithms.connectivity import local_edge_connectivity
560 We use in this example the platonic icosahedral graph, which has edge
561 connectivity 5.
563 >>> G = nx.icosahedral_graph()
564 >>> local_edge_connectivity(G, 0, 6)
565 5
567 If you need to compute local connectivity on several pairs of
568 nodes in the same graph, it is recommended that you reuse the
569 data structures that NetworkX uses in the computation: the
570 auxiliary digraph for edge connectivity, and the residual
571 network for the underlying maximum flow computation.
573 Example of how to compute local edge connectivity among
574 all pairs of nodes of the platonic icosahedral graph reusing
575 the data structures.
577 >>> import itertools
578 >>> # You also have to explicitly import the function for
579 >>> # building the auxiliary digraph from the connectivity package
580 >>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
581 >>> H = build_auxiliary_edge_connectivity(G)
582 >>> # And the function for building the residual network from the
583 >>> # flow package
584 >>> from networkx.algorithms.flow import build_residual_network
585 >>> # Note that the auxiliary digraph has an edge attribute named capacity
586 >>> R = build_residual_network(H, "capacity")
587 >>> result = dict.fromkeys(G, dict())
588 >>> # Reuse the auxiliary digraph and the residual network by passing them
589 >>> # as parameters
590 >>> for u, v in itertools.combinations(G, 2):
591 ... k = local_edge_connectivity(G, u, v, auxiliary=H, residual=R)
592 ... result[u][v] = k
593 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
594 True
596 You can also use alternative flow algorithms for computing edge
597 connectivity. For instance, in dense networks the algorithm
598 :meth:`shortest_augmenting_path` will usually perform better than
599 the default :meth:`edmonds_karp` which is faster for sparse
600 networks with highly skewed degree distributions. Alternative flow
601 functions have to be explicitly imported from the flow package.
603 >>> from networkx.algorithms.flow import shortest_augmenting_path
604 >>> local_edge_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
605 5
607 Notes
608 -----
609 This is a flow based implementation of edge connectivity. We compute the
610 maximum flow using, by default, the :meth:`edmonds_karp` algorithm on an
611 auxiliary digraph build from the original input graph:
613 If the input graph is undirected, we replace each edge (`u`,`v`) with
614 two reciprocal arcs (`u`, `v`) and (`v`, `u`) and then we set the attribute
615 'capacity' for each arc to 1. If the input graph is directed we simply
616 add the 'capacity' attribute. This is an implementation of algorithm 1
617 in [1]_.
619 The maximum flow in the auxiliary network is equal to the local edge
620 connectivity because the value of a maximum s-t-flow is equal to the
621 capacity of a minimum s-t-cut (Ford and Fulkerson theorem).
623 See also
624 --------
625 :meth:`edge_connectivity`
626 :meth:`local_node_connectivity`
627 :meth:`node_connectivity`
628 :meth:`maximum_flow`
629 :meth:`edmonds_karp`
630 :meth:`preflow_push`
631 :meth:`shortest_augmenting_path`
633 References
634 ----------
635 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
636 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
638 """
639 if flow_func is None:
640 flow_func = default_flow_func
642 if auxiliary is None:
643 H = build_auxiliary_edge_connectivity(G)
644 else:
645 H = auxiliary
647 kwargs = {"flow_func": flow_func, "residual": residual}
648 if flow_func is shortest_augmenting_path:
649 kwargs["cutoff"] = cutoff
650 kwargs["two_phase"] = True
651 elif flow_func is edmonds_karp:
652 kwargs["cutoff"] = cutoff
653 elif flow_func is dinitz:
654 kwargs["cutoff"] = cutoff
655 elif flow_func is boykov_kolmogorov:
656 kwargs["cutoff"] = cutoff
658 return nx.maximum_flow_value(H, s, t, **kwargs)
661@nx._dispatch
662def edge_connectivity(G, s=None, t=None, flow_func=None, cutoff=None):
663 r"""Returns the edge connectivity of the graph or digraph G.
665 The edge connectivity is equal to the minimum number of edges that
666 must be removed to disconnect G or render it trivial. If source
667 and target nodes are provided, this function returns the local edge
668 connectivity: the minimum number of edges that must be removed to
669 break all paths from source to target in G.
671 Parameters
672 ----------
673 G : NetworkX graph
674 Undirected or directed graph
676 s : node
677 Source node. Optional. Default value: None.
679 t : node
680 Target node. Optional. Default value: None.
682 flow_func : function
683 A function for computing the maximum flow among a pair of nodes.
684 The function has to accept at least three parameters: a Digraph,
685 a source node, and a target node. And return a residual network
686 that follows NetworkX conventions (see :meth:`maximum_flow` for
687 details). If flow_func is None, the default maximum flow function
688 (:meth:`edmonds_karp`) is used. See below for details. The
689 choice of the default function may change from version
690 to version and should not be relied on. Default value: None.
692 cutoff : integer, float, or None (default: None)
693 If specified, the maximum flow algorithm will terminate when the
694 flow value reaches or exceeds the cutoff. This only works for flows
695 that support the cutoff parameter (most do) and is ignored otherwise.
697 Returns
698 -------
699 K : integer
700 Edge connectivity for G, or local edge connectivity if source
701 and target were provided
703 Examples
704 --------
705 >>> # Platonic icosahedral graph is 5-edge-connected
706 >>> G = nx.icosahedral_graph()
707 >>> nx.edge_connectivity(G)
708 5
710 You can use alternative flow algorithms for the underlying
711 maximum flow computation. In dense networks the algorithm
712 :meth:`shortest_augmenting_path` will usually perform better
713 than the default :meth:`edmonds_karp`, which is faster for
714 sparse networks with highly skewed degree distributions.
715 Alternative flow functions have to be explicitly imported
716 from the flow package.
718 >>> from networkx.algorithms.flow import shortest_augmenting_path
719 >>> nx.edge_connectivity(G, flow_func=shortest_augmenting_path)
720 5
722 If you specify a pair of nodes (source and target) as parameters,
723 this function returns the value of local edge connectivity.
725 >>> nx.edge_connectivity(G, 3, 7)
726 5
728 If you need to perform several local computations among different
729 pairs of nodes on the same graph, it is recommended that you reuse
730 the data structures used in the maximum flow computations. See
731 :meth:`local_edge_connectivity` for details.
733 Notes
734 -----
735 This is a flow based implementation of global edge connectivity.
736 For undirected graphs the algorithm works by finding a 'small'
737 dominating set of nodes of G (see algorithm 7 in [1]_ ) and
738 computing local maximum flow (see :meth:`local_edge_connectivity`)
739 between an arbitrary node in the dominating set and the rest of
740 nodes in it. This is an implementation of algorithm 6 in [1]_ .
741 For directed graphs, the algorithm does n calls to the maximum
742 flow function. This is an implementation of algorithm 8 in [1]_ .
744 See also
745 --------
746 :meth:`local_edge_connectivity`
747 :meth:`local_node_connectivity`
748 :meth:`node_connectivity`
749 :meth:`maximum_flow`
750 :meth:`edmonds_karp`
751 :meth:`preflow_push`
752 :meth:`shortest_augmenting_path`
753 :meth:`k_edge_components`
754 :meth:`k_edge_subgraphs`
756 References
757 ----------
758 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
759 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
761 """
762 if (s is not None and t is None) or (s is None and t is not None):
763 raise nx.NetworkXError("Both source and target must be specified.")
765 # Local edge connectivity
766 if s is not None and t is not None:
767 if s not in G:
768 raise nx.NetworkXError(f"node {s} not in graph")
769 if t not in G:
770 raise nx.NetworkXError(f"node {t} not in graph")
771 return local_edge_connectivity(G, s, t, flow_func=flow_func, cutoff=cutoff)
773 # Global edge connectivity
774 # reuse auxiliary digraph and residual network
775 H = build_auxiliary_edge_connectivity(G)
776 R = build_residual_network(H, "capacity")
777 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
779 if G.is_directed():
780 # Algorithm 8 in [1]
781 if not nx.is_weakly_connected(G):
782 return 0
784 # initial value for \lambda is minimum degree
785 L = min(d for n, d in G.degree())
786 nodes = list(G)
787 n = len(nodes)
789 if cutoff is not None:
790 L = min(cutoff, L)
792 for i in range(n):
793 kwargs["cutoff"] = L
794 try:
795 L = min(L, local_edge_connectivity(G, nodes[i], nodes[i + 1], **kwargs))
796 except IndexError: # last node!
797 L = min(L, local_edge_connectivity(G, nodes[i], nodes[0], **kwargs))
798 return L
799 else: # undirected
800 # Algorithm 6 in [1]
801 if not nx.is_connected(G):
802 return 0
804 # initial value for \lambda is minimum degree
805 L = min(d for n, d in G.degree())
807 if cutoff is not None:
808 L = min(cutoff, L)
810 # A dominating set is \lambda-covering
811 # We need a dominating set with at least two nodes
812 for node in G:
813 D = nx.dominating_set(G, start_with=node)
814 v = D.pop()
815 if D:
816 break
817 else:
818 # in complete graphs the dominating sets will always be of one node
819 # thus we return min degree
820 return L
822 for w in D:
823 kwargs["cutoff"] = L
824 L = min(L, local_edge_connectivity(G, v, w, **kwargs))
826 return L