Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/steinertree.py: 16%

1from itertools import chain 

2 

3import networkx as nx 

4from networkx.utils import not_implemented_for, pairwise 

5 

6__all__ = ["metric_closure", "steiner_tree"] 

7 

8 

9@not_implemented_for("directed") 

10@nx._dispatch(edge_attrs="weight") 

11def metric_closure(G, weight="weight"): 

12 """Return the metric closure of a graph. 

13 

14 The metric closure of a graph *G* is the complete graph in which each edge 

15 is weighted by the shortest path distance between the nodes in *G* . 

16 

17 Parameters 

18 ---------- 

19 G : NetworkX graph 

20 

21 Returns 

22 ------- 

23 NetworkX graph 

24 Metric closure of the graph `G`. 

25 

26 """ 

27 M = nx.Graph() 

28 

29 Gnodes = set(G) 

30 

31 # check for connected graph while processing first node 

32 all_paths_iter = nx.all_pairs_dijkstra(G, weight=weight) 

33 u, (distance, path) = next(all_paths_iter) 

34 if Gnodes - set(distance): 

35 msg = "G is not a connected graph. metric_closure is not defined." 

36 raise nx.NetworkXError(msg) 

37 Gnodes.remove(u) 

38 for v in Gnodes: 

39 M.add_edge(u, v, distance=distance[v], path=path[v]) 

40 

41 # first node done -- now process the rest 

42 for u, (distance, path) in all_paths_iter: 

43 Gnodes.remove(u) 

44 for v in Gnodes: 

45 M.add_edge(u, v, distance=distance[v], path=path[v]) 

46 

47 return M 

48 

49 

50def _mehlhorn_steiner_tree(G, terminal_nodes, weight): 

51 paths = nx.multi_source_dijkstra_path(G, terminal_nodes) 

52 

53 d_1 = {} 

54 s = {} 

55 for v in G.nodes(): 

56 s[v] = paths[v][0] 

57 d_1[(v, s[v])] = len(paths[v]) - 1 

58 

59 # G1-G4 names match those from the Mehlhorn 1988 paper. 

60 G_1_prime = nx.Graph() 

61 for u, v, data in G.edges(data=True): 

62 su, sv = s[u], s[v] 

63 weight_here = d_1[(u, su)] + data.get(weight, 1) + d_1[(v, sv)] 

64 if not G_1_prime.has_edge(su, sv): 

65 G_1_prime.add_edge(su, sv, weight=weight_here) 

66 else: 

67 new_weight = min(weight_here, G_1_prime[su][sv][weight]) 

68 G_1_prime.add_edge(su, sv, weight=new_weight) 

69 

70 G_2 = nx.minimum_spanning_edges(G_1_prime, data=True) 

71 

72 G_3 = nx.Graph() 

73 for u, v, d in G_2: 

74 path = nx.shortest_path(G, u, v, weight) 

75 for n1, n2 in pairwise(path): 

76 G_3.add_edge(n1, n2) 

77 

78 G_3_mst = list(nx.minimum_spanning_edges(G_3, data=False)) 

79 if G.is_multigraph(): 

80 G_3_mst = ( 

81 (u, v, min(G[u][v], key=lambda k: G[u][v][k][weight])) for u, v in G_3_mst 

82 ) 

83 G_4 = G.edge_subgraph(G_3_mst).copy() 

84 _remove_nonterminal_leaves(G_4, terminal_nodes) 

85 return G_4.edges() 

86 

87 

88def _kou_steiner_tree(G, terminal_nodes, weight): 

89 # H is the subgraph induced by terminal_nodes in the metric closure M of G. 

90 M = metric_closure(G, weight=weight) 

91 H = M.subgraph(terminal_nodes) 

92 

93 # Use the 'distance' attribute of each edge provided by M. 

94 mst_edges = nx.minimum_spanning_edges(H, weight="distance", data=True) 

95 

96 # Create an iterator over each edge in each shortest path; repeats are okay 

97 mst_all_edges = chain.from_iterable(pairwise(d["path"]) for u, v, d in mst_edges) 

98 if G.is_multigraph(): 

99 mst_all_edges = ( 

100 (u, v, min(G[u][v], key=lambda k: G[u][v][k][weight])) 

101 for u, v in mst_all_edges 

102 ) 

103 

104 # Find the MST again, over this new set of edges 

105 G_S = G.edge_subgraph(mst_all_edges) 

106 T_S = nx.minimum_spanning_edges(G_S, weight="weight", data=False) 

107 

108 # Leaf nodes that are not terminal might still remain; remove them here 

109 T_H = G.edge_subgraph(T_S).copy() 

