boykov_kolmogorov#

boykov_kolmogorov(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None)[source]#

使用Boykov-Kolmogorov算法找到最大单商品流。

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

该算法在最坏情况下的复杂度为:math:O(n^2 m |C|)，其中:math:`n`是节点数，:math:`m`是边数，:math:`|C|`是最小割的代价[1]。此实现使用了[2]中定义的标记启发式方法，该方法在许多实际问题中提高了运行时间。

Parameters:
GNetworkX图

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

s节点

流的源节点。

t节点

流的汇节点。

capacity字符串

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

residualNetworkX图

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

value_only布尔值

如果为True，则仅计算最大流的值。此参数将被此算法忽略，因为它不适用。

cutoff整数, 浮点数

如果指定，当流值达到或超过cutoff时，算法将终止。在这种情况下，可能无法立即确定最小割。默认值：None。

Returns:
RNetworkX有向图

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

Raises:
NetworkXError

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

NetworkXUnbounded

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

See also

maximum_flow()
minimum_cut()
preflow_push()
shortest_augmenting_path()

Notes

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

对于:samp:R 中的每条边:samp:(u, v) ，R[u][v]['capacity'] 等于:samp:G 中:samp:(u, v) 的容量（如果存在）或零。如果容量是无限的，R[u][v]['capacity'] 将具有一个不影响问题解决方案的高任意有限值。该值存储在:samp:R.graph['inf'] 中。对于:samp:R 中的每条边:samp:(u, v) ，R[u][v]['flow'] 表示:samp:(u, v) 的流函数，并满足:samp:R[u][v]['flow'] == -R[v][u]['flow'] 。

流值定义为流入汇:samp:t 的总流量，存储在:samp:R.graph['flow_value'] 中。如果未指定:samp:cutoff ，则仅使用满足:samp:R[u][v]['flow'] < R[u][v]['capacity'] 的边:samp:(u, v) 可达:samp:t ，这将诱导一个最小:samp:s -t 割。

References

[1]

Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(9), 1124-1137. https://doi.org/10.1109/TPAMI.2004.60

[2]

Vladimir Kolmogorov. Graph-based Algorithms for Multi-camera Reconstruction Problem. PhD thesis, Cornell University, CS Department, 2003. pp. 109-114. https://web.archive.org/web/20170809091249/https://pub.ist.ac.at/~vnk/papers/thesis.pdf

Examples

>>> from networkx.algorithms.flow import boykov_kolmogorov

实现流算法并输出残余网络的函数（如本函数）不会导入到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 = boykov_kolmogorov(G, "x", "y")
>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value
3.0
>>> flow_value == R.graph["flow_value"]
True

Boykov-Kolmogorov算法的一个优点是，可以根据算法期间使用的搜索树轻松计算定义最小割的节点分区。这些树存储在残余网络的图属性 trees 中。

>>> source_tree, target_tree = R.graph["trees"]
>>> partition = (set(source_tree), set(G) - set(source_tree))

或者等效地：

>>> partition = (set(G) - set(target_tree), set(target_tree))
On this page