minimum_st_edge_cut#

minimum_st_edge_cut(G, s, t, flow_func=None, auxiliary=None, residual=None)[源代码]#

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

此函数返回一组最小基数的边,如果删除这些边,将以g为单位破坏源和目标之间的所有路径。不考虑边权重。见 minimum_cut() 用于计算考虑边缘权重的最小切割。

参数
G网络X图表
s结点

流的源节点。

t结点

流的汇聚节点。

auxiliary网络X有向图

计算基于流的节点连通性的辅助有向图。它必须有一个名为map的图属性,并有一个字典映射G和辅助有向图中的节点名称。如果提供,它将被重复使用,而不是重新创建。默认值:无。

flow_func功能

一种函数,用于计算一对节点之间的最大流。该函数必须接受至少三个参数:有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参见 maximum_flow() 有关详细信息,请参见)。如果FLOW_FUNC为NONE,则默认的最大流量函数 (edmonds_karp() )被使用。看见 node_connectivity() 了解更多细节。默认功能的选择可能因版本不同而有所不同,不应依赖。默认值:无。

residual网络X有向图

计算最大流量的残差网络。如果提供,它将被重复使用,而不是重新创建。默认值:无。

返回
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命名空间中,因此必须从连接包中显式导入:

>>> 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() 对于高度倾斜度分布的稀疏网络,这一点更快。必须从流包显式导入可选流函数。

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