edmonds_karp

edmonds_karp(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None)

使用 Edmonds-Karp 算法查找最大单商品流。

此函数返回计算最大流后得到的残量网络。关于 NetworkX 定义残量网络的惯例，请参见下文详细信息。

该算法对于 \(n\) 个节点和 \(m\) 条边的时间复杂度为 \(O(n m^2)\)。

参数:

GNetworkX 图

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

s节点

流的源节点。

t节点

流的汇点。

capacity字符串

图 G 的边应具有 'capacity' 属性，该属性表示该边可以支持多少流。如果此属性不存在，则认为该边具有无限容量。默认值：'capacity'。

residualNetworkX 图

算法将在其上执行的残量网络。如果为 None，则创建一个新的残量网络。默认值：None。

value_only布尔值

如果为 True，则只计算最大流的值。该参数将被此算法忽略，因为它不适用。

cutoff整数, 浮点数

如果指定，当流值达到或超过截止值时，算法将终止。在这种情况下，可能无法立即确定最小割。默认值：None。

返回:

RNetworkX DiGraph

计算最大流后的残量网络。

引发:

NetworkXError

该算法不支持 MultiGraph 和 MultiDiGraph。如果输入图是这两个类之一的实例，则会引发 NetworkXError。

NetworkXUnbounded

如果图具有无限容量的路径，则图上可行流的值是无界的，函数会引发 NetworkXUnbounded。

另请参阅

maximum_flow()

minimum_cut()

preflow_push()

shortest_augmenting_path()

备注

输入图 G 生成的残量网络 R 具有与 G 相同的节点。当且仅当 (u, v) 不是自环，并且 G 中至少存在 (u, v) 和 (v, u) 中的一条边时，R 是一个包含一对边 (u, v) 和 (v, u) 的 DiGraph。

对于 R 中的每条边 (u, v)，如果 (u, v) 在 G 中存在，则 R[u][v]['capacity'] 等于其在 G 中的容量，否则为零。如果容量是无限的，则 R[u][v]['capacity'] 将被设置为一个较高的任意有限值，该值不会影响问题的解。此值存储在 R.graph['inf'] 中。对于 (u, v) 在 R 中的每条边，R[u][v]['flow'] 表示 (u, v) 的流函数，并满足 R[u][v]['flow'] == -R[v][u]['flow']。

流值（定义为流入汇点 t 的总流量）存储在 R.graph['flow_value'] 中。如果未指定 cutoff，则仅使用满足 R[u][v]['flow'] < R[u][v]['capacity'] 的边 (u, v) 到 t 的可达性将导出一个最小 s-t 割。

示例

>>> from networkx.algorithms.flow import edmonds_karp

实现流算法并输出残量网络的函数（例如此函数）未导入到 NetworkX 基础命名空间中，因此您必须从 flow 包中显式导入它们。

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