all_pairs_node_connectivity

all_pairs_node_connectivity(G, nbunch=None, cutoff=None)

计算所有节点对之间的节点连通性。

两个不同且不相邻节点之间的成对或局部节点连通性是指必须移除的最小节点数（最小分离割集）以使它们断开。根据门格尔定理，这等于节点独立路径数（除了源节点和目标节点外，路径不共享任何节点）。这也是我们在此函数中计算的内容。

此算法是一种快速近似，提供了两个节点之间实际节点独立路径数的严格下限 [1]。它适用于有向图和无向图。

参数:

GNetworkX 图

nbunch: 容器

节点的容器。如果提供，节点连通性将仅在 nbunch 中的节点对之间计算。

cutoff整数

考虑的最大节点连通性。如果为 None，则在每对节点中，使用源节点或目标节点的最小度作为截止值。默认值为 None。

返回:

K字典

字典，以源节点和目标节点为键，存储成对节点连通性

另请参阅

local_node_connectivity

node_connectivity

参考文献

[1]

White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 http://eclectic.ss.uci.edu/~drwhite/working.pdf

示例

一个具有一个附加节点的 3 节点环，环中所有节点之间的连通性为 2，附加节点与其余节点之间的连通性为 1

>>> G = nx.cycle_graph(3)
>>> G.add_edge(2, 3)
>>> import pprint  # for nice dictionary formatting
>>> pprint.pprint(nx.all_pairs_node_connectivity(G))
{0: {1: 2, 2: 2, 3: 1},
 1: {0: 2, 2: 2, 3: 1},
 2: {0: 2, 1: 2, 3: 1},
 3: {0: 1, 1: 1, 2: 1}}
----

其他后端实现了此函数

parallel一个使用 joblib 并行运行图算法的 networkx 后端。在此处查找 nx-parallel 的配置指南：这里

并行实现首先将所有排列（对于有向图）和组合（对于无向图）的列表 (iter_func(nbunch, 2)) 分割成块，然后创建一个生成器，延迟计算每个块的局部节点连通性，最后使用 joblib 的 Parallel 函数在 n_jobs 个 CPU 核上并行执行这些计算。最后，将结果聚合到一个字典中并返回。

附加参数

get_chunksstr, function (默认值 = “chunks”)

一个函数，接受 list(iter_func(nbunch, 2)) 作为输入，并返回一个可迭代对象 pairs_chunks，其中 iter_func 在有向图情况下是 permutations，在无向图情况下是 combinations。默认设置是通过将列表切片成 n_jobs 个块来创建块，每个块的大小至多为 10，且至少为 1。

[源代码]