preflow_push#

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

使用最高标签预流推送算法查找最大单个商品流。

此函数返回计算最大流量后产生的剩余网络。有关networkx用于定义剩余网络的约定的详细信息，请参阅下面的内容。

该算法的运行时间为 \(O(n^2 \sqrt{{m}})\) 为 \(n\) 节点和 \(m\) 边缘。

参数

G网络X图表: 图的边应该有一个称为‘Capacity’的属性。如果不存在该属性，则认为该边具有无限容量。
s结点: 流的源节点。
t结点: 流的汇聚节点。
capacity字符串: 图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性，则认为该边具有无限容量。默认值：‘Capacity’。
residual网络X图表: 要在其上执行算法的剩余网络。如果没有，则创建新的剩余网络。默认值：无。
global_relabel_freq整数、浮点数: 应用全局重标记启发式算法的相对频率来加速算法。如果为None，则禁用启发式。默认值：1。
value_only布尔尔: 如果为False，则计算最大流量；否则，计算足以计算最大流量值的最大预流。默认值：FALSE。

返回

R网络X有向图: 计算出最大流量后的残差网络。

加薪

NetworkXError: 该算法不支持多重图和多重有向图。如果输入图形是这两个类之一的实例，则会引发NetworkXError。
NetworkXUnbounded: 如果图有一条无限容量的路径，则图上的可行流的值在上面是无界的，并且该函数引发一个NetworkXUnbound。

参见

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

笔记

剩余网络 R 从输入图 G 具有与相同的节点 G . R 是包含一对边的有向图 (u, v) 和 (v, u) 敌我识别 (u, v) 不是自循环，并且至少是 (u, v) 和 (v, u) 存在于 G . 对于每个节点 u 在里面 R ， R.nodes[u]['excess'] 表示流入之间的差异 u 流出 u .

对于每个边缘 (u, v) 在里面 R ， R[u][v]['capacity'] 等于 (u, v) 在里面 G 如果它存在于 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'] . 可达性 t 仅使用边 (u, v) 这样的话 R[u][v]['flow'] < R[u][v]['capacity'] 诱导最小值 s -t 切。

实例

>>> from networkx.algorithms.flow import preflow_push

实现流算法并输出剩余网络的函数（如本函数）不会导入到基本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 = 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