preflow_push#

preflow_push(G, s, t, capacity='capacity', residual=None, global_relabel_freq=1, value_only=False)[source]#

使用最高标签预流推进算法找到最大单商品流。

此函数返回计算最大流后得到的残差网络。有关 NetworkX 定义残差网络的约定详情，请参见下文。

该算法对于 \(n\) 个节点和 \(m\) 条边，运行时间为 \(O(n^2 \sqrt{m})\)。

参数:
GNetworkX 图

图的边预期具有一个名为“capacity”的属性。如果此属性不存在，则认为该边具有无限容量。

s节点

流的源节点。

t节点

流的汇节点。

capacity字符串

图 G 的边预期具有一个 capacity 属性，指示该边可以支持的流量。如果此属性不存在，则认为该边具有无限容量。默认值：“capacity”。

residualNetworkX 图

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

global_relabel_freq整数, 浮点数

应用全局重新标记启发式算法以加速算法的相对频率。如果为 None，则禁用该启发式算法。默认值：1。

value_only布尔值

如果为 False，则计算最大流；否则，计算足以计算最大流值的最大预流。默认值：False。

返回:
RNetworkX DiGraph

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

引发:
NetworkXError

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

NetworkXUnbounded

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

另请参阅

maximum_flow()
minimum_cut()
edmonds_karp()
shortest_augmenting_path()

注意

输入图 G 生成的残差网络 R 与 G 具有相同的节点。R 是一个有向图 (DiGraph)，当且仅当 (u, v) 不是自环且 (u, v) 和 (v, u) 中至少有一条存在于 G 中时，R 包含一对边 (u, v) 和 (v, u)。对于 R 中的每个节点 u，R.nodes[u]['excess'] 表示流入 u 的流量与流出 u 的流量之差。

对于 R 中的每条边 (u, v)，R[u][v]['capacity'] 等于 G 中 (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'] 中。仅使用满足 R[u][v]['flow'] < R[u][v]['capacity'] 的边 (u, v) 到达 t 会产生一个最小的 s-t 割。

示例

>>> from networkx.algorithms.flow import preflow_push

实现流算法并输出残差网络的函数（例如此函数）不会导入到 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 = preflow_push(G, "x", "y")
>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value == R.graph["flow_value"]
True
>>> # preflow_push also stores the maximum flow value
>>> # in the excess attribute of the sink node t
>>> flow_value == R.nodes["y"]["excess"]
True
>>> # For some problems, you might only want to compute a
>>> # maximum preflow.
>>> R = preflow_push(G, "x", "y", value_only=True)
>>> flow_value == R.graph["flow_value"]
True
>>> flow_value == R.nodes["y"]["excess"]
True
在本页上