minimum_cut_value#

minimum_cut_value(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[源代码]#

计算最小(s,t)切割值。

使用最大流量最小切割定理,即最小容量切割的容量等于最大流量的流量值。

参数
flowG网络X图表

图的边应该有一个称为‘Capacity’的属性。如果不存在该属性,则认为该边具有无限容量。

_s结点

流的源节点。

_t结点

流的汇聚节点。

capacity字符串

图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性,则认为该边具有无限容量。默认值:‘Capacity’。

flow_func功能

一种函数,用于计算容量图中两个结点之间的最大流。该函数必须接受至少三个参数:图或有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参阅注释)。如果FLOW_FUNC为NONE,则默认的最大流量函数 (preflow_push() )被使用。有关替代算法,请参阅下面的内容。默认功能的选择可能因版本不同而有所不同,不应依赖。默认值:无。

kwargs将任何其他关键字参数传递给

计算最大流量。

返回
cut_value整数、浮点数

最小切割的值。

加薪
NetworkXUnbounded

如果图形具有无限容量的路径,则所有切割都具有无限容量,并且该函数将引发NetworkXError。

笔记

Flow_func参数中使用的函数必须返回遵循networkx约定的剩余网络:

剩余网络 R 从输入图 G 具有与相同的节点 G . R 是包含一对边的有向图 (u, v)(v, u) 敌我识别 (u, v) 不是自循环,并且至少是 (u, v)(v, u) 存在于 G .

对于每个边缘 (u, v) 在里面 RR[u][v]['capacity'] 等于 (u, v) 在里面 G 如果它存在于 G 否则为零。如果容量是无限的, R[u][v]['capacity'] 将具有不影响问题解的高任意有限值。此值存储在 R.graph['inf'] . 对于每个边缘 (u, v) 在里面 RR[u][v]['flow'] 表示的流函数 (u, v) 满足 R[u][v]['flow'] == -R[v][u]['flow'] .

流量值,定义为流入的总流量 t 水槽储存在 R.graph['flow_value'] . 可达性 t 仅使用边 (u, v) 这样的话 R[u][v]['flow'] < R[u][v]['capacity'] 诱导最小值 s -t 切。

特定算法可能会在 R .

函数应只支持可选的布尔参数值_。如果为真,则可以选择在确定最大流量值和最小切割后立即终止算法。

实例

>>> 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)

最小切割值仅计算最小切割值:

>>> cut_value = nx.minimum_cut_value(G, "x", "y")
>>> cut_value
3.0

您还可以使用其他算法通过使用Flow_func参数计算最小切割。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> cut_value == nx.minimum_cut_value(
...     G, "x", "y", flow_func=shortest_augmenting_path
... )
True