maximum_flow_value#

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

查找最大单商品流的值。

参数:
flowGNetworkX图

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

_s节点

流的源节点。

_t节点

流的汇节点。

capacity字符串

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

flow_func函数

用于计算容量图中一对节点之间的最大流的函数。该函数必须至少接受三个参数：Graph或Digraph、源节点和目标节点。并返回遵循NetworkX约定的剩余网络（参见Notes）。如果flow_func为None，则使用默认的最大流函数（preflow_push()）。替代算法见下文。默认函数的选择可能因版本而异，不应依赖于此。默认值：None。

kwargs传递给计算最大流的函数的任何其他关键字参数。

计算最大流。

返回值:
flow_value整数，浮点数

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

引发:
NetworkXError

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

NetworkXUnbounded

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

另请参阅

maximum_flow()
minimum_cut()
minimum_cut_value()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

注意

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

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

对于R中的每条边(u, v)，如果G中存在边(u, v)，则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_value仅计算最大流的值

>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value
3.0

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

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> flow_value == nx.maximum_flow_value(
...     G, "x", "y", flow_func=shortest_augmenting_path
... )
True
在此页面上