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

如果输入图为空图，则引发。

参见

minimum_cut()

maximum_flow()

笔记

该实现基于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