preflow_push#

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

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

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

该算法对于:math:n`个节点和:math:`m`条边的时间复杂度为:math:`O(n^2 sqrt{m})。

Parameters:
GNetworkX图

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

s节点

流的源节点。

t节点

流的汇节点。

capacity字符串

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

residualNetworkX图

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

global_relabel_freq整数, 浮点数

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

value_only布尔值

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

Returns:
RNetworkX有向图

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

Raises:
NetworkXError

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

NetworkXUnbounded

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

See also

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

Notes

从输入图G得到的残余网络R具有与G相同的节点。R是一个有向图，如果(u, v)不是自环，并且G中至少存在(u, v)和(v, u)之一，则R包含一对边(u, v)和(v, u)。对于R中的每个节点u，R.nodes[u][‘excess’]表示流入u和流出u之间的流量差。

对于R中的每条边(u, v)，R[u][v][‘capacity’]等于G中(u, v)的容量（如果存在）或零。如果容量是无限的，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割。

Examples

>>> 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还在汇节点t的excess属性中存储最大流值
>>> flow_value == R.nodes["y"]["excess"]
True
>>> # 对于某些问题，您可能只想计算最大预流
>>> R = preflow_push(G, "x", "y", value_only=True)
>>> flow_value == R.graph["flow_value"]
True
>>> flow_value == R.nodes["y"]["excess"]
True
On this page