minimum_cut#

minimum_cut(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[source]#

计算最小 (s, t)-割的值和节点划分。

利用最大流最小割定理，即最小容量割的容量等于最大流的流量值。

Parameters:
flowGNetworkX 图

图的边应具有名为 ‘capacity’ 的属性。如果该属性不存在，则认为该边具有无限容量。

_s节点

流的源节点。

_t节点

流的汇节点。

capacity字符串

图 G 的边应具有一个表示边支持流量的 capacity 属性。如果该属性不存在，则认为该边具有无限容量。默认值：’capacity’。

flow_func函数

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

kwargs任何其他关键字参数都将传递给计算最大流的函数。
Returns:
cut_value整数, 浮点数

最小割的值。

partition节点集对

定义最小割的节点划分。

Raises:
NetworkXUnbounded

如果图具有无限容量的路径，所有割都具有无限容量，函数将引发 NetworkXError。

See also

maximum_flow()
maximum_flow_value()
minimum_cut_value()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

Notes

flow_func 参数中使用的函数必须返回遵循 NetworkX 约定的残差网络：

输入图 G 的残差网络 R 具有与 G 相同的节点。R 是一个有向图，如果 (u, v) 不是自环，并且 G 中至少存在 (u, v) 和 (v, u) 之一，则 R 包含一对边 (u, v) 和 (v, u)。

对于 R 中的每条边 (u, v)，R[u][v][‘capacity’] 等于 G 中 (u, v) 的容量（如果存在）或零。如果容量是无限的，R[u][v][‘capacity’] 将具有一个不影响问题解决方案的高任意有限值。该值存储在 R.graph[‘inf’] 中。对于 R 中的每条边 (u, v)，R[u][v][‘flow’] 表示 (u, v) 的流函数，并满足 R[u][v][‘flow’] == -R[v][u][‘flow’]。

定义为流入汇 t 的总流量的流值存储在 R.graph[‘flow_value’] 中。仅使用满足 R[u][v][‘flow’] < R[u][v][‘capacity’] 的边 (u, v) 可达 t 的路径诱导出一个最小 s-t 割。

特定算法可能会在 R 中存储额外数据。

该函数应支持一个可选的布尔参数 value_only。当为 True 时，一旦可以确定最大流值和最小割，算法可以选择性地终止。

Examples

>>> G = nx.DiGraph()
>>> G.add_edge("x", "a", capacity=3.0)
>>> G.add_edge("x", "b", capacity=1.0)
>>> G.add_edge("a", "c", capacity=3.0)
>>> G.add_edge("b", "c", capacity=5.0)
>>> G.add_edge("b", "d", capacity=4.0)
>>> G.add_edge("d", "e", capacity=2.0)
>>> G.add_edge("c", "y", capacity=2.0)
>>> G.add_edge("e", "y", capacity=3.0)

minimum_cut 计算最小割的值和节点划分：

>>> cut_value, partition = nx.minimum_cut(G, "x", "y")
>>> reachable, non_reachable = partition

‘partition’ 是一个包含定义最小割的两个节点集的元组。你可以按如下方式计算诱导最小割的边集：

>>> cutset = set()
>>> for u, nbrs in ((n, G[n]) for n in reachable):
...     cutset.update((u, v) for v in nbrs if v in non_reachable)
>>> print(sorted(cutset))
[('c', 'y'), ('x', 'b')]
>>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset)
True

你还可以使用 flow_func 参数使用替代算法计算最小割。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0]
True
On this page