local_edge_connectivity#

local_edge_connectivity(G, s, t, flow_func=None, auxiliary=None, residual=None, cutoff=None)[source]#

返回图G中节点s和t的局部边连通性。

两个节点s和t的局部边连通性是指必须移除的最少边数，以使它们断开连接。

这是一个基于流的边连通性实现。我们计算辅助有向图上的最大流，该有向图由原始网络构建（详见下文）。这等于局部边连通性，因为最大s-t流的值等于最小s-t割的容量（Ford和Fulkerson定理）[Rddfd752c6267-1]_。

Parameters:

GNetworkX图: 无向或有向图
s节点: 源节点
t节点: 目标节点
flow_func函数: 用于计算一对节点间最大流的函数。该函数至少需要接受三个参数：一个有向图、一个源节点和一个目标节点。并返回一个遵循NetworkX惯例的残余网络（详见：meth:maximum_flow ）。如果flow_func为None，则使用默认的最大流函数（：meth:edmonds_karp ）。详见下文。默认函数的选取可能会随版本变化，不应依赖。默认值：None。
auxiliaryNetworkX有向图: 用于计算基于流的边连通性的辅助有向图。如果提供，将重用而不是重新创建。默认值：None。
residualNetworkX有向图: 用于计算最大流的残余网络。如果提供，将重用而不是重新创建。默认值：None。
cutoff整数、浮点数或None（默认：None）: 如果指定，当流值达到或超过截止值时，最大流算法将终止。这仅适用于支持截止参数的流（大多数都支持），否则将被忽略。

Returns:

K整数: 节点s和t的局部边连通性。

See also

edge_connectivity()
local_node_connectivity()
node_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

Notes

这是一个基于流的边连通性实现。我们默认使用：meth:edmonds_karp 算法在由原始输入图构建的辅助有向图上计算最大流：

如果输入图是无向的，我们将每条边（ u , v ）替换为两个互反弧（ u , v ）和（ v , u ），然后将每个弧的属性’capacity’设置为1。如果输入图是有向的，我们只需添加’capacity’属性。这是[Rddfd752c6267-1]_中算法1的实现。

辅助网络中的最大流等于局部边连通性，因为最大s-t流的值等于最小s-t割的容量（Ford和Fulkerson定理）。

References

[1]

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

Examples

此函数未在NetworkX基础命名空间中导入，因此您需要从连通性包中显式导入它：

>>> from networkx.algorithms.connectivity import local_edge_connectivity

在此示例中，我们使用柏拉图二十面体图，其边连通性为5。

>>> G = nx.icosahedral_graph()
>>> local_edge_connectivity(G, 0, 6)
5

如果您需要在同一个图中计算多对节点的局部连通性，建议您重用NetworkX在计算中使用的数据结构：边连通性的辅助有向图和底层最大流计算的残余网络。

示例：如何重用数据结构计算柏拉图二十面体图中所有节点对的局部边连通性。

>>> import itertools
>>> # 您还需要从连通性包中显式导入构建辅助有向图的函数
>>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
>>> H = build_auxiliary_edge_connectivity(G)
>>> # 以及从流包中导入构建残余网络的函数
>>> from networkx.algorithms.flow import build_residual_network
>>> # 注意辅助有向图有一个名为capacity的边属性
>>> R = build_residual_network(H, "capacity")
>>> result = dict.fromkeys(G, dict())
>>> # 通过将它们作为参数传递来重用辅助有向图和残余网络
>>> for u, v in itertools.combinations(G, 2):
...     k = local_edge_connectivity(G, u, v, auxiliary=H, residual=R)
...     result[u][v] = k
>>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
True

您还可以使用替代流算法来计算边连通性。例如，在密集网络中，算法：meth:shortest_augmenting_path 通常比默认的：meth:edmonds_karp 表现更好，后者在具有高度偏斜度分布的稀疏网络中速度更快。替代流函数需要从流包中显式导入。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> local_edge_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
5