"""
Gomory-Hu tree of undirected Graphs.
"""
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, preserve_edge_attrs=True
)
def gomory_hu_tree(G, capacity="capacity", flow_func=None):
r"""Returns the Gomory-Hu tree of an undirected graph G.
A Gomory-Hu tree of an undirected graph with capacities is a
weighted tree that represents the minimum s-t cuts for all s-t
pairs in the graph.
It only requires `n-1` minimum cut computations instead of the
obvious `n(n-1)/2`. The tree represents all s-t cuts as the
minimum cut value among any pair of nodes is the minimum edge
weight in the shortest path between the two nodes in the
Gomory-Hu tree.
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.
See Examples section below for details.
Parameters
----------
G : NetworkX graph
Undirected graph
capacity : string or function (default= 'capacity')
If this is a string, then edge capacity will be accessed via the
edge attribute with this key (that is, the capacity of the edge
joining `u` to `v` will be ``G.edges[u, v][capacity]``). If no
such edge attribute exists, the capacity of the edge is assumed to
be infinite.
If this is a function, the capacity of an edge is the value
returned by the function. The function must accept exactly three
positional arguments: the two endpoints of an edge and the
dictionary of edge attributes for that edge. The function must
return a number or None to indicate a hidden edge.
flow_func : function
Function to perform the underlying flow computations. Default value
:func:`edmonds_karp`. This function performs better in sparse graphs
with right tailed degree distributions.
:func:`shortest_augmenting_path` will perform better in denser
graphs.
Returns
-------
Tree : NetworkX graph
A NetworkX graph representing the Gomory-Hu tree of the input graph.
Raises
------
NetworkXNotImplemented
Raised if the input graph is directed.
NetworkXError
Raised if the input graph is an empty Graph.
Examples
--------
>>> 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
Notes
-----
This implementation is based on Gusfield approach [1]_ to compute
Gomory-Hu trees, which does not require node contractions and has
the same computational complexity than the original method.
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
