ioftools / networkxMiCe / networkxmaster / networkx / algorithms / flow / gomory_hu.py @ 5cef0f13
History  View  Annotate  Download (6.25 KB)
1 
# * coding: utf8 *


2 
# gomory_hu.py  function for computing Gomory Hu trees

3 
#

4 
# Copyright 20172019 NetworkX developers.

5 
#

6 
# This file is part of NetworkX.

7 
#

8 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

9 
# information.

10 
#

11 
# Author: Jordi Torrents <jordi.t21@gmail.com>

12 
"""

13 
GomoryHu tree of undirected Graphs.

14 
"""

15 
import networkx as nx 
16 
from networkx.utils import not_implemented_for 
17  
18 
from .edmondskarp import edmonds_karp 
19 
from .utils import build_residual_network 
20  
21 
default_flow_func = edmonds_karp 
22  
23 
__all__ = ['gomory_hu_tree']

24  
25  
26 
@not_implemented_for('directed') 
27 
def gomory_hu_tree(G, capacity='capacity', flow_func=None): 
28 
r"""Returns the GomoryHu tree of an undirected graph G.

29 

30 
A GomoryHu tree of an undirected graph with capacities is a

31 
weighted tree that represents the minimum st cuts for all st

32 
pairs in the graph.

33 

34 
It only requires `n1` minimum cut computations instead of the

35 
obvious `n(n1)/2`. The tree represents all st cuts as the

36 
minimum cut value among any pair of nodes is the minimum edge

37 
weight in the shortest path between the two nodes in the

38 
GomoryHu tree.

39 

40 
The GomoryHu tree also has the property that removing the

41 
edge with the minimum weight in the shortest path between

42 
any two nodes leaves two connected components that form

43 
a partition of the nodes in G that defines the minimum st

44 
cut.

45 

46 
See Examples section below for details.

47 

48 
Parameters

49 


50 
G : NetworkX graph

51 
Undirected graph

52 

53 
capacity : string

54 
Edges of the graph G are expected to have an attribute capacity

55 
that indicates how much flow the edge can support. If this

56 
attribute is not present, the edge is considered to have

57 
infinite capacity. Default value: 'capacity'.

58 

59 
flow_func : function

60 
Function to perform the underlying flow computations. Default value

61 
:func:`edmonds_karp`. This function performs better in sparse graphs

62 
with right tailed degree distributions.

63 
:func:`shortest_augmenting_path` will perform better in denser

64 
graphs.

65 

66 
Returns

67 


68 
Tree : NetworkX graph

69 
A NetworkX graph representing the GomoryHu tree of the input graph.

70 

71 
Raises

72 


73 
NetworkXNotImplemented : Exception

74 
Raised if the input graph is directed.

75 

76 
NetworkXError: Exception

77 
Raised if the input graph is an empty Graph.

78 

79 
Examples

80 


81 
>>> G = nx.karate_club_graph()

82 
>>> nx.set_edge_attributes(G, 1, 'capacity')

83 
>>> T = nx.gomory_hu_tree(G)

84 
>>> # The value of the minimum cut between any pair

85 
... # of nodes in G is the minimum edge weight in the

86 
... # shortest path between the two nodes in the

87 
... # GomoryHu tree.

88 
... def minimum_edge_weight_in_shortest_path(T, u, v):

89 
... path = nx.shortest_path(T, u, v, weight='weight')

90 
... return min((T[u][v]['weight'], (u,v)) for (u, v) in zip(path, path[1:]))

91 
>>> u, v = 0, 33

92 
>>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)

93 
>>> cut_value

94 
10

95 
>>> nx.minimum_cut_value(G, u, v)

96 
10

97 
>>> # The ComoryHu tree also has the property that removing the

98 
... # edge with the minimum weight in the shortest path between

99 
... # any two nodes leaves two connected components that form

100 
... # a partition of the nodes in G that defines the minimum st

101 
... # cut.

102 
... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)

103 
>>> T.remove_edge(*edge)

104 
>>> U, V = list(nx.connected_components(T))

105 
>>> # Thus U and V form a partition that defines a minimum cut

106 
... # between u and v in G. You can compute the edge cut set,

107 
... # that is, the set of edges that if removed from G will

108 
... # disconnect u from v in G, with this information:

109 
... cutset = set()

110 
>>> for x, nbrs in ((n, G[n]) for n in U):

111 
... cutset.update((x, y) for y in nbrs if y in V)

112 
>>> # Because we have set the capacities of all edges to 1

113 
... # the cutset contains ten edges

114 
... len(cutset)

115 
10

116 
>>> # You can use any maximum flow algorithm for the underlying

117 
... # flow computations using the argument flow_func

118 
... from networkx.algorithms import flow

119 
>>> T = nx.gomory_hu_tree(G, flow_func=flow.boykov_kolmogorov)

120 
>>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)

121 
>>> cut_value

122 
10

123 
>>> nx.minimum_cut_value(G, u, v, flow_func=flow.boykov_kolmogorov)

124 
10

125 

126 
Notes

127 


128 
This implementation is based on Gusfield approach [1]_ to compute

129 
ComoryHu trees, which does not require node contractions and has

130 
the same computational complexity than the original method.

131 

132 
See also

133 


134 
:func:`minimum_cut`

135 
:func:`maximum_flow`

136 

137 
References

138 


139 
.. [1] Gusfield D: Very simple methods for all pairs network flow analysis.

140 
SIAM J Comput 19(1):143155, 1990.

141 

142 
"""

143 
if flow_func is None: 
144 
flow_func = default_flow_func 
145  
146 
if len(G) == 0: # empty graph 
147 
msg = 'Empty Graph does not have a GomoryHu tree representation'

148 
raise nx.NetworkXError(msg)

149  
150 
# Start the tree as a star graph with an arbitrary node at the center

151 
tree = {} 
152 
labels = {} 
153 
iter_nodes = iter(G)

154 
root = next(iter_nodes)

155 
for n in iter_nodes: 
156 
tree[n] = root 
157  
158 
# Reuse residual network

159 
R = build_residual_network(G, capacity) 
160  
161 
# For all the leaves in the star graph tree (that is n1 nodes).

162 
for source in tree: 
163 
# Find neighbor in the tree

164 
target = tree[source] 
165 
# compute minimum cut

166 
cut_value, partition = nx.minimum_cut(G, source, target, 
167 
capacity=capacity, flow_func=flow_func, 
168 
residual=R) 
169 
labels[(source, target)] = cut_value 
170 
# Update the tree

171 
# Source will always be in partition[0] and target in partition[1]

172 
for node in partition[0]: 
173 
if node != source and node in tree and tree[node] == target: 
174 
tree[node] = source 
175 
labels[(node, source)] = labels.get((node, target), cut_value) 
176 
# Build the tree

177 
T = nx.Graph() 
178 
T.add_nodes_from(G) 
179 
T.add_weighted_edges_from(((u, v, labels[(u, v)]) for u, v in tree.items())) 
180 
return T
