local_node_connectivity

local_node_connectivity(G, s, t, flow_func=None, auxiliary=None, residual=None, cutoff=None)

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

两个不相邻节点 s 和 t 的局部节点连通性是必须移除的最少节点数（以及它们的关联边），以便将它们断开连接。

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

参数：

GNetworkX 图

无向图

s节点

源节点

t节点

目标节点

flow_func函数

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

auxiliaryNetworkX 有向图

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

residualNetworkX 有向图

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

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

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

返回：

K整数

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

另请参阅

local_edge_connectivity()

node_connectivity()

minimum_node_cut()

maximum_flow()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

说明

这是基于流的节点连通性实现。我们通过对从原始输入图构建的辅助有向图计算最大流来获得结果，默认情况下使用 edmonds_karp() 算法（参见：maximum_flow()）

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

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

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

参考文献

[1]

Kammer, Frank 和 Hanjo Taubig. Graph Connectivity. 见 Brandes 和 Erlebach，《网络分析：方法论基础》，Lecture Notes in Computer Science，第 3418 卷，Springer-Verlag，2005 年。http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf

示例

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

>>> from networkx.algorithms.connectivity import local_node_connectivity

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

>>> G = nx.icosahedral_graph()
>>> local_node_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_node_connectivity
>>> H = build_auxiliary_node_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_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

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

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