gomory_hu_tree#
- gomory_hu_tree(G, capacity='capacity', flow_func=None)[源代码]#
返回无向图G的Gomory Hu树。
具有容量的无向图的Gomory Hu树是表示图中所有S-T对的最小S-T割集的加权树。
它只需要
n-1
最小切割计算而不是明显的n(n-1)/2
. 树表示所有S-T切割,任意一对节点之间的最小切割值是Gomory Hu树中两个节点之间最短路径中的最小边缘权重。Gomory Hu树还具有这样的特性:在任意两个节点之间的最短路径中,以最小权重移除边,留下两个连接的组件,这些组件形成G中节点的一个划分,定义最小S-T切割。
有关详细信息,请参阅下面的示例部分。
- 参数
- G网络X图表
无向图
- capacity字符串
图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性,则认为该边具有无限容量。默认值:‘Capacity’。
- flow_func功能
函数来执行基础流计算。缺省值
edmonds_karp()
。此函数在具有右尾度分布的稀疏图中执行得更好。shortest_augmenting_path()
将在更密集的图形中执行得更好。
- 返回
- Tree网络X图表
表示输入图的Gomory-Hu树的NetworkX图。
- 加薪
- NetworkXNotImplemented
如果输入图是定向的,则引发。
- NetworkXError
如果输入图为空图,则引发。
笔记
该实现基于Gusfield方法 [1] 计算Comory-Hu树,该方法不需要节点收缩,具有与原方法相同的计算复杂度。
工具书类
- 1
gusfield:所有对网络流分析的非常简单的方法。暹罗J计算19(1):143-1551990。
实例
>>> G = nx.karate_club_graph() >>> nx.set_edge_attributes(G, 1, "capacity") >>> T = nx.gomory_hu_tree(G) >>> # The value of the minimum cut between any pair ... # of nodes in G is the minimum edge weight in the ... # shortest path between the two nodes in the ... # Gomory-Hu tree. ... def minimum_edge_weight_in_shortest_path(T, u, v): ... path = nx.shortest_path(T, u, v, weight="weight") ... return min((T[u][v]["weight"], (u, v)) for (u, v) in zip(path, path[1:])) >>> u, v = 0, 33 >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v) >>> cut_value 10 >>> nx.minimum_cut_value(G, u, v) 10 >>> # The Comory-Hu tree also has the property that removing the ... # edge with the minimum weight in the shortest path between ... # any two nodes leaves two connected components that form ... # a partition of the nodes in G that defines the minimum s-t ... # cut. ... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v) >>> T.remove_edge(*edge) >>> U, V = list(nx.connected_components(T)) >>> # Thus U and V form a partition that defines a minimum cut ... # between u and v in G. You can compute the edge cut set, ... # that is, the set of edges that if removed from G will ... # disconnect u from v in G, with this information: ... cutset = set() >>> for x, nbrs in ((n, G[n]) for n in U): ... cutset.update((x, y) for y in nbrs if y in V) >>> # Because we have set the capacities of all edges to 1 ... # the cutset contains ten edges ... len(cutset) 10 >>> # You can use any maximum flow algorithm for the underlying ... # flow computations using the argument flow_func ... from networkx.algorithms import flow >>> T = nx.gomory_hu_tree(G, flow_func=flow.boykov_kolmogorov) >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v) >>> cut_value 10 >>> nx.minimum_cut_value(G, u, v, flow_func=flow.boykov_kolmogorov) 10