Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/flow/gomory_hu.py: 24%

1""" 

2Gomory-Hu tree of undirected Graphs. 

3""" 

4import networkx as nx 

5from networkx.utils import not_implemented_for 

6 

7from .edmondskarp import edmonds_karp 

8from .utils import build_residual_network 

9 

10default_flow_func = edmonds_karp 

11 

12__all__ = ["gomory_hu_tree"] 

13 

14 

15@not_implemented_for("directed") 

16@nx._dispatch(edge_attrs={"capacity": float("inf")}) 

17def gomory_hu_tree(G, capacity="capacity", flow_func=None): 

18 r"""Returns the Gomory-Hu tree of an undirected graph G. 

19 

20 A Gomory-Hu tree of an undirected graph with capacities is a 

21 weighted tree that represents the minimum s-t cuts for all s-t 

22 pairs in the graph. 

23 

24 It only requires `n-1` minimum cut computations instead of the 

25 obvious `n(n-1)/2`. The tree represents all s-t cuts as the 

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

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

28 Gomory-Hu tree. 

29 

30 The Gomory-Hu tree also has the property that removing the 

31 edge with the minimum weight in the shortest path between 

32 any two nodes leaves two connected components that form 

33 a partition of the nodes in G that defines the minimum s-t 

34 cut. 

35 

36 See Examples section below for details. 

37 

38 Parameters 

39 ---------- 

40 G : NetworkX graph 

41 Undirected graph 

42 

43 capacity : string 

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

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

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

47 infinite capacity. Default value: 'capacity'. 

48 

49 flow_func : function 

50 Function to perform the underlying flow computations. Default value 

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

52 with right tailed degree distributions. 

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

54 graphs. 

55 

56 Returns 

57 ------- 

58 Tree : NetworkX graph 

59 A NetworkX graph representing the Gomory-Hu tree of the input graph. 

60 

61 Raises 

62 ------ 

63 NetworkXNotImplemented 

64 Raised if the input graph is directed. 

65 

66 NetworkXError 

67 Raised if the input graph is an empty Graph. 

68 

69 Examples 

70 -------- 

71 >>> G = nx.karate_club_graph() 

72 >>> nx.set_edge_attributes(G, 1, "capacity") 

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

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

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

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

77 ... # Gomory-Hu tree. 

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

79 ... path = nx.shortest_path(T, u, v, weight="weight") 

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

81 >>> u, v = 0, 33 

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

83 >>> cut_value 

84 10 

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

86 10 

87 >>> # The Gomory-Hu tree also has the property that removing the 

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

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

90 ... # a partition of the nodes in G that defines the minimum s-t 

91 ... # cut. 

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

93 >>> T.remove_edge(*edge) 

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

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

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

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

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

99 ... cutset = set() 

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

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

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

103 ... # the cutset contains ten edges 

104 ... len(cutset) 

105 10 

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

107 ... # flow computations using the argument flow_func 

108 ... from networkx.algorithms import flow 

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

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

111 >>> cut_value 

112 10 

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

114 10 

115 

116 Notes 

117 ----- 

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

119 Gomory-Hu trees, which does not require node contractions and has 

120 the same computational complexity than the original method. 

121 

122 See also 

123 -------- 

124 :func:`minimum_cut` 

125 :func:`maximum_flow` 

126 

127 References 

128 ---------- 

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

130 SIAM J Comput 19(1):143-155, 1990. 

131 

132 """ 

133 if flow_func is None: 

134 flow_func = default_flow_func 

135 

136 if len(G) == 0: # empty graph 

137 msg = "Empty Graph does not have a Gomory-Hu tree representation" 

138 raise nx.NetworkXError(msg) 

139 

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

141 tree = {} 

142 labels = {} 

143 iter_nodes = iter(G) 

144 root = next(iter_nodes) 

145 for n in iter_nodes: 

146 tree[n] = root 

147 

148 # Reuse residual network 

149 R = build_residual_network(G, capacity) 

150 

151 # For all the leaves in the star graph tree (that is n-1 nodes). 

152 for source in tree: 

153 # Find neighbor in the tree 

154 target = tree[source] 

155 # compute minimum cut 

156 cut_value, partition = nx.minimum_cut( 

157 G, source, target, capacity=capacity, flow_func=flow_func, residual=R 

158 ) 

159 labels[(source, target)] = cut_value 

160 # Update the tree 

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

162 for node in partition[0]: 

163 if node != source and node in tree and tree[node] == target: 

164 tree[node] = source 

165 labels[node, source] = labels.get((node, target), cut_value) 

166 # 

167 if target != root and tree[target] in partition[0]: 

168 labels[source, tree[target]] = labels[target, tree[target]] 

169 labels[target, source] = cut_value 

170 tree[source] = tree[target] 

171 tree[target] = source 

172 

173 # Build the tree 

174 T = nx.Graph() 

175 T.add_nodes_from(G) 

176 T.add_weighted_edges_from(((u, v, labels[u, v]) for u, v in tree.items())) 

177 return T