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