Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / sparsifiers.py @ 5cef0f13

History | View | Annotate | Download (9.84 KB)

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
from __future__ import division
7
import math
8
import networkx as nx
9
from networkx.utils import not_implemented_for, py_random_state
10

    
11
__all__ = ['spanner']
12

    
13

    
14
@py_random_state(3)
15
@not_implemented_for('directed')
16
@not_implemented_for('multigraph')
17
def spanner(G, stretch, weight=None, seed=None):
18
    """Returns a spanner of the given graph with the given stretch.
19

20
    A spanner of a graph G = (V, E) with stretch t is a subgraph
21
    H = (V, E_S) such that E_S is a subset of E and the distance between
22
    any pair of nodes in H is at most t times the distance between the
23
    nodes in G.
24

25
    Parameters
26
    ----------
27
    G : NetworkX graph
28
        An undirected simple graph.
29

30
    stretch : float
31
        The stretch of the spanner.
32

33
    weight : object
34
        The edge attribute to use as distance.
35

36
    seed : integer, random_state, or None (default)
37
        Indicator of random number generation state.
38
        See :ref:`Randomness<randomness>`.
39

40
    Returns
41
    -------
42
    NetworkX graph
43
        A spanner of the given graph with the given stretch.
44

45
    Raises
46
    ------
47
    ValueError
48
        If a stretch less than 1 is given.
49

50
    Notes
51
    -----
52
    This function implements the spanner algorithm by Baswana and Sen,
53
    see [1].
54

55
    This algorithm is a randomized las vegas algorithm: The expected
56
    running time is O(km) where k = (stretch + 1) // 2 and m is the
57
    number of edges in G. The returned graph is always a spanner of the
58
    given graph with the specified stretch. For weighted graphs the
59
    number of edges in the spanner is O(k * n^(1 + 1 / k)) where k is
60
    defined as above and n is the number of nodes in G. For unweighted
61
    graphs the number of edges is O(n^(1 + 1 / k) + kn).
62

63
    References
64
    ----------
65
    [1] S. Baswana, S. Sen. A Simple and Linear Time Randomized
66
    Algorithm for Computing Sparse Spanners in Weighted Graphs.
67
    Random Struct. Algorithms 30(4): 532-563 (2007).
68
    """
69
    if stretch < 1:
70
        raise ValueError('stretch must be at least 1')
71

    
72
    k = (stretch + 1) // 2
73

    
74
    # initialize spanner H with empty edge set
75
    H = nx.empty_graph()
76
    H.add_nodes_from(G.nodes)
77

    
78
    # phase 1: forming the clusters
79
    # the residual graph has V' from the paper as its node set
80
    # and E' from the paper as its edge set
81
    residual_graph = _setup_residual_graph(G, weight)
82
    # clustering is a dictionary that maps nodes in a cluster to the
83
    # cluster center
84
    clustering = {v: v for v in G.nodes}
85
    sample_prob = math.pow(G.number_of_nodes(), - 1 / k)
86
    size_limit = 2 * math.pow(G.number_of_nodes(), 1 + 1 / k)
87

    
88
    i = 0
89
    while i < k - 1:
90
        # step 1: sample centers
91
        sampled_centers = set()
92
        for center in set(clustering.values()):
93
            if seed.random() < sample_prob:
94
                sampled_centers.add(center)
95

    
96
        # combined loop for steps 2 and 3
97
        edges_to_add = set()
98
        edges_to_remove = set()
99
        new_clustering = {}
100
        for v in residual_graph.nodes:
101
            if clustering[v] in sampled_centers:
102
                continue
103

    
104
            # step 2: find neighboring (sampled) clusters and
105
            # lightest edges to them
106
            lightest_edge_neighbor, lightest_edge_weight =\
107
                _lightest_edge_dicts(residual_graph, clustering, v)
108
            neighboring_sampled_centers =\
109
                set(lightest_edge_weight.keys()) & sampled_centers
110

    
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))
119

    
120
            else:  # there is a neighboring sampled center
121
                closest_center = min(neighboring_sampled_centers,
122
                                     key=lightest_edge_weight.get)
123
                closest_center_weight = lightest_edge_weight[closest_center]
124
                closest_center_neighbor =\
125
                    lightest_edge_neighbor[closest_center]
126

    
127
                edges_to_add.add((v, closest_center_neighbor))
