"""
无向图的Gomory-Hu树。
"""
import networkx as nx
from networkx.utils import not_implemented_for
from .edmondskarp import edmonds_karp
from .utils import build_residual_network
default_flow_func = edmonds_karp
__all__ = ["gomory_hu_tree"]
[docs]
@not_implemented_for("directed")
@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
def gomory_hu_tree(G, capacity="capacity", flow_func=None):
r"""返回无向图 G 的 Gomory-Hu 树。
无向图的 Gomory-Hu 树是一个加权树，表示图中所有 s-t 对的
最小 s-t 割。
它只需要 `n-1` 次最小割计算，而不是明显的 `n(n-1)/2` 次。
该树表示所有 s-t 割，因为任意一对节点之间的最小割值是
Gomory-Hu 树中这两节点之间最短路径上的最小边权重。
Gomory-Hu 树还具有以下性质：删除任意两节点之间最短路径上
的最小权重边后，剩下的两个连通分量形成了 G 中节点的划分，
定义了最小 s-t 割。
详见下面的示例部分。
Parameters
----------
G : NetworkX 图
无向图
capacity : 字符串
图 G 的边应具有一个 capacity 属性，表示该边能支持的流量。
如果该属性不存在，则认为该边具有无限容量。默认值：'capacity'。
flow_func : 函数
执行底层流量计算的函数。默认值：:func:`edmonds_karp` 。
该函数在具有右尾度分布的稀疏图中表现更好。
:func:`shortest_augmenting_path` 在更密集的图中表现更好。
Returns
-------
Tree : NetworkX 图
表示输入图的 Gomory-Hu 树的 NetworkX 图。
Raises
------
NetworkXNotImplemented
如果输入图是有向图，则引发此异常。
NetworkXError
如果输入图是空图，则引发此异常。
Examples
--------
>>> G = nx.karate_club_graph()
>>> nx.set_edge_attributes(G, 1, "capacity")
>>> T = nx.gomory_hu_tree(G)
>>> # G 中任意一对节点之间的最小割值是
... # Gomory-Hu 树中这两节点之间最短路径上的最小边权重。
... 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
>>> # Gomory-Hu 树还具有以下性质：删除任意两节点之间最短路径上
... # 的最小权重边后，剩下的两个连通分量形成了 G 中节点的划分，
... # 定义了最小 s-t 割。
... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
>>> T.remove_edge(*edge)
>>> U, V = list(nx.connected_components(T))
>>> # 因此 U 和 V 形成了一个划分，定义了 G 中 u 和 v 之间的最小割。
... # 你可以用这些信息计算边割集，即，如果从 G 中移除这些边，
... # 将使 u 和 v 在 G 中不连通：
... 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)
>>> # 因为我们设置了所有边的容量为 1
... # 所以割集包含十条边
... len(cutset)
10
>>> # 你可以使用任何最大流算法进行底层流量计算，
... # 使用 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
Notes
-----
此实现基于 Gusfield 的方法 [1]_ 来计算 Gomory-Hu 树，
该方法不需要节点收缩，并且具有与原始方法相同的计算复杂度。
See Also
--------
:func:`minimum_cut`
:func:`maximum_flow`
References
----------
.. [1] Gusfield D: Very simple methods for all pairs network flow analysis.
SIAM J Comput 19(1):143-155, 1990.
"""
if flow_func is None:
flow_func = default_flow_func
if len(G) == 0: # empty graph
msg = "Empty Graph does not have a Gomory-Hu tree representation"
raise nx.NetworkXError(msg)
# Start the tree as a star graph with an arbitrary node at the center
tree = {}
labels = {}
iter_nodes = iter(G)
root = next(iter_nodes)
for n in iter_nodes:
tree[n] = root
# Reuse residual network
R = build_residual_network(G, capacity)
# For all the leaves in the star graph tree (that is n-1 nodes).
for source in tree:
# Find neighbor in the tree
target = tree[source]
# compute minimum cut
cut_value, partition = nx.minimum_cut(
G, source, target, capacity=capacity, flow_func=flow_func, residual=R
)
labels[(source, target)] = cut_value
# Update the tree
# Source will always be in partition[0] and target in partition[1]
for node in partition[0]:
if node != source and node in tree and tree[node] == target:
tree[node] = source
labels[node, source] = labels.get((node, target), cut_value)
#
if target != root and tree[target] in partition[0]:
labels[source, tree[target]] = labels[target, tree[target]]
labels[target, source] = cut_value
tree[source] = tree[target]
tree[target] = source
# Build the tree
T = nx.Graph()
T.add_nodes_from(G)
T.add_weighted_edges_from(((u, v, labels[u, v]) for u, v in tree.items()))
return T
