boykov_kolmogorov#
- boykov_kolmogorov(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None)[源代码]#
利用Boykov-Kolmogorov算法求单个商品的最大流量。
此函数返回计算最大流量后产生的剩余网络。有关networkx用于定义剩余网络的约定的详细信息,请参阅下面的内容。
该算法具有较差的案例复杂度 \(O(n^2 m |C|)\) 为 \(n\) 节点, \(m\) 边,和 \(|C|\) 最低限度削减的成本 [1]. 此实现使用在 [2] 在许多实际问题上提高了算法的运行时间。
- 参数
- G网络X图表
图的边应该有一个称为‘Capacity’的属性。如果不存在该属性,则认为该边具有无限容量。
- s结点
流的源节点。
- t结点
流的汇聚节点。
- capacity字符串
图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性,则认为该边具有无限容量。默认值:‘Capacity’。
- residual网络X图表
要在其上执行算法的剩余网络。如果没有,则创建新的剩余网络。默认值:无。
- value_only布尔尔
如果为True,则仅计算最大流的值。此参数将被此算法忽略,因为它不适用。
- cutoff整数、浮点数
如果指定,则当流量值达到或超过分界值时,算法将终止。在这种情况下,它可能无法立即确定最低降幅。默认值:无。
- 返回
- R网络X有向图
计算出最大流量后的残差网络。
- 加薪
- NetworkXError
该算法不支持多重图和多重有向图。如果输入图形是这两个类之一的实例,则会引发NetworkXError。
- NetworkXUnbounded
如果图有一条无限容量的路径,则图上的可行流的值在上面是无界的,并且该函数引发一个NetworkXUnbound。
笔记
剩余网络
R
从输入图G
具有与相同的节点G
.R
是包含一对边的有向图(u, v)
和(v, u)
敌我识别(u, v)
不是自循环,并且至少是(u, v)
和(v, u)
存在于G
.对于每个边缘
(u, v)
在里面R
,R[u][v]['capacity']
等于(u, v)
在里面G
如果它存在于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
未指定,可访问到t
仅使用边(u, v)
这样的话R[u][v]['flow'] < R[u][v]['capacity']
诱导最小值s
-t
切。工具书类
- 1
Boykov,Y.和Kolmogorov,V.(2004)。视觉能量最小化的最小截流/最大流算法的实验比较。模式分析与机器智能,IEEE学报,26(9),1124-1137。Https://doi.org/10.1109/TPAMI.2004.60
- 2
弗拉基米尔·科尔莫戈罗夫。基于图的多摄像机重建算法。2003年康奈尔大学计算机科学系博士论文。第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命名空间,因此必须从流包显式导入它们。
>>> 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))