最大流#

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

查找最大单商品流。

参数:

flowGNetworkX 图: 图的边应具有一个名为 ‘capacity’ 的属性。如果该属性不存在，则认为该边具有无限容量。
_s节点: 流的源节点。
_t节点: 流的汇点节点。
capacity字符串: 图 G 的边应具有一个名为 capacity 的属性，表示该边可以支持的最大流量。如果此属性不存在，则认为该边具有无限容量。默认值：'capacity'。
flow_func函数: 一个用于计算容许图中一对节点之间最大流的函数。该函数必须至少接受三个参数：一个 Graph 或 Digraph，一个源节点，和一个目标节点。并返回一个遵循 NetworkX 约定的残差网络（参见 Notes）。如果 flow_func 为 None，则使用默认的最大流函数 (preflow_push())。请参阅下方了解替代算法。默认函数的选择可能会随版本而改变，不应依赖于此。默认值：None。
kwargs任何其他关键字参数都传递给用于计算最大流的函数。: computes the maximum flow.

返回:

flow_value整数, 浮点数: 最大流的值，即从源点流出的净流量。
flow_dict字典: 一个字典，包含流经每条边的流量值。

引发:

NetworkXError: 该算法不支持 MultiGraph 和 MultiDiGraph。如果输入图是这两个类之一的实例，则会引发 NetworkXError。
NetworkXUnbounded: 如果图中存在无限容量的路径，则图上的可行流的值无上限，函数将引发 NetworkXUnbounded。

另请参阅

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

注释

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

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

对于 R 中的每条边 (u, v)，如果 (u, v) 存在于 G 中，则 R[u][v]['capacity'] 等于其在 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 割。

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

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

示例

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