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 定理）[1]。

参数:
GNetworkX 图

无向图或有向图

s节点

源节点

t节点

目标节点

flow_func函数

用于计算一对节点之间最大流的函数。该函数必须至少接受三个参数：一个有向图、一个源节点和一个目标节点。并返回遵循 NetworkX 约定的残差网络（详见 maximum_flow()）。如果 flow_func 为 None，则使用默认的最大流函数 (edmonds_karp())。详见下文。默认函数的选择可能因版本而异，不应依赖于此。默认值：None。

auxiliaryNetworkX 有向图

用于计算基于流的边连通性的辅助有向图。如果提供，则会重复使用而不是重新创建。默认值：None。

residualNetworkX 有向图

用于计算最大流的残差网络。如果提供，则会重复使用而不是重新创建。默认值：None。

cutoff整数、浮点数或 None (默认值: None)

如果指定，当流值达到或超过截止值时，最大流算法将终止。这仅适用于支持 cutoff 参数的流算法（大多数都支持），否则将被忽略。

返回值:
K整数

节点 s 和 t 的局部边连通性。

另请参阅

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

注释

这是边连通性的基于流的实现。默认情况下，我们使用 edmonds_karp() 算法在根据原始输入图构建的辅助有向图上计算最大流

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

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

参考文献

[1] (1,2)

Abdol-Hossein Esfahanian. 连通性算法 (Connectivity Algorithms)。 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

示例

此函数未在 NetworkX 的基础命名空间中导入，因此您必须从 connectivity 包中显式导入它

>>> from networkx.algorithms.connectivity import local_edge_connectivity

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

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

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

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

>>> import itertools
>>> # You also have to explicitly import the function for
>>> # building the auxiliary digraph from the connectivity package
>>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
>>> H = build_auxiliary_edge_connectivity(G)
>>> # And the function for building the residual network from the
>>> # flow package
>>> from networkx.algorithms.flow import build_residual_network
>>> # Note that the auxiliary digraph has an edge attribute named capacity
>>> R = build_residual_network(H, "capacity")
>>> result = dict.fromkeys(G, dict())
>>> # Reuse the auxiliary digraph and the residual network by passing them
>>> # as parameters
>>> 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

您还可以使用其他流算法来计算边连通性。例如，在密集网络中，算法 shortest_augmenting_path() 通常会比默认的 edmonds_karp() 表现更好，后者对于度分布高度倾斜的稀疏网络更快。替代流函数必须从 flow 包中显式导入。

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