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 割。

详细信息请参见下面的示例部分。

参数:

GNetworkX 图

无向图

capacity字符串

图 G 的边应具有一个表示边可以支持多少流的 capacity 属性。如果不存在此属性，则认为该边具有无限容量。默认值: 'capacity'。

flow_func函数

执行底层流计算的函数。默认值 edmonds_karp()。此函数在具有右偏度分布的稀疏图上性能更好。shortest_augmenting_path() 在密集图上性能会更好。

返回:

TreeNetworkX 图

表示输入图的 Gomory-Hu 树的 NetworkX 图。

引发:

NetworkXNotImplemented

如果输入图是有向图则引发。

NetworkXError

如果输入图是空图则引发。

另请参阅

minimum_cut()

maximum_flow()

注意

此实现基于 Gusfield 计算 Gomory-Hu 树的方法 [1]，该方法不需要节点收缩，并且与原始方法具有相同的计算复杂度。

参考文献

[1]

Gusfield D: Very simple methods for all pairs network flow analysis. SIAM J Comput 19(1):143-155, 1990.

示例

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