110 _remove_nonterminal_leaves(T_H, terminal_nodes) 

111 

112 return T_H.edges() 

113 

114 

115def _remove_nonterminal_leaves(G, terminals): 

116 terminals_set = set(terminals) 

117 for n in list(G.nodes): 

118 if n not in terminals_set and G.degree(n) == 1: 

119 G.remove_node(n) 

120 

121 

122ALGORITHMS = { 

123 "kou": _kou_steiner_tree, 

124 "mehlhorn": _mehlhorn_steiner_tree, 

125} 

126 

127 

128@not_implemented_for("directed") 

129@nx._dispatch(edge_attrs="weight") 

130def steiner_tree(G, terminal_nodes, weight="weight", method=None): 

131 r"""Return an approximation to the minimum Steiner tree of a graph. 

132 

133 The minimum Steiner tree of `G` w.r.t a set of `terminal_nodes` (also *S*) 

134 is a tree within `G` that spans those nodes and has minimum size (sum of 

135 edge weights) among all such trees. 

136 

137 The approximation algorithm is specified with the `method` keyword 

138 argument. All three available algorithms produce a tree whose weight is 

139 within a ``(2 - (2 / l))`` factor of the weight of the optimal Steiner tree, 

140 where ``l`` is the minimum number of leaf nodes across all possible Steiner 

141 trees. 

142 

143 * ``"kou"`` [2]_ (runtime $O(|S| |V|^2)$) computes the minimum spanning tree of 

144 the subgraph of the metric closure of *G* induced by the terminal nodes, 

145 where the metric closure of *G* is the complete graph in which each edge is 

146 weighted by the shortest path distance between the nodes in *G*. 

147 

148 * ``"mehlhorn"`` [3]_ (runtime $O(|E|+|V|\log|V|)$) modifies Kou et al.'s 

149 algorithm, beginning by finding the closest terminal node for each 

150 non-terminal. This data is used to create a complete graph containing only 

151 the terminal nodes, in which edge is weighted with the shortest path 

152 distance between them. The algorithm then proceeds in the same way as Kou 

153 et al.. 

154 

155 Parameters 

156 ---------- 

157 G : NetworkX graph 

158 

159 terminal_nodes : list 

160 A list of terminal nodes for which minimum steiner tree is 

161 to be found. 

162 

163 weight : string (default = 'weight') 

164 Use the edge attribute specified by this string as the edge weight. 

165 Any edge attribute not present defaults to 1. 

166 

167 method : string, optional (default = 'kou') 

168 The algorithm to use to approximate the Steiner tree. 

169 Supported options: 'kou', 'mehlhorn'. 

170 Other inputs produce a ValueError. 

171 

172 Returns 

173 ------- 

174 NetworkX graph 

175 Approximation to the minimum steiner tree of `G` induced by 

176 `terminal_nodes` . 

177 

178 Notes 

179 ----- 

180 For multigraphs, the edge between two nodes with minimum weight is the 

181 edge put into the Steiner tree. 

182 

183 

184 References 

185 ---------- 

186 .. [1] Steiner_tree_problem on Wikipedia. 

187 https://en.wikipedia.org/wiki/Steiner_tree_problem 

188 .. [2] Kou, L., G. Markowsky, and L. Berman. 1981. 

189 ‘A Fast Algorithm for Steiner Trees’. 

190 Acta Informatica 15 (2): 141–45. 

191 https://doi.org/10.1007/BF00288961. 

192 .. [3] Mehlhorn, Kurt. 1988. 

193 ‘A Faster Approximation Algorithm for the Steiner Problem in Graphs’. 

194 Information Processing Letters 27 (3): 125–28. 

195 https://doi.org/10.1016/0020-0190(88)90066-X. 

196 """ 

197 if method is None: 

198 import warnings 

199 

200 msg = ( 

201 "steiner_tree will change default method from 'kou' to 'mehlhorn' " 

202 "in version 3.2.\nSet the `method` kwarg to remove this warning." 

203 ) 

204 warnings.warn(msg, FutureWarning, stacklevel=4) 

205 method = "kou" 

206 

207 try: 

208 algo = ALGORITHMS[method] 

209 except KeyError as e: 

210 msg = f"{method} is not a valid choice for an algorithm." 

211 raise ValueError(msg) from e 

212 

213 edges = algo(G, terminal_nodes, weight) 

214 # For multigraph we should add the minimal weight edge keys 

215 if G.is_multigraph(): 

216 edges = ( 

217 (u, v, min(G[u][v], key=lambda k: G[u][v][k][weight])) for u, v in edges 

218 ) 

219 T = G.edge_subgraph(edges) 

220 return T