1"""Functions for computing sparsifiers of graphs."""
2import math
3import networkx as nx
4from 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")
12def 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
187def _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
223def _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
269def _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]
294