minimum_st_node_cut#

minimum_st_node_cut(G, s, t, flow_func=None, auxiliary=None, residual=None)[source]#

返回一个最小基数的节点集合，该集合在图中将源节点与目标节点断开。

此函数返回一个最小基数的节点集合，如果移除这些节点，将破坏图中源节点与目标节点之间的所有路径。

Parameters:
GNetworkX 图
s节点

源节点。

t节点

目标节点。

flow_func函数

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

auxiliaryNetworkX 有向图

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

residualNetworkX 有向图

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

Returns:
cutset集合

如果移除这些节点，将破坏图中源节点与目标节点之间的所有路径的节点集合。

See also

minimum_node_cut()
minimum_edge_cut()
stoer_wagner()
node_connectivity()
edge_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

Notes

这是基于流的实现的最小节点割集。该算法基于解决多个最大流计算来确定辅助有向网络上的最小割集容量，该辅助有向网络对应于 G 的最小节点割集。它处理有向图和无向图。此实现基于 [1] 中的算法 11。

References

[1]

Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

Examples

此函数未导入到基础 NetworkX 命名空间中，因此您需要从连通性包中显式导入它：

>>> from networkx.algorithms.connectivity import minimum_st_node_cut

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

>>> G = nx.icosahedral_graph()
>>> len(minimum_st_node_cut(G, 0, 6))
5

如果您需要在同一图中计算多对节点之间的局部 st 割集，建议您重用 NetworkX 在计算中使用的数据结构：节点连通性和节点割集的辅助有向图，以及底层最大流计算的残差网络。

重用数据结构计算局部 st 节点割集的示例：

>>> # 您还需要从连通性包中显式导入构建辅助有向图的函数
>>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity
>>> H = build_auxiliary_node_connectivity(G)
>>> # 以及从流包中导入构建残差网络的函数
>>> from networkx.algorithms.flow import build_residual_network
>>> # 注意辅助有向图有一个名为 capacity 的边属性
>>> R = build_residual_network(H, "capacity")
>>> # 通过传递这些参数来重用辅助有向图和残差网络
>>> len(minimum_st_node_cut(G, 0, 6, auxiliary=H, residual=R))
5

您还可以使用替代流算法来计算最小 st 节点割集。例如，在密集网络中，算法 shortest_augmenting_path() 通常比默认的 edmonds_karp() 表现更好，后者在稀疏网络和高度倾斜的度分布中速度更快。替代流函数需要从流包中显式导入。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> len(minimum_st_node_cut(G, 0, 6, flow_func=shortest_augmenting_path))
5
On this page