Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/sparsifiers.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 """Functions for computing sparsifiers of graphs.""" | |
2 import math | |
3 import networkx as nx | |
4 from networkx.utils import not_implemented_for, py_random_state | |
5 | |
6 __all__ = ["spanner"] | |
7 | |
8 | |
9 @py_random_state(3) | |
10 @not_implemented_for("directed") | |
11 @not_implemented_for("multigraph") | |
12 def spanner(G, stretch, weight=None, seed=None): | |
13 """Returns a spanner of the given graph with the given stretch. | |
14 | |
15 A spanner of a graph G = (V, E) with stretch t is a subgraph | |
16 H = (V, E_S) such that E_S is a subset of E and the distance between | |
17 any pair of nodes in H is at most t times the distance between the | |
18 nodes in G. | |
19 | |
20 Parameters | |
21 ---------- | |
22 G : NetworkX graph | |
23 An undirected simple graph. | |
24 | |
25 stretch : float | |
26 The stretch of the spanner. | |
27 | |
28 weight : object | |
29 The edge attribute to use as distance. | |
30 | |
31 seed : integer, random_state, or None (default) | |
32 Indicator of random number generation state. | |
33 See :ref:`Randomness<randomness>`. | |
34 | |
35 Returns | |
36 ------- | |
37 NetworkX graph | |
38 A spanner of the given graph with the given stretch. | |
39 | |
40 Raises | |
41 ------ | |
42 ValueError | |
43 If a stretch less than 1 is given. | |
44 | |
45 Notes | |
46 ----- | |
47 This function implements the spanner algorithm by Baswana and Sen, | |
48 see [1]. | |
49 | |
50 This algorithm is a randomized las vegas algorithm: The expected | |
51 running time is O(km) where k = (stretch + 1) // 2 and m is the | |
52 number of edges in G. The returned graph is always a spanner of the | |
53 given graph with the specified stretch. For weighted graphs the | |
54 number of edges in the spanner is O(k * n^(1 + 1 / k)) where k is | |
55 defined as above and n is the number of nodes in G. For unweighted | |
56 graphs the number of edges is O(n^(1 + 1 / k) + kn). | |
57 | |
58 References | |
59 ---------- | |
60 [1] S. Baswana, S. Sen. A Simple and Linear Time Randomized | |
61 Algorithm for Computing Sparse Spanners in Weighted Graphs. | |
62 Random Struct. Algorithms 30(4): 532-563 (2007). | |
63 """ | |
64 if stretch < 1: | |
65 raise ValueError("stretch must be at least 1") | |
66 | |
67 k = (stretch + 1) // 2 | |
68 | |
69 # initialize spanner H with empty edge set | |
70 H = nx.empty_graph() | |
71 H.add_nodes_from(G.nodes) | |
72 | |
73 # phase 1: forming the clusters | |
74 # the residual graph has V' from the paper as its node set | |
75 # and E' from the paper as its edge set | |
76 residual_graph = _setup_residual_graph(G, weight) | |
77 # clustering is a dictionary that maps nodes in a cluster to the | |
78 # cluster center | |
79 clustering = {v: v for v in G.nodes} | |
80 sample_prob = math.pow(G.number_of_nodes(), -1 / k) | |
81 size_limit = 2 * math.pow(G.number_of_nodes(), 1 + 1 / k) | |
82 | |
83 i = 0 | |
84 while i < k - 1: | |
85 # step 1: sample centers | |
86 sampled_centers = set() | |
87 for center in set(clustering.values()): | |
88 if seed.random() < sample_prob: | |
89 sampled_centers.add(center) | |
90 | |
91 # combined loop for steps 2 and 3 | |
92 edges_to_add = set() | |
93 edges_to_remove = set() | |
94 new_clustering = {} | |
95 for v in residual_graph.nodes: | |
96 if clustering[v] in sampled_centers: | |
97 continue | |
98 | |
99 # step 2: find neighboring (sampled) clusters and | |
100 # lightest edges to them | |
101 lightest_edge_neighbor, lightest_edge_weight = _lightest_edge_dicts( | |
102 residual_graph, clustering, v | |
103 ) | |
104 neighboring_sampled_centers = ( | |
105 set(lightest_edge_weight.keys()) & sampled_centers | |
106 ) | |
107 | |
108 # step 3: add edges to spanner | |
109 if not neighboring_sampled_centers: | |
110 # connect to each neighboring center via lightest edge | |
111 for neighbor in lightest_edge_neighbor.values(): | |
112 edges_to_add.add((v, neighbor)) | |
113 # remove all incident edges | |
114 for neighbor in residual_graph.adj[v]: | |
115 edges_to_remove.add((v, neighbor)) | |
116 | |
117 else: # there is a neighboring sampled center | |
118 closest_center = min( | |
119 neighboring_sampled_centers, key=lightest_edge_weight.get | |
120 ) | |
121 closest_center_weight = lightest_edge_weight[closest_center] | |
122 closest_center_neighbor = lightest_edge_neighbor[closest_center] | |
123 | |
124 edges_to_add.add((v, closest_center_neighbor)) | |
125 new_clustering[v] = closest_center | |
126 | |
127 # connect to centers with edge weight less than | |
128 # closest_center_weight | |
129 for center, edge_weight in lightest_edge_weight.items(): | |
130 if edge_weight < closest_center_weight: | |
131 neighbor = lightest_edge_neighbor[center] | |
132 edges_to_add.add((v, neighbor)) | |
133 | |
134 # remove edges to centers with edge weight less than | |
135 # closest_center_weight | |
136 for neighbor in residual_graph.adj[v]: | |
137 neighbor_cluster = clustering[neighbor] | |
138 neighbor_weight = lightest_edge_weight[neighbor_cluster] | |
139 if ( | |
140 neighbor_cluster == closest_center | |
141 or neighbor_weight < closest_center_weight | |
142 ): | |
143 edges_to_remove.add((v, neighbor)) | |
144 | |
145 # check whether iteration added too many edges to spanner, | |
146 # if so repeat | |
147 if len(edges_to_add) > size_limit: | |
148 # an iteration is repeated O(1) times on expectation | |
149 continue | |
150 | |
151 # iteration succeeded | |
152 i = i + 1 | |
153 | |
154 # actually add edges to spanner | |
155 for u, v in edges_to_add: | |
156 _add_edge_to_spanner(H, residual_graph, u, v, weight) | |
157 | |
158 # actually delete edges from residual graph | |
159 residual_graph.remove_edges_from(edges_to_remove) | |
160 | |
161 # copy old clustering data to new_clustering | |
162 for node, center in clustering.items(): | |
163 if center in sampled_centers: | |
164 new_clustering[node] = center | |
165 clustering = new_clustering | |
166 | |
167 # step 4: remove intra-cluster edges | |
168 for u in residual_graph.nodes: | |
169 for v in list(residual_graph.adj[u]): | |
170 if clustering[u] == clustering[v]: | |
171 residual_graph.remove_edge(u, v) | |
172 | |
173 # update residual graph node set | |
174 for v in list(residual_graph.nodes): | |
175 if v not in clustering: | |
176 residual_graph.remove_node(v) | |
177 | |
178 # phase 2: vertex-cluster joining | |
179 for v in residual_graph.nodes: | |
180 lightest_edge_neighbor, _ = _lightest_edge_dicts(residual_graph, clustering, v) | |
181 for neighbor in lightest_edge_neighbor.values(): | |
182 _add_edge_to_spanner(H, residual_graph, v, neighbor, weight) | |
183 | |
184 return H | |
185 | |
186 | |
187 def _setup_residual_graph(G, weight): | |
188 """Setup residual graph as a copy of G with unique edges weights. | |
189 | |
190 The node set of the residual graph corresponds to the set V' from | |
191 the Baswana-Sen paper and the edge set corresponds to the set E' | |
192 from the paper. | |
193 | |
194 This function associates distinct weights to the edges of the | |
195 residual graph (even for unweighted input graphs), as required by | |
196 the algorithm. | |
197 | |
198 Parameters | |
199 ---------- | |
200 G : NetworkX graph | |
201 An undirected simple graph. | |
202 | |
203 weight : object | |
204 The edge attribute to use as distance. | |
205 | |
206 Returns | |
207 ------- | |
208 NetworkX graph | |
209 The residual graph used for the Baswana-Sen algorithm. | |
210 """ | |
211 residual_graph = G.copy() | |
212 | |
213 # establish unique edge weights, even for unweighted graphs | |
214 for u, v in G.edges(): | |
215 if not weight: | |
216 residual_graph[u][v]["weight"] = (id(u), id(v)) | |
217 else: | |
218 residual_graph[u][v]["weight"] = (G[u][v][weight], id(u), id(v)) | |
219 | |
220 return residual_graph | |
221 | |
222 | |
223 def _lightest_edge_dicts(residual_graph, clustering, node): | |
224 """Find the lightest edge to each cluster. | |
225 | |
226 Searches for the minimum-weight edge to each cluster adjacent to | |
227 the given node. | |
228 | |
229 Parameters | |
230 ---------- | |
231 residual_graph : NetworkX graph | |
232 The residual graph used by the Baswana-Sen algorithm. | |
233 | |
234 clustering : dictionary | |
235 The current clustering of the nodes. | |
236 | |
237 node : node | |
238 The node from which the search originates. | |
239 | |
240 Returns | |
241 ------- | |
242 lightest_edge_neighbor, lightest_edge_weight : dictionary, dictionary | |
243 lightest_edge_neighbor is a dictionary that maps a center C to | |
244 a node v in the corresponding cluster such that the edge from | |
245 the given node to v is the lightest edge from the given node to | |
246 any node in cluster. lightest_edge_weight maps a center C to the | |
247 weight of the aforementioned edge. | |
248 | |
249 Notes | |
250 ----- | |
251 If a cluster has no node that is adjacent to the given node in the | |
252 residual graph then the center of the cluster is not a key in the | |
253 returned dictionaries. | |
254 """ | |
255 lightest_edge_neighbor = {} | |
256 lightest_edge_weight = {} | |
257 for neighbor in residual_graph.adj[node]: | |
258 neighbor_center = clustering[neighbor] | |
259 weight = residual_graph[node][neighbor]["weight"] | |
260 if ( | |
261 neighbor_center not in lightest_edge_weight | |
262 or weight < lightest_edge_weight[neighbor_center] | |
263 ): | |
264 lightest_edge_neighbor[neighbor_center] = neighbor | |
265 lightest_edge_weight[neighbor_center] = weight | |
266 return lightest_edge_neighbor, lightest_edge_weight | |
267 | |
268 | |
269 def _add_edge_to_spanner(H, residual_graph, u, v, weight): | |
270 """Add the edge {u, v} to the spanner H and take weight from | |
271 the residual graph. | |
272 | |
273 Parameters | |
274 ---------- | |
275 H : NetworkX graph | |
276 The spanner under construction. | |
277 | |
278 residual_graph : NetworkX graph | |
279 The residual graph used by the Baswana-Sen algorithm. The weight | |
280 for the edge is taken from this graph. | |
281 | |
282 u : node | |
283 One endpoint of the edge. | |
284 | |
285 v : node | |
286 The other endpoint of the edge. | |
287 | |
288 weight : object | |
289 The edge attribute to use as distance. | |
290 """ | |
291 H.add_edge(u, v) | |
292 if weight: | |
293 H[u][v][weight] = residual_graph[u][v]["weight"][0] |