edmonds_karp#
- edmonds_karp(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None)[source]#
使用Edmonds-Karp算法找到最大单商品流。
此函数返回在计算最大流后产生的残余网络。有关NetworkX用于定义残余网络的约定，请参见下文详细信息。
该算法对于:math:
n`个节点和:math:`m`条边的时间复杂度为:math:`O(n m^2)。- Parameters:
- GNetworkX图
图的边应具有名为’capacity’的属性。如果此属性不存在，则认为该边具有无限容量。
- s节点
流的源节点。
- t节点
流的汇节点。
- capacity字符串
图G的边应具有指示边可以支持多少流的容量属性。如果此属性不存在，则认为该边具有无限容量。默认值：’capacity’。
- residualNetworkX图
要在其上执行算法的残余网络。如果为None，则创建一个新的残余网络。默认值：None。
- value_only布尔值
如果为True，则仅计算最大流的值。此参数将被此算法忽略，因为它不适用。
- cutoff整数, 浮点数
如果指定，当流值达到或超过截止值时，算法将终止。在这种情况下，可能无法立即确定最小割。默认值：None。
- Returns:
- RNetworkX有向图
计算最大流后的残余网络。
- Raises:
- NetworkXError
该算法不支持MultiGraph和MultiDiGraph。如果输入图是这两个类之一的实例，则会引发NetworkXError。
- NetworkXUnbounded
如果图具有无限容量的路径，则图上可行流的价值是无界的，函数会引发NetworkXUnbounded。
Notes
从输入图:samp:
G得到的残余网络:samp:R具有与:samp:G相同的节点。R是一个有向图，如果:samp:(u, v)不是自环，并且:samp:(u, v)和:samp:(v, u)中至少有一个存在于:samp:G中，则包含一对边:samp:(u, v)和:samp:(v, u)。对于:samp:
R中的每条边:samp:(u, v)，R[u][v]['capacity']等于:samp:G中:samp:(u, v)的容量（如果存在）或零。如果容量是无限的，R[u][v]['capacity']将具有一个不影响问题解决方案的高任意有限值。此值存储在:samp:R.graph['inf']中。对于:samp:R中的每条边:samp:(u, v)，R[u][v]['flow']表示:samp:(u, v)的流函数，并满足:samp:R[u][v]['flow'] == -R[v][u]['flow']。流值定义为流入汇节点:samp:
t的总流，存储在:samp:R.graph['flow_value']中。如果未指定:samp:cutoff，则仅使用满足:samp:R[u][v]['flow'] < R[u][v]['capacity']的边:samp:(u, v)可达:samp:t，诱导出最小:samp:s-t割。Examples
>>> from networkx.algorithms.flow import edmonds_karp
实现流算法并输出残余网络的函数（如本函数）不会导入到NetworkX基础命名空间中，因此您必须从流包中显式导入它们。
>>> 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) >>> R = edmonds_karp(G, "x", "y") >>> flow_value = nx.maximum_flow_value(G, "x", "y") >>> flow_value 3.0 >>> flow_value == R.graph["flow_value"] True