local_node_connectivity#

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

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

对于两个非相邻节点s和t，局部节点连通性是指必须移除的最少节点数（及其关联边）以断开它们之间的连接。

这是一个基于流的节点连通性实现。我们通过从原始输入图构建辅助有向图来计算最大流（详见下文）。

Parameters:
GNetworkX图

无向图

s节点

源节点

t节点

目标节点

flow_func函数

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

auxiliaryNetworkX有向图

用于计算基于流的节点连通性的辅助有向图。它必须有一个名为mapping的图属性，包含一个将G中的节点名称映射到辅助有向图中的字典。如果提供，将重用而不是重新创建。默认值：None。

residualNetworkX有向图

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

cutoff整数、浮点数或None（默认：None）

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

Returns:
K整数

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

See also

local_edge_connectivity()
node_connectivity()
minimum_node_cut()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

Notes

这是一个基于流的节点连通性实现。我们默认使用：meth： edmonds_karp 算法（详见：meth： maximum_flow ）在从原始输入图构建的辅助有向图上计算最大流：

对于具有 n 个节点和 m 条边的无向图G，我们通过将每个原始节点 v 替换为两个节点 v_A 、 v_B 并在H中通过一条（内部）弧连接，从而得到具有 2n 个节点和 2m+n 条弧的有向图H。然后对于G中的每条边（ u ， v ），我们在H中添加两条弧（ u_B ， v_A ）和（ v_B ， u_A ）。最后，我们将H中每条弧的属性capacity设置为1 [1]。

对于具有 n 个节点和 m 条弧的有向图G，我们通过将每个原始节点 v 替换为两个节点 v_A 、 v_B 并在H中通过一条（内部）弧（ v_A ， v_B ）连接，从而得到具有 2n 个节点和 m+n 条弧的有向图H。然后对于G中的每条弧（ u ， v ），我们在H中添加一条弧（ u_B ， v_A ）。最后，我们将H中每条弧的属性capacity设置为1。

这等于局部节点连通性，因为最大s-t流的值等于最小s-t割的容量。

References

[1]

Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and Erlebach, ‘Network Analysis: Methodological Foundations’, Lecture Notes in Computer Science, Volume 3418, Springer-Verlag, 2005. http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf

Examples

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

>>> from networkx.algorithms.connectivity import local_node_connectivity

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

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

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

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

>>> import itertools
>>> # 您还需要从连通性包中显式导入构建辅助有向图的函数
>>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity
>>> H = build_auxiliary_node_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_node_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_node_connectivity(G, 0, 6, flow_func=shortest_augmenting_path)
5
On this page