Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1from itertools import chain
3import networkx as nx
4from networkx.utils import not_implemented_for, pairwise
6__all__ = ["metric_closure", "steiner_tree"]
9@not_implemented_for("directed")
10@nx._dispatchable(edge_attrs="weight", returns_graph=True)
11def metric_closure(G, weight="weight"):
12 """Return the metric closure of a graph.
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* .
17 Parameters
18 ----------
19 G : NetworkX graph
21 Returns
22 -------
23 NetworkX graph
24 Metric closure of the graph `G`.
26 Notes
27 -----
28 .. deprecated:: 3.6
29 `metric_closure` is deprecated and will be removed in NetworkX 3.8.
30 Use :func:`networkx.all_pairs_shortest_path_length` instead.
32 """
33 import warnings
35 warnings.warn(
36 "metric_closure is deprecated and will be removed in NetworkX 3.8.\n"
37 "Use nx.all_pairs_shortest_path_length instead.",
38 category=DeprecationWarning,
39 stacklevel=5,
40 )
42 M = nx.Graph()
44 Gnodes = set(G)
46 # check for connected graph while processing first node
47 all_paths_iter = nx.all_pairs_dijkstra(G, weight=weight)
48 u, (distance, path) = next(all_paths_iter)
49 if len(G) != len(distance):
50 msg = "G is not a connected graph. metric_closure is not defined."
51 raise nx.NetworkXError(msg)
52 Gnodes.remove(u)
53 for v in Gnodes:
54 M.add_edge(u, v, distance=distance[v], path=path[v])
56 # first node done -- now process the rest
57 for u, (distance, path) in all_paths_iter:
58 Gnodes.remove(u)
59 for v in Gnodes:
60 M.add_edge(u, v, distance=distance[v], path=path[v])
62 return M
65def _mehlhorn_steiner_tree(G, terminal_nodes, weight):
66 distances, paths = nx.multi_source_dijkstra(G, terminal_nodes, weight=weight)
68 d_1 = {}
69 s = {}
70 for v in G.nodes():
71 s[v] = paths[v][0]
72 d_1[(v, s[v])] = distances[v]
74 # G1-G4 names match those from the Mehlhorn 1988 paper.
75 G_1_prime = nx.Graph()
76 # iterate over all edges to complete d1
77 for u, v, data in G.edges(data=True):
78 su, sv = s[u], s[v]
79 weight_here = d_1[(u, su)] + data.get(weight, 1) + d_1[(v, sv)]
80 if not G_1_prime.has_edge(su, sv):
81 G_1_prime.add_edge(su, sv, weight_d1=weight_here)
82 else:
83 new_weight = min(weight_here, G_1_prime[su][sv]["weight_d1"])
84 G_1_prime.add_edge(su, sv, weight_d1=new_weight)
86 G_2 = nx.minimum_spanning_edges(G_1_prime, data=True, weight="weight_d1")
88 G_3 = nx.Graph()
89 for u, v, _ in G_2:
90 path = nx.shortest_path(G, u, v, weight=weight)
91 for n1, n2 in pairwise(path):
92 G_3.add_edge(n1, n2, weight=G[n1][n2].get(weight, 1))
94 G_3_mst = list(nx.minimum_spanning_edges(G_3, data=False, weight=weight))
95 if G.is_multigraph():
96 G_3_mst = (
97 (u, v, min(G[u][v], key=lambda k: G[u][v][k].get(weight, 1)))
98 for u, v in G_3_mst
99 )
100 G_4 = G.edge_subgraph(G_3_mst).copy()
101 _remove_nonterminal_leaves(G_4, terminal_nodes)
102 return G_4.edges()
105def _kou_steiner_tree(G, terminal_nodes, weight):
106 # Compute the metric closure only for terminal nodes
107 # Create a complete graph H from the metric edges
108 H = nx.Graph()
109 unvisited_terminals = set(terminal_nodes)
111 # check for connected graph while processing first node
112 u = unvisited_terminals.pop()
113 distances, paths = nx.single_source_dijkstra(G, source=u, weight=weight)
114 if len(G) != len(distances):
115 msg = "G is not a connected graph."
116 raise nx.NetworkXError(msg)
117 for v in unvisited_terminals:
118 H.add_edge(u, v, distance=distances[v], path=paths[v])
120 # first node done -- now process the rest
121 for u in unvisited_terminals.copy():
122 distances, paths = nx.single_source_dijkstra(G, source=u, weight=weight)
123 unvisited_terminals.remove(u)
124 for v in unvisited_terminals:
125 H.add_edge(u, v, distance=distances[v], path=paths[v])
127 # Use the 'distance' attribute of each edge provided by H.
128 mst_edges = nx.minimum_spanning_edges(H, weight="distance", data=True)
130 # Create an iterator over each edge in each shortest path; repeats are okay
131 mst_all_edges = chain.from_iterable(pairwise(d["path"]) for u, v, d in mst_edges)
132 if G.is_multigraph():
133 mst_all_edges = (
134 (u, v, min(G[u][v], key=lambda k: G[u][v][k].get(weight, 1)))
135 for u, v in mst_all_edges
136 )
138 # Find the MST again, over this new set of edges
139 G_S = G.edge_subgraph(mst_all_edges)
140 T_S = nx.minimum_spanning_edges(G_S, weight="weight", data=False)
142 # Leaf nodes that are not terminal might still remain; remove them here
143 T_H = G.edge_subgraph(T_S).copy()
144 _remove_nonterminal_leaves(T_H, terminal_nodes)
146 return T_H.edges()
149def _remove_nonterminal_leaves(G, terminals):
150 terminal_set = set(terminals)
151 leaves = {n for n in G if len(set(G[n]) - {n}) == 1}
152 nonterminal_leaves = leaves - terminal_set
154 while nonterminal_leaves:
155 # Removing a node may create new non-terminal leaves, so we limit
156 # search for candidate non-terminal nodes to neighbors of current
157 # non-terminal nodes
158 candidate_leaves = set.union(*(set(G[n]) for n in nonterminal_leaves))
159 candidate_leaves -= nonterminal_leaves | terminal_set
160 # Remove current set of non-terminal nodes
161 G.remove_nodes_from(nonterminal_leaves)
162 # Find any new non-terminal nodes from the set of candidates
163 leaves = {n for n in candidate_leaves if len(set(G[n]) - {n}) == 1}
164 nonterminal_leaves = leaves - terminal_set
167ALGORITHMS = {
168 "kou": _kou_steiner_tree,
169 "mehlhorn": _mehlhorn_steiner_tree,
170}
173@not_implemented_for("directed")
174@nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
175def steiner_tree(G, terminal_nodes, weight="weight", method=None):
176 r"""Return an approximation to the minimum Steiner tree of a graph.
178 The minimum Steiner tree of `G` w.r.t a set of `terminal_nodes` (also *S*)
179 is a tree within `G` that spans those nodes and has minimum size (sum of
180 edge weights) among all such trees.
182 The approximation algorithm is specified with the `method` keyword
183 argument. All three available algorithms produce a tree whose weight is
184 within a ``(2 - (2 / l))`` factor of the weight of the optimal Steiner tree,
185 where ``l`` is the minimum number of leaf nodes across all possible Steiner
186 trees.
188 * ``"kou"`` [2]_ (runtime $O(|S| |V|^2)$) computes the minimum spanning tree of
189 the subgraph of the metric closure of *G* induced by the terminal nodes,
190 where the metric closure of *G* is the complete graph in which each edge is
191 weighted by the shortest path distance between the nodes in *G*.
193 * ``"mehlhorn"`` [3]_ (runtime $O(|E|+|V|\log|V|)$) modifies Kou et al.'s
194 algorithm, beginning by finding the closest terminal node for each
195 non-terminal. This data is used to create a complete graph containing only
196 the terminal nodes, in which edge is weighted with the shortest path
197 distance between them. The algorithm then proceeds in the same way as Kou
198 et al..
200 Parameters
201 ----------
202 G : NetworkX graph
204 terminal_nodes : list
205 A list of terminal nodes for which minimum steiner tree is
206 to be found.
208 weight : string (default = 'weight')
209 Use the edge attribute specified by this string as the edge weight.
210 Any edge attribute not present defaults to 1.
212 method : string, optional (default = 'mehlhorn')
213 The algorithm to use to approximate the Steiner tree.
214 Supported options: 'kou', 'mehlhorn'.
215 Other inputs produce a ValueError.
217 Returns
218 -------
219 NetworkX graph
220 Approximation to the minimum steiner tree of `G` induced by
221 `terminal_nodes` .
223 Raises
224 ------
225 NetworkXNotImplemented
226 If `G` is directed.
228 ValueError
229 If the specified `method` is not supported.
231 Notes
232 -----
233 For multigraphs, the edge between two nodes with minimum weight is the
234 edge put into the Steiner tree.
237 References
238 ----------
239 .. [1] Steiner_tree_problem on Wikipedia.
240 https://en.wikipedia.org/wiki/Steiner_tree_problem
241 .. [2] Kou, L., G. Markowsky, and L. Berman. 1981.
242 ‘A Fast Algorithm for Steiner Trees’.
243 Acta Informatica 15 (2): 141–45.
244 https://doi.org/10.1007/BF00288961.
245 .. [3] Mehlhorn, Kurt. 1988.
246 ‘A Faster Approximation Algorithm for the Steiner Problem in Graphs’.
247 Information Processing Letters 27 (3): 125–28.
248 https://doi.org/10.1016/0020-0190(88)90066-X.
249 """
250 if method is None:
251 method = "mehlhorn"
253 try:
254 algo = ALGORITHMS[method]
255 except KeyError as e:
256 raise ValueError(f"{method} is not a valid choice for an algorithm.") from e
258 edges = algo(G, terminal_nodes, weight)
259 # For multigraph we should add the minimal weight edge keys
260 if G.is_multigraph():
261 edges = (
262 (u, v, min(G[u][v], key=lambda k: G[u][v][k][weight])) for u, v in edges
263 )
264 T = G.edge_subgraph(edges)
265 return T