Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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 preflow_push,
18 shortest_augmenting_path,
19)
21from .utils import build_auxiliary_edge_connectivity, build_auxiliary_node_connectivity
23default_flow_func = edmonds_karp
25__all__ = [
26 "average_node_connectivity",
27 "local_node_connectivity",
28 "node_connectivity",
29 "local_edge_connectivity",
30 "edge_connectivity",
31 "all_pairs_node_connectivity",
32]
35@nx._dispatchable(graphs={"G": 0, "auxiliary?": 4}, preserve_graph_attrs={"auxiliary"})
36def local_node_connectivity(
37 G, s, t, flow_func=None, auxiliary=None, residual=None, cutoff=None
38):
39 r"""Computes local node connectivity for nodes s and t.
41 Local node connectivity for two non adjacent nodes s and t is the
42 minimum number of nodes that must be removed (along with their incident
43 edges) to disconnect them.
45 This is a flow based implementation of node connectivity. We compute the
46 maximum flow on an auxiliary digraph build from the original input
47 graph (see below for details).
49 Parameters
50 ----------
51 G : NetworkX graph
52 Undirected graph
54 s : node
55 Source node
57 t : node
58 Target node
60 flow_func : function
61 A function for computing the maximum flow among a pair of nodes.
62 The function has to accept at least three parameters: a Digraph,
63 a source node, and a target node. And return a residual network
64 that follows NetworkX conventions (see :meth:`maximum_flow` for
65 details). If flow_func is None, the default maximum flow function
66 (:meth:`edmonds_karp`) is used. See below for details. The choice
67 of the default function may change from version to version and
68 should not be relied on. Default value: None.
70 auxiliary : NetworkX DiGraph
71 Auxiliary digraph to compute flow based node connectivity. It has
72 to have a graph attribute called mapping with a dictionary mapping
73 node names in G and in the auxiliary digraph. If provided
74 it will be reused instead of recreated. Default value: None.
76 residual : NetworkX DiGraph
77 Residual network to compute maximum flow. If provided it will be
78 reused instead of recreated. Default value: None.
80 cutoff : integer, float, or None (default: None)
81 If specified, the maximum flow algorithm will terminate when the
82 flow value reaches or exceeds the cutoff. This only works for flows
83 that support the cutoff parameter (most do) and is ignored otherwise.
85 Returns
86 -------
87 K : integer
88 local node connectivity for nodes s and t
90 Examples
91 --------
92 This function is not imported in the base NetworkX namespace, so you
93 have to explicitly import it from the connectivity package:
95 >>> from networkx.algorithms.connectivity import local_node_connectivity
97 We use in this example the platonic icosahedral graph, which has node
98 connectivity 5.
100 >>> G = nx.icosahedral_graph()
101 >>> local_node_connectivity(G, 0, 6)
102 5
104 If you need to compute local connectivity on several pairs of
105 nodes in the same graph, it is recommended that you reuse the
106 data structures that NetworkX uses in the computation: the
107 auxiliary digraph for node connectivity, and the residual
108 network for the underlying maximum flow computation.
110 Example of how to compute local node connectivity among
111 all pairs of nodes of the platonic icosahedral graph reusing
112 the data structures.
114 >>> import itertools
115 >>> # You also have to explicitly import the function for
116 >>> # building the auxiliary digraph from the connectivity package
117 >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity
118 >>> H = build_auxiliary_node_connectivity(G)
119 >>> # And the function for building the residual network from the
120 >>> # flow package
121 >>> from networkx.algorithms.flow import build_residual_network
122 >>> # Note that the auxiliary digraph has an edge attribute named capacity
123 >>> R = build_residual_network(H, "capacity")
124 >>> result = dict.fromkeys(G, dict())
125 >>> # Reuse the auxiliary digraph and the residual network by passing them
126 >>> # as parameters
127 >>> for u, v in itertools.combinations(G, 2):
128 ... k = local_node_connectivity(G, u, v, auxiliary=H, residual=R)
129 ... result[u][v] = k
130 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
131 True
133 You can also use alternative flow algorithms for computing node
134 connectivity. For instance, in dense networks the algorithm
135 :meth:`shortest_augmenting_path` will usually perform better than
136 the default :meth:`edmonds_karp` which is faster for sparse
137 networks with highly skewed degree distributions. Alternative flow
138 functions have to be explicitly imported from the flow package.
140 >>> from networkx.algorithms.flow import shortest_augmenting_path
141 >>> local_node_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
142 5
144 Notes
145 -----
146 This is a flow based implementation of node connectivity. We compute the
147 maximum flow using, by default, the :meth:`edmonds_karp` algorithm (see:
148 :meth:`maximum_flow`) on an auxiliary digraph build from the original
149 input graph:
151 For an undirected graph G having `n` nodes and `m` edges we derive a
152 directed graph H with `2n` nodes and `2m+n` arcs by replacing each
153 original node `v` with two nodes `v_A`, `v_B` linked by an (internal)
154 arc in H. Then for each edge (`u`, `v`) in G we add two arcs
155 (`u_B`, `v_A`) and (`v_B`, `u_A`) in H. Finally we set the attribute
156 capacity = 1 for each arc in H [1]_ .
158 For a directed graph G having `n` nodes and `m` arcs we derive a
159 directed graph H with `2n` nodes and `m+n` arcs by replacing each
160 original node `v` with two nodes `v_A`, `v_B` linked by an (internal)
161 arc (`v_A`, `v_B`) in H. Then for each arc (`u`, `v`) in G we add one arc
162 (`u_B`, `v_A`) in H. Finally we set the attribute capacity = 1 for
163 each arc in H.
165 This is equal to the local node connectivity because the value of
166 a maximum s-t-flow is equal to the capacity of a minimum s-t-cut.
168 See also
169 --------
170 :meth:`local_edge_connectivity`
171 :meth:`node_connectivity`
172 :meth:`minimum_node_cut`
173 :meth:`maximum_flow`
174 :meth:`edmonds_karp`
175 :meth:`preflow_push`
176 :meth:`shortest_augmenting_path`
178 References
179 ----------
180 .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and
181 Erlebach, 'Network Analysis: Methodological Foundations', Lecture
182 Notes in Computer Science, Volume 3418, Springer-Verlag, 2005.
183 http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
185 """
186 if flow_func is None:
187 flow_func = default_flow_func
189 if auxiliary is None:
190 H = build_auxiliary_node_connectivity(G)
191 else:
192 H = auxiliary
194 mapping = H.graph.get("mapping", None)
195 if mapping is None:
196 raise nx.NetworkXError("Invalid auxiliary digraph.")
198 kwargs = {"flow_func": flow_func, "residual": residual}
200 if flow_func is not preflow_push:
201 kwargs["cutoff"] = cutoff
203 if flow_func is shortest_augmenting_path:
204 kwargs["two_phase"] = True
206 return nx.maximum_flow_value(H, f"{mapping[s]}B", f"{mapping[t]}A", **kwargs)
209@nx._dispatchable
210def node_connectivity(G, s=None, t=None, flow_func=None):
211 r"""Returns node connectivity for a graph or digraph G.
213 Node connectivity is equal to the minimum number of nodes that
214 must be removed to disconnect G or render it trivial. If source
215 and target nodes are provided, this function returns the local node
216 connectivity: the minimum number of nodes that must be removed to break
217 all paths from source to target in G.
219 Parameters
220 ----------
221 G : NetworkX graph
222 Undirected graph
224 s : node
225 Source node. Optional. Default value: None.
227 t : node
228 Target node. Optional. Default value: None.
230 flow_func : function
231 A function for computing the maximum flow among a pair of nodes.
232 The function has to accept at least three parameters: a Digraph,
233 a source node, and a target node. And return a residual network
234 that follows NetworkX conventions (see :meth:`maximum_flow` for
235 details). If flow_func is None, the default maximum flow function
236 (:meth:`edmonds_karp`) is used. See below for details. The
237 choice of the default function may change from version
238 to version and should not be relied on. Default value: None.
240 Returns
241 -------
242 K : integer
243 Node connectivity of G, or local node connectivity if source
244 and target are provided.
246 Examples
247 --------
248 >>> # Platonic icosahedral graph is 5-node-connected
249 >>> G = nx.icosahedral_graph()
250 >>> nx.node_connectivity(G)
251 5
253 You can use alternative flow algorithms for the underlying maximum
254 flow computation. In dense networks the algorithm
255 :meth:`shortest_augmenting_path` will usually perform better
256 than the default :meth:`edmonds_karp`, which is faster for
257 sparse networks with highly skewed degree distributions. Alternative
258 flow functions have to be explicitly imported from the flow package.
260 >>> from networkx.algorithms.flow import shortest_augmenting_path
261 >>> nx.node_connectivity(G, flow_func=shortest_augmenting_path)
262 5
264 If you specify a pair of nodes (source and target) as parameters,
265 this function returns the value of local node connectivity.
267 >>> nx.node_connectivity(G, 3, 7)
268 5
270 If you need to perform several local computations among different
271 pairs of nodes on the same graph, it is recommended that you reuse
272 the data structures used in the maximum flow computations. See
273 :meth:`local_node_connectivity` for details.
275 Notes
276 -----
277 This is a flow based implementation of node connectivity. The
278 algorithm works by solving $O((n-\delta-1+\delta(\delta-1)/2))$
279 maximum flow problems on an auxiliary digraph. Where $\delta$
280 is the minimum degree of G. For details about the auxiliary
281 digraph and the computation of local node connectivity see
282 :meth:`local_node_connectivity`. This implementation is based
283 on algorithm 11 in [1]_.
285 See also
286 --------
287 :meth:`local_node_connectivity`
288 :meth:`edge_connectivity`
289 :meth:`maximum_flow`
290 :meth:`edmonds_karp`
291 :meth:`preflow_push`
292 :meth:`shortest_augmenting_path`
294 References
295 ----------
296 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
297 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
299 """
300 if (s is not None and t is None) or (s is None and t is not None):
301 raise nx.NetworkXError("Both source and target must be specified.")
303 # Local node connectivity
304 if s is not None and t is not None:
305 if s not in G:
306 raise nx.NetworkXError(f"node {s} not in graph")
307 if t not in G:
308 raise nx.NetworkXError(f"node {t} not in graph")
309 return local_node_connectivity(G, s, t, flow_func=flow_func)
311 # Global node connectivity
312 if G.is_directed():
313 if not nx.is_weakly_connected(G):
314 return 0
315 iter_func = itertools.permutations
316 # It is necessary to consider both predecessors
317 # and successors for directed graphs
319 def neighbors(v):
320 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)])
322 else:
323 if not nx.is_connected(G):
324 return 0
325 iter_func = itertools.combinations
326 neighbors = G.neighbors
328 # Reuse the auxiliary digraph and the residual network
329 H = build_auxiliary_node_connectivity(G)
330 R = build_residual_network(H, "capacity")
331 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
333 # Pick a node with minimum degree
334 # Node connectivity is bounded by degree.
335 v, K = min(G.degree(), key=itemgetter(1))
336 # compute local node connectivity with all its non-neighbors nodes
337 for w in set(G) - set(neighbors(v)) - {v}:
338 kwargs["cutoff"] = K
339 K = min(K, local_node_connectivity(G, v, w, **kwargs))
340 # Also for non adjacent pairs of neighbors of v
341 for x, y in iter_func(neighbors(v), 2):
342 if y in G[x]:
343 continue
344 kwargs["cutoff"] = K
345 K = min(K, local_node_connectivity(G, x, y, **kwargs))
347 return K
350@nx._dispatchable
351def average_node_connectivity(G, flow_func=None):
352 r"""Returns the average connectivity of a graph G.
354 The average connectivity `\bar{\kappa}` of a graph G is the average
355 of local node connectivity over all pairs of nodes of G [1]_ .
357 .. math::
359 \bar{\kappa}(G) = \frac{\sum_{u,v} \kappa_{G}(u,v)}{{n \choose 2}}
361 Parameters
362 ----------
364 G : NetworkX graph
365 Undirected graph
367 flow_func : function
368 A function for computing the maximum flow among a pair of nodes.
369 The function has to accept at least three parameters: a Digraph,
370 a source node, and a target node. And return a residual network
371 that follows NetworkX conventions (see :meth:`maximum_flow` for
372 details). If flow_func is None, the default maximum flow function
373 (:meth:`edmonds_karp`) is used. See :meth:`local_node_connectivity`
374 for details. The choice of the default function may change from
375 version to version and should not be relied on. Default value: None.
377 Returns
378 -------
379 K : float
380 Average node connectivity
382 See also
383 --------
384 :meth:`local_node_connectivity`
385 :meth:`node_connectivity`
386 :meth:`edge_connectivity`
387 :meth:`maximum_flow`
388 :meth:`edmonds_karp`
389 :meth:`preflow_push`
390 :meth:`shortest_augmenting_path`
392 References
393 ----------
394 .. [1] Beineke, L., O. Oellermann, and R. Pippert (2002). The average
395 connectivity of a graph. Discrete mathematics 252(1-3), 31-45.
396 http://www.sciencedirect.com/science/article/pii/S0012365X01001807
398 """
399 if G.is_directed():
400 iter_func = itertools.permutations
401 else:
402 iter_func = itertools.combinations
404 # Reuse the auxiliary digraph and the residual network
405 H = build_auxiliary_node_connectivity(G)
406 R = build_residual_network(H, "capacity")
407 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
409 num, den = 0, 0
410 for u, v in iter_func(G, 2):
411 num += local_node_connectivity(G, u, v, **kwargs)
412 den += 1
414 if den == 0: # Null Graph
415 return 0
416 return num / den
419@nx._dispatchable
420def all_pairs_node_connectivity(G, nbunch=None, flow_func=None):
421 """Compute node connectivity between all pairs of nodes of G.
423 Parameters
424 ----------
425 G : NetworkX graph
426 Undirected graph
428 nbunch: container
429 Container of nodes. If provided node connectivity will be computed
430 only over pairs of nodes in nbunch.
432 flow_func : function
433 A function for computing the maximum flow among a pair of nodes.
434 The function has to accept at least three parameters: a Digraph,
435 a source node, and a target node. And return a residual network
436 that follows NetworkX conventions (see :meth:`maximum_flow` for
437 details). If flow_func is None, the default maximum flow function
438 (:meth:`edmonds_karp`) is used. See below for details. The
439 choice of the default function may change from version
440 to version and should not be relied on. Default value: None.
442 Returns
443 -------
444 all_pairs : dict
445 A dictionary with node connectivity between all pairs of nodes
446 in G, or in nbunch if provided.
448 See also
449 --------
450 :meth:`local_node_connectivity`
451 :meth:`edge_connectivity`
452 :meth:`local_edge_connectivity`
453 :meth:`maximum_flow`
454 :meth:`edmonds_karp`
455 :meth:`preflow_push`
456 :meth:`shortest_augmenting_path`
458 """
459 if nbunch is None:
460 nbunch = G
461 else:
462 nbunch = set(nbunch)
464 directed = G.is_directed()
465 if directed:
466 iter_func = itertools.permutations
467 else:
468 iter_func = itertools.combinations
470 all_pairs = {n: {} for n in nbunch}
472 # Reuse auxiliary digraph and residual network
473 H = build_auxiliary_node_connectivity(G)
474 mapping = H.graph["mapping"]
475 R = build_residual_network(H, "capacity")
476 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
478 for u, v in iter_func(nbunch, 2):
479 K = local_node_connectivity(G, u, v, **kwargs)
480 all_pairs[u][v] = K
481 if not directed:
482 all_pairs[v][u] = K
484 return all_pairs
487@nx._dispatchable(graphs={"G": 0, "auxiliary?": 4})
488def local_edge_connectivity(
489 G, s, t, flow_func=None, auxiliary=None, residual=None, cutoff=None
490):
491 r"""Returns local edge connectivity for nodes s and t in G.
493 Local edge connectivity for two nodes s and t is the minimum number
494 of edges that must be removed to disconnect them.
496 This is a flow based implementation of edge connectivity. We compute the
497 maximum flow on an auxiliary digraph build from the original
498 network (see below for details). This is equal to the local edge
499 connectivity because the value of a maximum s-t-flow is equal to the
500 capacity of a minimum s-t-cut (Ford and Fulkerson theorem) [1]_ .
502 Parameters
503 ----------
504 G : NetworkX graph
505 Undirected or directed graph
507 s : node
508 Source node
510 t : node
511 Target node
513 flow_func : function
514 A function for computing the maximum flow among a pair of nodes.
515 The function has to accept at least three parameters: a Digraph,
516 a source node, and a target node. And return a residual network
517 that follows NetworkX conventions (see :meth:`maximum_flow` for
518 details). If flow_func is None, the default maximum flow function
519 (:meth:`edmonds_karp`) is used. See below for details. The
520 choice of the default function may change from version
521 to version and should not be relied on. Default value: None.
523 auxiliary : NetworkX DiGraph
524 Auxiliary digraph for computing flow based edge connectivity. If
525 provided it will be reused instead of recreated. Default value: None.
527 residual : NetworkX DiGraph
528 Residual network to compute maximum flow. If provided it will be
529 reused instead of recreated. Default value: None.
531 cutoff : integer, float, or None (default: None)
532 If specified, the maximum flow algorithm will terminate when the
533 flow value reaches or exceeds the cutoff. This only works for flows
534 that support the cutoff parameter (most do) and is ignored otherwise.
536 Returns
537 -------
538 K : integer
539 local edge connectivity for nodes s and t.
541 Examples
542 --------
543 This function is not imported in the base NetworkX namespace, so you
544 have to explicitly import it from the connectivity package:
546 >>> from networkx.algorithms.connectivity import local_edge_connectivity
548 We use in this example the platonic icosahedral graph, which has edge
549 connectivity 5.
551 >>> G = nx.icosahedral_graph()
552 >>> local_edge_connectivity(G, 0, 6)
553 5
555 If you need to compute local connectivity on several pairs of
556 nodes in the same graph, it is recommended that you reuse the
557 data structures that NetworkX uses in the computation: the
558 auxiliary digraph for edge connectivity, and the residual
559 network for the underlying maximum flow computation.
561 Example of how to compute local edge connectivity among
562 all pairs of nodes of the platonic icosahedral graph reusing
563 the data structures.
565 >>> import itertools
566 >>> # You also have to explicitly import the function for
567 >>> # building the auxiliary digraph from the connectivity package
568 >>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
569 >>> H = build_auxiliary_edge_connectivity(G)
570 >>> # And the function for building the residual network from the
571 >>> # flow package
572 >>> from networkx.algorithms.flow import build_residual_network
573 >>> # Note that the auxiliary digraph has an edge attribute named capacity
574 >>> R = build_residual_network(H, "capacity")
575 >>> result = dict.fromkeys(G, dict())
576 >>> # Reuse the auxiliary digraph and the residual network by passing them
577 >>> # as parameters
578 >>> for u, v in itertools.combinations(G, 2):
579 ... k = local_edge_connectivity(G, u, v, auxiliary=H, residual=R)
580 ... result[u][v] = k
581 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
582 True
584 You can also use alternative flow algorithms for computing edge
585 connectivity. For instance, in dense networks the algorithm
586 :meth:`shortest_augmenting_path` will usually perform better than
587 the default :meth:`edmonds_karp` which is faster for sparse
588 networks with highly skewed degree distributions. Alternative flow
589 functions have to be explicitly imported from the flow package.
591 >>> from networkx.algorithms.flow import shortest_augmenting_path
592 >>> local_edge_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
593 5
595 Notes
596 -----
597 This is a flow based implementation of edge connectivity. We compute the
598 maximum flow using, by default, the :meth:`edmonds_karp` algorithm on an
599 auxiliary digraph build from the original input graph:
601 If the input graph is undirected, we replace each edge (`u`,`v`) with
602 two reciprocal arcs (`u`, `v`) and (`v`, `u`) and then we set the attribute
603 'capacity' for each arc to 1. If the input graph is directed we simply
604 add the 'capacity' attribute. This is an implementation of algorithm 1
605 in [1]_.
607 The maximum flow in the auxiliary network is equal to the local edge
608 connectivity because the value of a maximum s-t-flow is equal to the
609 capacity of a minimum s-t-cut (Ford and Fulkerson theorem).
611 See also
612 --------
613 :meth:`edge_connectivity`
614 :meth:`local_node_connectivity`
615 :meth:`node_connectivity`
616 :meth:`maximum_flow`
617 :meth:`edmonds_karp`
618 :meth:`preflow_push`
619 :meth:`shortest_augmenting_path`
621 References
622 ----------
623 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
624 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
626 """
627 if flow_func is None:
628 flow_func = default_flow_func
630 if auxiliary is None:
631 H = build_auxiliary_edge_connectivity(G)
632 else:
633 H = auxiliary
635 kwargs = {"flow_func": flow_func, "residual": residual}
637 if flow_func is not preflow_push:
638 kwargs["cutoff"] = cutoff
640 if flow_func is shortest_augmenting_path:
641 kwargs["two_phase"] = True
643 return nx.maximum_flow_value(H, s, t, **kwargs)
646@nx._dispatchable
647def edge_connectivity(G, s=None, t=None, flow_func=None, cutoff=None):
648 r"""Returns the edge connectivity of the graph or digraph G.
650 The edge connectivity is equal to the minimum number of edges that
651 must be removed to disconnect G or render it trivial. If source
652 and target nodes are provided, this function returns the local edge
653 connectivity: the minimum number of edges that must be removed to
654 break all paths from source to target in G.
656 Parameters
657 ----------
658 G : NetworkX graph
659 Undirected or directed graph
661 s : node
662 Source node. Optional. Default value: None.
664 t : node
665 Target node. Optional. Default value: None.
667 flow_func : function
668 A function for computing the maximum flow among a pair of nodes.
669 The function has to accept at least three parameters: a Digraph,
670 a source node, and a target node. And return a residual network
671 that follows NetworkX conventions (see :meth:`maximum_flow` for
672 details). If flow_func is None, the default maximum flow function
673 (:meth:`edmonds_karp`) is used. See below for details. The
674 choice of the default function may change from version
675 to version and should not be relied on. Default value: None.
677 cutoff : integer, float, or None (default: None)
678 If specified, the maximum flow algorithm will terminate when the
679 flow value reaches or exceeds the cutoff. This only works for flows
680 that support the cutoff parameter (most do) and is ignored otherwise.
682 Returns
683 -------
684 K : integer
685 Edge connectivity for G, or local edge connectivity if source
686 and target were provided
688 Examples
689 --------
690 >>> # Platonic icosahedral graph is 5-edge-connected
691 >>> G = nx.icosahedral_graph()
692 >>> nx.edge_connectivity(G)
693 5
695 You can use alternative flow algorithms for the underlying
696 maximum flow computation. In dense networks the algorithm
697 :meth:`shortest_augmenting_path` will usually perform better
698 than the default :meth:`edmonds_karp`, which is faster for
699 sparse networks with highly skewed degree distributions.
700 Alternative flow functions have to be explicitly imported
701 from the flow package.
703 >>> from networkx.algorithms.flow import shortest_augmenting_path
704 >>> nx.edge_connectivity(G, flow_func=shortest_augmenting_path)
705 5
707 If you specify a pair of nodes (source and target) as parameters,
708 this function returns the value of local edge connectivity.
710 >>> nx.edge_connectivity(G, 3, 7)
711 5
713 If you need to perform several local computations among different
714 pairs of nodes on the same graph, it is recommended that you reuse
715 the data structures used in the maximum flow computations. See
716 :meth:`local_edge_connectivity` for details.
718 Notes
719 -----
720 This is a flow based implementation of global edge connectivity.
721 For undirected graphs the algorithm works by finding a 'small'
722 dominating set of nodes of G (see algorithm 7 in [1]_ ) and
723 computing local maximum flow (see :meth:`local_edge_connectivity`)
724 between an arbitrary node in the dominating set and the rest of
725 nodes in it. This is an implementation of algorithm 6 in [1]_ .
726 For directed graphs, the algorithm does n calls to the maximum
727 flow function. This is an implementation of algorithm 8 in [1]_ .
729 See also
730 --------
731 :meth:`local_edge_connectivity`
732 :meth:`local_node_connectivity`
733 :meth:`node_connectivity`
734 :meth:`maximum_flow`
735 :meth:`edmonds_karp`
736 :meth:`preflow_push`
737 :meth:`shortest_augmenting_path`
738 :meth:`k_edge_components`
739 :meth:`k_edge_subgraphs`
741 References
742 ----------
743 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
744 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
746 """
747 if (s is not None and t is None) or (s is None and t is not None):
748 raise nx.NetworkXError("Both source and target must be specified.")
750 # Local edge connectivity
751 if s is not None and t is not None:
752 if s not in G:
753 raise nx.NetworkXError(f"node {s} not in graph")
754 if t not in G:
755 raise nx.NetworkXError(f"node {t} not in graph")
756 return local_edge_connectivity(G, s, t, flow_func=flow_func, cutoff=cutoff)
758 # Global edge connectivity
759 # reuse auxiliary digraph and residual network
760 H = build_auxiliary_edge_connectivity(G)
761 R = build_residual_network(H, "capacity")
762 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
764 if G.is_directed():
765 # Algorithm 8 in [1]
766 if not nx.is_weakly_connected(G):
767 return 0
769 # initial value for \lambda is minimum degree
770 L = min(d for n, d in G.degree())
771 nodes = list(G)
772 n = len(nodes)
774 if cutoff is not None:
775 L = min(cutoff, L)
777 for i in range(n):
778 kwargs["cutoff"] = L
779 try:
780 L = min(L, local_edge_connectivity(G, nodes[i], nodes[i + 1], **kwargs))
781 except IndexError: # last node!
782 L = min(L, local_edge_connectivity(G, nodes[i], nodes[0], **kwargs))
783 return L
784 else: # undirected
785 # Algorithm 6 in [1]
786 if not nx.is_connected(G):
787 return 0
789 # initial value for \lambda is minimum degree
790 L = min(d for n, d in G.degree())
792 if cutoff is not None:
793 L = min(cutoff, L)
795 # A dominating set is \lambda-covering
796 # We need a dominating set with at least two nodes
797 for node in G:
798 D = nx.dominating_set(G, start_with=node)
799 v = D.pop()
800 if D:
801 break
802 else:
803 # in complete graphs the dominating sets will always be of one node
804 # thus we return min degree
805 return L
807 for w in D:
808 kwargs["cutoff"] = L
809 L = min(L, local_edge_connectivity(G, v, w, **kwargs))
811 return L