all_node_cuts#

all_node_cuts(G, k=None, flow_func=None)[源代码]#

返回无向图G的所有最小k割集。

该实现基于卡涅夫斯基的算法 [1] 用于寻找无向图G的所有最小尺寸节点割集;即等于G的节点连通性的基数节点的集合。因此,如果去掉,将把G分解为两个或多个连通分量。

参数
G网络X图表

无向图

k整数

输入图形的节点连通性。如果k为无,则对其进行计算。默认值:无。

flow_func功能

函数来执行基础流计算。默认值Edmonds_Karp。此函数在具有右尾度分布的稀疏图中执行得更好。在密度较大的图形中,最短增强路径的性能会更好。

返回
cuts节点割集生成器

每个节点割集的基数等于输入图的节点连通性。

参见

node_connectivity
edmonds_karp
shortest_augmenting_path

笔记

该实现基于寻找图中所有最小尺寸分离顶点集的顺序算法 [1]. 其主要思想是利用图中最高度节点和所有其他非相邻节点之间的局部最大流计算来计算最小割。一旦找到最小割线,我们就在局部最大流计算的高度节点和目标节点之间添加一条边,以确保不会再次找到该最小割线。

工具书类

1(1,2)

Kanevsky,A.(1993年)。在一个图中查找所有分隔顶点集的最小大小。网络23(6),533--541。http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract

实例

>>> # A two-dimensional grid graph has 4 cutsets of cardinality 2
>>> G = nx.grid_2d_graph(5, 5)
>>> cutsets = list(nx.all_node_cuts(G))
>>> len(cutsets)
4
>>> all(2 == len(cutset) for cutset in cutsets)
True
>>> nx.node_connectivity(G)
2