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