minimum_st_node_cut#

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

返回在图 G 中分离源节点 s 和目标节点 t 的最小节点集。

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

参数:
GNetworkX 图
s节点

源节点。

t节点

目标节点。

flow_func函数

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

auxiliaryNetworkX 有向图 (DiGraph)

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

residualNetworkX 有向图 (DiGraph)

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

返回:
cutset集合

移除后会破坏 G 中源节点和目标节点之间所有路径的节点集合。

参见

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

注意

这是一个基于流的最小节点割实现。该算法基于计算辅助有向网络上的最小割容量，从而确定图 G 的最小节点割。该辅助有向网络对应于 G 的最小节点割。它处理有向图和无向图。该实现基于文献 [1] 中的算法 11。

参考

[1]

Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf (连通性算法)

示例

此函数未导入到 NetworkX 基本命名空间中，因此您必须从 connectivity 包中显式导入它

>>> from networkx.algorithms.connectivity import minimum_st_node_cut

在此示例中，我们使用柏拉图二十面体图 (platonic icosahedral graph)，其节点连通性为 5。

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

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

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

>>> # 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")
>>> # Reuse the auxiliary digraph and the residual network by passing them
>>> # as parameters
>>> len(minimum_st_node_cut(G, 0, 6, auxiliary=H, residual=R))
5

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

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> len(minimum_st_node_cut(G, 0, 6, flow_func=shortest_augmenting_path))
5
在本页