boykov_kolmogorov#

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

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

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

对于 $n$ 个节点、 $m$ 条边以及最小割 $| C |$ 的成本，该算法的最坏情况复杂度为 $O (n^{2} m | C |)$ [1]。此实现使用了 [2] 中定义的标记启发式算法，这在许多实际问题中提高了其运行时间。

参数:

GNetworkX 图: 图的边期望具有一个名为 ‘capacity’ 的属性。如果此属性不存在，则该边被视为具有无限容量。
s节点: 流的源节点。
t节点: 流的汇点节点。
capacity字符串: 图 G 的边期望有一个 capacity 属性，指示该边可以支持的流大小。如果此属性不存在，则该边被视为具有无限容量。默认值：‘capacity’。
residualNetworkX 图: 算法将在其上执行的剩余网络。如果为 None，则创建一个新的剩余网络。默认值：None。
value_only布尔值: 如果为 True，则仅计算最大流的值。此参数将被该算法忽略，因为它不适用。
cutoff整数, 浮点数: 如果指定，当流值达到或超过此阈值时，算法将终止。在这种情况下，可能无法立即确定最小割。默认值：None。

返回:

RNetworkX 有向图 (DiGraph): 计算最大流后的剩余网络。

抛出:

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

另请参阅

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

注意

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

对于 R 中的每条边 (u, v)，如果 (u, v) 存在于 G 中，则 R[u][v]['capacity'] 等于其在 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'] 中。如果未指定 cutoff，则仅使用满足 R[u][v]['flow'] < R[u][v]['capacity'] 的边到达 t 的可达性将产生一个最小 s-t 割。

参考文献

[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

示例

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