maximum_flow#

maximum_flow(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[source]#

查找最大单商品流。

Parameters:
flowGNetworkX 图

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

_s节点

流的源节点。

_t节点

流的汇节点。

capacity字符串

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

flow_func函数

用于计算容量图中一对节点之间的最大流的函数。该函数至少需要接受三个参数：一个图或有向图、一个源节点和一个目标节点，并返回一个遵循 NetworkX 约定的残差网络（见注释）。如果 flow_func 为 None，则使用默认的最大流函数（preflow_push() ）。请参阅下面的替代算法。默认函数的选取可能会随版本变化，不应依赖。默认值：None。

kwargs任何其他关键字参数都将传递给计算最大流的函数。
Returns:
flow_value整数, 浮点数

最大流的值，即从源节点流出的净流量。

flow_dict字典

包含每条边流量的字典。

Raises:
NetworkXError

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

NetworkXUnbounded

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

See also

maximum_flow_value()
minimum_cut()
minimum_cut_value()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

Notes

flow_func 参数中使用的函数必须返回一个遵循 NetworkX 约定的残差网络：

从输入图 G 得到的残差网络 R 具有与 G 相同的节点。R 是一个有向图，如果 (u, v) 不是自环，并且 (u, v) 和 (v, u) 中至少有一个存在于 G 中，则 R 包含一对边 (u, v) 和 (v, u) 。

对于 R 中的每条边 (u, v) ，如果 (u, v) 在 G 中存在，则 R[u][v]['capacity'] 等于 (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'] 中。仅使用边 (u, v) 且 R[u][v]['flow'] < R[u][v]['capacity'] 可达 t ，诱导出一个最小 s -t 割。

特定算法可能会在 R 中存储额外数据。

该函数应支持一个可选的布尔参数 value_only。当为 True 时，一旦可以确定最大流值和最小割，它可以选择性地终止算法。

Examples

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

maximum_flow 返回最大流的值和所有流量的字典。

>>> flow_value, flow_dict = nx.maximum_flow(G, "x", "y")
>>> flow_value
3.0
>>> print(flow_dict["x"]["b"])
1.0

您还可以使用 flow_func 参数使用替代算法计算最大流。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> flow_value == nx.maximum_flow(G, "x", "y", flow_func=shortest_augmenting_path)[0]
True
On this page