128
                new_clustering[v] = closest_center
129

    
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))
136

    
137
                # remove edges to centers with edge weight less than
138
                # closest_center_weight
139
                for neighbor in residual_graph.adj[v]:
140
                    neighbor_cluster = clustering[neighbor]
141
                    neighbor_weight = lightest_edge_weight[neighbor_cluster]
142
                    if neighbor_cluster == closest_center or neighbor_weight < closest_center_weight:
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, _ =\
181
            _lightest_edge_dicts(residual_graph, clustering, v)
182
        for neighbor in lightest_edge_neighbor.values():
183
            _add_edge_to_spanner(H, residual_graph, v, neighbor, weight)
184

    
185
    return H
186

    
187

    
188
def _setup_residual_graph(G, weight):
189
    """Setup residual graph as a copy of G with unique edges weights.
190

191
    The node set of the residual graph corresponds to the set V' from
192
    the Baswana-Sen paper and the edge set corresponds to the set E'
193
    from the paper.
194

195
    This function associates distinct weights to the edges of the
196
    residual graph (even for unweighted input graphs), as required by
197
    the algorithm.
198

199
    Parameters
200
    ----------
201
    G : NetworkX graph
202
        An undirected simple graph.
203

204
    weight : object
205
        The edge attribute to use as distance.
206

207
    Returns
208
    -------
209
    NetworkX graph
210
        The residual graph used for the Baswana-Sen algorithm.
211
    """
212
    residual_graph = G.copy()
213

    
214
    # establish unique edge weights, even for unweighted graphs
215
    for u, v in G.edges():
216
        if not weight:
217
            residual_graph[u][v]['weight'] = (id(u), id(v))
218
        else:
219
            residual_graph[u][v]['weight'] = (G[u][v][weight], id(u), id(v))
220

    
221
    return residual_graph
222

    
223

    
224
def _lightest_edge_dicts(residual_graph, clustering, node):
225
    """Find the lightest edge to each cluster.
226

227
    Searches for the minimum-weight edge to each cluster adjacent to
228
    the given node.
229

230
    Parameters
231
    ----------
232
    residual_graph : NetworkX graph
233
        The residual graph used by the Baswana-Sen algorithm.
234

235
    clustering : dictionary
236
        The current clustering of the nodes.
237

238
    node : node
239
        The node from which the search originates.
240

241
    Returns
242
    -------
243
    lightest_edge_neighbor, lightest_edge_weight : dictionary, dictionary
244
        lightest_edge_neighbor is a dictionary that maps a center C to
245
        a node v in the corresponding cluster such that the edge from
246
        the given node to v is the lightest edge from the given node to
247
        any node in cluster. lightest_edge_weight maps a center C to the
248
        weight of the aforementioned edge.
249

250
    Notes
251
    -----
252
    If a cluster has no node that is adjacent to the given node in the
253
    residual graph then the center of the cluster is not a key in the
254
    returned dictionaries.
255
    """
256
    lightest_edge_neighbor = {}
257
    lightest_edge_weight = {}
258
    for neighbor in residual_graph.adj[node]:
259
        neighbor_center = clustering[neighbor]
260
        weight = residual_graph[node][neighbor]['weight']
261
        if neighbor_center not in lightest_edge_weight or\
262
                weight < lightest_edge_weight[neighbor_center]:
263
            lightest_edge_neighbor[neighbor_center] = neighbor
264
            lightest_edge_weight[neighbor_center] = weight
265
    return lightest_edge_neighbor, lightest_edge_weight
266

    
267

    
268
def _add_edge_to_spanner(H, residual_graph, u, v, weight):
269
    """Add the edge {u, v} to the spanner H and take weight from
270
    the residual graph.
271

272
    Parameters
273
    ----------
274
    H : NetworkX graph
275
        The spanner under construction.
276

277
    residual_graph : NetworkX graph
278
        The residual graph used by the Baswana-Sen algorithm. The weight
279
        for the edge is taken from this graph.
280

281
    u : node
282
        One endpoint of the edge.
283

284
    v : node
285
        The other endpoint of the edge.
286

287
    weight : object
288
        The edge attribute to use as distance.
289
    """
290
    H.add_edge(u, v)
291
    if weight:
292
        H[u][v][weight] = residual_graph[u][v]['weight'][0]