minimum_st_edge_cut

minimum_st_edge_cut(G, s, t, flow_func=None, auxiliary=None, residual=None)

返回最小 (s, t)-割的割集的边。

此函数返回最小基数的边集，如果移除这些边，将破坏 G 中源节点和目标节点之间的所有路径。不考虑边的权重。有关考虑边权重计算最小割的信息，请参见 minimum_cut()。

参数:

GNetworkX 图

s节点

流的源节点。

t节点

流的汇点。

auxiliaryNetworkX 有向图

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

flow_func函数

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

residualNetworkX 有向图

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

返回:

cutset集合

移除后会导致图断开连接的边集。

另请参阅

minimum_cut()

minimum_node_cut()

minimum_edge_cut()

stoer_wagner()

node_connectivity()

edge_connectivity()

maximum_flow()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

示例

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

>>> from networkx.algorithms.connectivity import minimum_st_edge_cut

在此示例中，我们使用柏拉图二十面体图，其边连通性为 5。

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

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

示例：如何在重用数据结构的情况下计算柏拉图二十面体图所有节点对之间的局部边割。

>>> import itertools
>>> # You also have to explicitly import the function for
>>> # building the auxiliary digraph from the connectivity package
>>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
>>> H = build_auxiliary_edge_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")
>>> result = dict.fromkeys(G, dict())
>>> # Reuse the auxiliary digraph and the residual network by passing them
>>> # as parameters
>>> for u, v in itertools.combinations(G, 2):
...     k = len(minimum_st_edge_cut(G, u, v, auxiliary=H, residual=R))
...     result[u][v] = k
>>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
True

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

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> len(minimum_st_edge_cut(G, 0, 6, flow_func=shortest_augmenting_path))
5