local_node_connectivity

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

计算节点s和t的本地节点连接。

两个非相邻节点s和t的本地节点连接是断开连接时必须删除的节点（连同它们的事件边缘）的最小数目。

这是一个基于流的节点连接实现。我们从原始的输入图计算辅助有向图构建上的最大流量（有关详细信息，请参见下文）。

参数

G网络X图表

无向图

s结点

源节点

t结点

目标节点

flow_func功能

一种函数，用于计算一对节点之间的最大流。该函数必须接受至少三个参数：有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参见 maximum_flow() 有关详细信息，请参见)。如果FLOW_FUNC为NONE，则默认的最大流量函数 (edmonds_karp() )被使用。详情见下文。默认功能的选择可能因版本不同而有所不同，不应依赖。默认值：无。

auxiliary网络X有向图

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

residual网络X有向图

计算最大流量的残差网络。如果提供，它将被重复使用，而不是重新创建。默认值：无。

cutoff整数、浮点数

如果指定，当流量值达到或超过分界值时，最大流量算法将终止。这仅适用于支持截止参数的算法： edmonds_karp() 和 shortest_augmenting_path() 。其他算法将忽略此参数。默认值：无。

返回

K整数

节点%s和%t的本地节点连接

参见

local_edge_connectivity()

node_connectivity()

minimum_node_cut()

maximum_flow()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

笔记

这是一个基于流的节点连接实现。默认情况下，我们使用 edmonds_karp() 算法（见： maximum_flow() ）在从原始输入图构建的辅助有向图上：

对于具有以下条件的无向图G n 节点和 m 我们导出一个有向图H的边 2n 节点和 2m+n 通过替换每个原始节点来绘制圆弧 v 具有两个节点 v_A ， v_B 由H中的(内部)圆弧连接，然后针对每条边 (u ， v 在G中，我们添加两个圆弧 (u_B ， v_A )和 (v_B ， u_A )中)。最后，我们为H中的每条弧设置属性Capacity=1 [1] 。

对于有向图G n 节点和 m 弧我们导出一个有向图h 2n 节点和 m+n 通过替换每个原始节点生成圆弧 v 有两个节点 v_A ， v_B 由（内部）弧链接 (v_A ， v_B ）以h为单位，然后为每个弧 (u ， v ）在G中，我们加一个弧 (u_B ， v_A ）在h中，最后我们为h中的每个弧设置属性capacity=1。

这等于本地节点连接，因为最大S-T-Flow的值等于最小S-T-Cut的容量。

工具书类

1

Kammer、Frank和Hanjo Taubig。图形连接。在Brandes和Erlebach的《网络分析：方法基础》，计算机科学讲座笔记，第3418卷，Springer Verlag，2005年。http://www.informatik.uni-augsburg.de/thi/personen/kammer/graph_connectivity.pdf

实例

此函数未导入到基本NetworkX命名空间中，因此必须从连接包中显式导入：

>>> 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() 对于高度倾斜度分布的稀疏网络，这一点更快。必须从流包显式导入可选流函数。

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