all_pairs_node_connectivity

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

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

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

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

Parameters:

GNetworkX图

nbunch: 容器

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

cutoff整数

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

Returns:

K字典

按源节点和目标节点键控的成对节点连通性字典

See also

local_node_connectivity

node_connectivity

References

[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

Examples

一个包含3个节点的环加上一个附加节点，环内所有节点之间的连通性为2，附加节点与其他节点之间的连通性为1：

>>> G = nx.cycle_graph(3)
>>> G.add_edge(2, 3)
>>> import pprint  # 用于漂亮的字典格式化
>>> 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}}

---

Additional backends implement this function

parallelParallel backend for NetworkX algorithms

The parallel implementation first divides the a list of all permutation (in case of directed graphs) and combinations (in case of undirected graphs) of nbunch into chunks and then creates a generator to lazily compute the local node connectivities for each chunk, and then employs joblib’s Parallel function to execute these computations in parallel across all available CPU cores. At the end, the results are aggregated into a single dictionary and returned.

Additional parameters:

get_chunksstr, function (default = “chunks”)

A function that takes in list(iter_func(nbunch, 2)) as input and returns an iterable pairs_chunks, here iter_func is permutations in case of directed graphs and combinations in case of undirected graphs. The default is to create chunks by slicing the list into n chunks, where n is the number of CPU cores, such that size of each chunk is atmost 10, and at least 1.

[Source]