minimum_cut#
- minimum_cut(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[源代码]#
计算最小(s,t)割的值和节点分区。
使用最大流量最小切割定理,即最小容量切割的容量等于最大流量的流量值。
- 参数
- flowG网络X图表
图的边应该有一个称为‘Capacity’的属性。如果不存在该属性,则认为该边具有无限容量。
- _s结点
流的源节点。
- _t结点
流的汇聚节点。
- capacity字符串
图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性,则认为该边具有无限容量。默认值:‘Capacity’。
- flow_func功能
一种函数,用于计算容量图中两个结点之间的最大流。该函数必须接受至少三个参数:图或有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参阅注释)。如果FLOW_FUNC为NONE,则默认的最大流量函数 (
preflow_push()
)被使用。有关替代算法,请参阅下面的内容。默认功能的选择可能因版本不同而有所不同,不应依赖。默认值:无。- kwargs将任何其他关键字参数传递给
计算最大流量。
- 返回
- cut_value整数、浮点数
最小切割的值。
- partition结点集对
定义最小割集的节点分区。
- 加薪
- NetworkXUnbounded
如果图形具有无限容量的路径,则所有切割都具有无限容量,并且该函数将引发NetworkXError。
参见
笔记
Flow_func参数中使用的函数必须返回遵循networkx约定的剩余网络:
剩余网络
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']
. 可达性t
仅使用边(u, v)
这样的话R[u][v]['flow'] < R[u][v]['capacity']
诱导最小值s
-t
切。特定算法可能会在
R
.函数应只支持可选的布尔参数值_。如果为真,则可以选择在确定最大流量值和最小切割后立即终止算法。
实例
>>> 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)
最小割集计算最小割集和节点分区的值:
>>> cut_value, partition = nx.minimum_cut(G, "x", "y") >>> reachable, non_reachable = partition
这里的“partition”是一个包含两组节点的元组,定义了最小割集。您可以按如下方式计算导致最小切割的边的切割集:
>>> cutset = set() >>> for u, nbrs in ((n, G[n]) for n in reachable): ... cutset.update((u, v) for v in nbrs if v in non_reachable) >>> print(sorted(cutset)) [('c', 'y'), ('x', 'b')] >>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset) True
您还可以使用其他算法通过使用Flow_func参数计算最小切割。
>>> from networkx.algorithms.flow import shortest_augmenting_path >>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0] True