minimum_edge_cut#

minimum_edge_cut(G, s=None, t=None, flow_func=None)[源代码]#

返回一组与g断开连接的最小基数的边。

如果提供了源节点和目标节点，则此函数返回最小基数的边集，如果移除该边集，则会中断g中源和目标之间的所有路径。否则，它将返回断开g的最小基数的边集。

参数

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

返回

cutset设置: 一组边，如果删除，将断开G。如果提供了源节点和目标节点，则该集合包含的边，如果删除，将破坏源和目标之间的所有路径。

参见

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

笔记

这是一种基于流的最小边切割实现。对于无向图，该算法的工作原理是找到G的一组占支配地位的节点(参见 [1]) 以及计算支配集中任意节点与其中其余节点之间的最大流。这是中算法6的一个实现 [1]. 对于有向图，该算法对最大流函数进行n次调用。如果有向图不是弱连通的，则该函数会引发错误，如果它是弱连通的，则返回空集。它是算法8在 [1].

工具书类

1(1,2,3): Abdol Hossein Esfahanian。连接算法。http://www.cse.msu.edu/~cse835/papers/graph_connectivity_revised.pdf

实例

>>> # Platonic icosahedral graph has edge connectivity 5
>>> G = nx.icosahedral_graph()
>>> len(nx.minimum_edge_cut(G))
5

您可以使用可选的流算法进行底层最大流计算。在稠密网络中，算法 shortest_augmenting_path() 通常会比默认性能更好 edmonds_karp() 对于高度倾斜度分布的稀疏网络来说，这一点更快。必须从流包显式导入可选流函数。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> len(nx.minimum_edge_cut(G, flow_func=shortest_augmenting_path))
5

如果指定一对节点（源和目标）作为参数，则此函数返回本地边缘连接的值。

>>> nx.edge_connectivity(G, 3, 7)
5

如果需要在同一个图上的不同节点对之间执行多个本地计算，建议重用最大流计算中使用的数据结构。见 local_edge_connectivity() 有关详细信息。