Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/sparsifiers.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # Copyright (C) 2018
2 # Robert Gmyr <robert@gmyr.net>
3 # All rights reserved.
4 # BSD license.
5 """Functions for computing sparsifiers of graphs."""
6 import math
7 import networkx as nx
8 from networkx.utils import not_implemented_for, py_random_state
9
10 __all__ = ['spanner']
11
12
13 @py_random_state(3)
14 @not_implemented_for('directed')
15 @not_implemented_for('multigraph')
16 def spanner(G, stretch, weight=None, seed=None):
17 """Returns a spanner of the given graph with the given stretch.
18
19 A spanner of a graph G = (V, E) with stretch t is a subgraph
20 H = (V, E_S) such that E_S is a subset of E and the distance between
21 any pair of nodes in H is at most t times the distance between the
22 nodes in G.
23
24 Parameters
25 ----------
26 G : NetworkX graph
27 An undirected simple graph.
28
29 stretch : float
30 The stretch of the spanner.
31
32 weight : object
33 The edge attribute to use as distance.
34
35 seed : integer, random_state, or None (default)
36 Indicator of random number generation state.
37 See :ref:`Randomness<randomness>`.
38
39 Returns
40 -------
41 NetworkX graph
42 A spanner of the given graph with the given stretch.
43
44 Raises
45 ------
46 ValueError
47 If a stretch less than 1 is given.
48
49 Notes
50 -----
51 This function implements the spanner algorithm by Baswana and Sen,
52 see [1].
53
54 This algorithm is a randomized las vegas algorithm: The expected
55 running time is O(km) where k = (stretch + 1) // 2 and m is the
56 number of edges in G. The returned graph is always a spanner of the
57 given graph with the specified stretch. For weighted graphs the
58 number of edges in the spanner is O(k * n^(1 + 1 / k)) where k is
59 defined as above and n is the number of nodes in G. For unweighted
60 graphs the number of edges is O(n^(1 + 1 / k) + kn).
61
62 References
63 ----------
64 [1] S. Baswana, S. Sen. A Simple and Linear Time Randomized
65 Algorithm for Computing Sparse Spanners in Weighted Graphs.
66 Random Struct. Algorithms 30(4): 532-563 (2007).
67 """
68 if stretch < 1:
69 raise ValueError('stretch must be at least 1')
70
71 k = (stretch + 1) // 2
72
73 # initialize spanner H with empty edge set
74 H = nx.empty_graph()
75 H.add_nodes_from(G.nodes)
76
77 # phase 1: forming the clusters
78 # the residual graph has V' from the paper as its node set
79 # and E' from the paper as its edge set
80 residual_graph = _setup_residual_graph(G, weight)
81 # clustering is a dictionary that maps nodes in a cluster to the
82 # cluster center
83 clustering = {v: v for v in G.nodes}
84 sample_prob = math.pow(G.number_of_nodes(), - 1 / k)
85 size_limit = 2 * math.pow(G.number_of_nodes(), 1 + 1 / k)
86
87 i = 0
88 while i < k - 1:
89 # step 1: sample centers
90 sampled_centers = set()
91 for center in set(clustering.values()):
92 if seed.random() < sample_prob:
93 sampled_centers.add(center)
94
95 # combined loop for steps 2 and 3
96 edges_to_add = set()
97 edges_to_remove = set()
98 new_clustering = {}
99 for v in residual_graph.nodes:
100 if clustering[v] in sampled_centers:
101 continue
102
103 # step 2: find neighboring (sampled) clusters and
104 # lightest edges to them
105 lightest_edge_neighbor, lightest_edge_weight =\
106 _lightest_edge_dicts(residual_graph, clustering, v)
107 neighboring_sampled_centers =\
108 set(lightest_edge_weight.keys()) & sampled_centers
109
110 # step 3: add edges to spanner
111 if not neighboring_sampled_centers:
112 # connect to each neighboring center via lightest edge
113 for neighbor in lightest_edge_neighbor.values():
114 edges_to_add.add((v, neighbor))
115 # remove all incident edges
116 for neighbor in residual_graph.adj[v]:
117 edges_to_remove.add((v, neighbor))
118
119 else: # there is a neighboring sampled center
120 closest_center = min(neighboring_sampled_centers,
121 key=lightest_edge_weight.get)
122 closest_center_weight = lightest_edge_weight[closest_center]
123 closest_center_neighbor =\
124 lightest_edge_neighbor[closest_center]
125
126 edges_to_add.add((v, closest_center_neighbor))
127 new_clustering[v] = closest_center
128
129 # connect to centers with edge weight less than
130 # closest_center_weight
131 for center, edge_weight in lightest_edge_weight.items():
132 if edge_weight < closest_center_weight:
133 neighbor = lightest_edge_neighbor[center]
134 edges_to_add.add((v, neighbor))
135
136 # remove edges to centers with edge weight less than
137 # closest_center_weight
138 for neighbor in residual_graph.adj[v]:
139 neighbor_cluster = clustering[neighbor]
140 neighbor_weight = lightest_edge_weight[neighbor_cluster]
141 if neighbor_cluster == closest_center or neighbor_weight < closest_center_weight:
142 edges_to_remove.add((v, neighbor))
143
144 # check whether iteration added too many edges to spanner,
145 # if so repeat
146 if len(edges_to_add) > size_limit:
147 # an iteration is repeated O(1) times on expectation
148 continue
149
150 # iteration succeeded
151 i = i + 1
152
153 # actually add edges to spanner
154 for u, v in edges_to_add:
155 _add_edge_to_spanner(H, residual_graph, u, v, weight)
156
157 # actually delete edges from residual graph
158 residual_graph.remove_edges_from(edges_to_remove)
159
160 # copy old clustering data to new_clustering
161 for node, center in clustering.items():
162 if center in sampled_centers:
163 new_clustering[node] = center
164 clustering = new_clustering
165
166 # step 4: remove intra-cluster edges
167 for u in residual_graph.nodes:
168 for v in list(residual_graph.adj[u]):
169 if clustering[u] == clustering[v]:
170 residual_graph.remove_edge(u, v)
171
172 # update residual graph node set
173 for v in list(residual_graph.nodes):
174 if v not in clustering:
175 residual_graph.remove_node(v)
176
177 # phase 2: vertex-cluster joining
178 for v in residual_graph.nodes:
179 lightest_edge_neighbor, _ =\
180 _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 neighbor_center not in lightest_edge_weight or\
261 weight < lightest_edge_weight[neighbor_center]:
262 lightest_edge_neighbor[neighbor_center] = neighbor
263 lightest_edge_weight[neighbor_center] = weight
264 return lightest_edge_neighbor, lightest_edge_weight
265
266
267 def _add_edge_to_spanner(H, residual_graph, u, v, weight):
268 """Add the edge {u, v} to the spanner H and take weight from
269 the residual graph.
270
271 Parameters
272 ----------
273 H : NetworkX graph
274 The spanner under construction.
275
276 residual_graph : NetworkX graph
277 The residual graph used by the Baswana-Sen algorithm. The weight
278 for the edge is taken from this graph.
279
280 u : node
281 One endpoint of the edge.
282
283 v : node
284 The other endpoint of the edge.
285
286 weight : object
287 The edge attribute to use as distance.
288 """
289 H.add_edge(u, v)
290 if weight:
291 H[u][v][weight] = residual_graph[u][v]['weight'][0]