comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/steinertree.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 from itertools import chain
2
3 from networkx.utils import pairwise, not_implemented_for
4 import networkx as nx
5
6 __all__ = ["metric_closure", "steiner_tree"]
7
8
9 @not_implemented_for("directed")
10 def metric_closure(G, weight="weight"):
11 """ Return the metric closure of a graph.
12
13 The metric closure of a graph *G* is the complete graph in which each edge
14 is weighted by the shortest path distance between the nodes in *G* .
15
16 Parameters
17 ----------
18 G : NetworkX graph
19
20 Returns
21 -------
22 NetworkX graph
23 Metric closure of the graph `G`.
24
25 """
26 M = nx.Graph()
27
28 Gnodes = set(G)
29
30 # check for connected graph while processing first node
31 all_paths_iter = nx.all_pairs_dijkstra(G, weight=weight)
32 u, (distance, path) = next(all_paths_iter)
33 if Gnodes - set(distance):
34 msg = "G is not a connected graph. metric_closure is not defined."
35 raise nx.NetworkXError(msg)
36 Gnodes.remove(u)
37 for v in Gnodes:
38 M.add_edge(u, v, distance=distance[v], path=path[v])
39
40 # first node done -- now process the rest
41 for u, (distance, path) in all_paths_iter:
42 Gnodes.remove(u)
43 for v in Gnodes:
44 M.add_edge(u, v, distance=distance[v], path=path[v])
45
46 return M
47
48
49 @not_implemented_for("directed")
50 def steiner_tree(G, terminal_nodes, weight="weight"):
51 """ Return an approximation to the minimum Steiner tree of a graph.
52
53 The minimum Steiner tree of `G` w.r.t a set of `terminal_nodes`
54 is a tree within `G` that spans those nodes and has minimum size
55 (sum of edge weights) among all such trees.
56
57 The minimum Steiner tree can be approximated by computing the minimum
58 spanning tree of the subgraph of the metric closure of *G* induced by the
59 terminal nodes, where the metric closure of *G* is the complete graph in
60 which each edge is weighted by the shortest path distance between the
61 nodes in *G* .
62 This algorithm produces a tree whose weight is within a (2 - (2 / t))
63 factor of the weight of the optimal Steiner tree where *t* is number of
64 terminal nodes.
65
66 Parameters
67 ----------
68 G : NetworkX graph
69
70 terminal_nodes : list
71 A list of terminal nodes for which minimum steiner tree is
72 to be found.
73
74 Returns
75 -------
76 NetworkX graph
77 Approximation to the minimum steiner tree of `G` induced by
78 `terminal_nodes` .
79
80 Notes
81 -----
82 For multigraphs, the edge between two nodes with minimum weight is the
83 edge put into the Steiner tree.
84
85
86 References
87 ----------
88 .. [1] Steiner_tree_problem on Wikipedia.
89 https://en.wikipedia.org/wiki/Steiner_tree_problem
90 """
91 # H is the subgraph induced by terminal_nodes in the metric closure M of G.
92 M = metric_closure(G, weight=weight)
93 H = M.subgraph(terminal_nodes)
94 # Use the 'distance' attribute of each edge provided by M.
95 mst_edges = nx.minimum_spanning_edges(H, weight="distance", data=True)
96 # Create an iterator over each edge in each shortest path; repeats are okay
97 edges = chain.from_iterable(pairwise(d["path"]) for u, v, d in mst_edges)
98 # For multigraph we should add the minimal weight edge keys
99 if G.is_multigraph():
100 edges = (
101 (u, v, min(G[u][v], key=lambda k: G[u][v][k][weight])) for u, v in edges
102 )
103 T = G.edge_subgraph(edges)
104 return T