edge_connectivity#

edge_connectivity(G, s=None, t=None, flow_func=None, cutoff=None)[source]#

返回图或有向图 G 的边连通性。

边连通性等于必须移除的最少边数，以断开 G 或使其变得平凡。如果提供了源节点和目标节点，此函数返回局部边连通性：必须移除的最少边数，以断开 G 中从源到目标的所有路径。

Parameters:

GNetworkX 图: 无向或有向图
s节点: 源节点。可选。默认值：None。
t节点: 目标节点。可选。默认值：None。
flow_func函数: 用于计算一对节点间最大流的函数。该函数必须至少接受三个参数：一个有向图、一个源节点和一个目标节点，并返回遵循 NetworkX 约定的残差网络（详见 maximum_flow() ）。如果 flow_func 为 None，则使用默认的最大流函数（edmonds_karp() ）。详见下文。默认函数的选取可能会随版本变化，不应依赖于此。默认值：None。
cutoff整数、浮点数或 None（默认：None）: 如果指定，当流值达到或超过 cutoff 时，最大流算法将终止。这仅适用于支持 cutoff 参数的流（大多数都支持），否则将被忽略。

Returns:

K整数: G 的边连通性，或如果提供了源和目标，则为局部边连通性

See also

local_edge_connectivity()
local_node_connectivity()
node_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()
k_edge_components()
k_edge_subgraphs()

Notes

这是基于流的全球边连通性实现。对于无向图，算法通过找到 G 的一个“小”支配节点集（见 [1] 中的算法 7）并计算支配集中任意节点与其余节点间的局部最大流（见 local_edge_connectivity() ）来工作。这是 [1] 中算法 6 的实现。对于有向图，算法对 n 个节点调用最大流函数。这是 [1] 中算法 8 的实现。

References

[1] (1,2,3)

Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

Examples

>>> # 柏拉图正二十面体图是 5 边连通的
>>> G = nx.icosahedral_graph()
>>> nx.edge_connectivity(G)
5

你可以使用替代的流算法进行底层最大流计算。在密集网络中，算法 shortest_augmenting_path() 通常会比默认的 edmonds_karp() 表现更好，后者在稀疏网络且度分布高度倾斜时更快。替代流函数需要从流包中显式导入。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> nx.edge_connectivity(G, flow_func=shortest_augmenting_path)
5

如果你指定一对节点（源和目标）作为参数，此函数返回局部边连通性的值。

>>> nx.edge_connectivity(G, 3, 7)
5

如果你需要在同一图上对不同节点对进行多次局部计算，建议你重用最大流计算中使用的数据结构。详见 local_edge_connectivity() 。