Mercurial > repos > shellac > sam_consensus_v3
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 |