maximum_flow_value#
- maximum_flow_value(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[source]#
查找最大单商品流的值。
- Parameters:
- flowGNetworkX 图
图的边预期具有一个名为 ‘capacity’ 的属性。如果该属性不存在，则认为该边具有无限容量。
- _s节点
流的源节点。
- _t节点
流的汇节点。
- capacity字符串
图 G 的边预期具有一个表示边支持流量的 capacity 属性。如果该属性不存在，则认为该边具有无限容量。默认值：’capacity’。
- flow_func函数
用于计算容量图中一对节点之间最大流的函数。该函数至少需要接受三个参数：图或有向图、源节点和目标节点，并返回遵循 NetworkX 约定的残差网络（见注释）。如果 flow_func 为 None，则使用默认的最大流函数（
preflow_push()）。请参阅下面的替代算法。默认函数的选取可能会随版本变化，不应依赖。默认值：None。- kwargs任何其他关键字参数将传递给计算最大流的函数。
- Returns:
- flow_value整数, 浮点数
最大流的值，即从源节点的净流出量。
- Raises:
- NetworkXError
该算法不支持 MultiGraph 和 MultiDiGraph。如果输入图是这两个类之一的实例，则会引发 NetworkXError。
- NetworkXUnbounded
如果图具有无限容量的路径，则图上可行流的值是无界的，函数会引发 NetworkXUnbounded。
See also
Notes
flow_func 参数中使用的函数必须返回遵循 NetworkX 约定的残差网络：
输入图
G的残差网络R具有与G相同的节点。R是一个有向图，如果(u, v)不是自环，并且(u, v)和(v, u)中至少有一个存在于G中，则包含一对边(u, v)和(v, u)。对于
R中的每条边(u, v)，如果(u, v)在G中存在，则R[u][v]['capacity']等于(u, v)在G中的容量，否则为零。如果容量是无限的，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']中。仅使用边(u, v)到达t，使得R[u][v]['flow'] < R[u][v]['capacity']，诱导出最小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)
maximum_flow_value 仅计算最大流的值：
>>> flow_value = nx.maximum_flow_value(G, "x", "y") >>> flow_value 3.0
您还可以使用 flow_func 参数使用替代算法计算最大流。
>>> from networkx.algorithms.flow import shortest_augmenting_path >>> flow_value == nx.maximum_flow_value( ... G, "x", "y", flow_func=shortest_augmenting_path ... ) True