Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.1 KB)

1
# -*- coding: utf-8 -*-
2
"""Swap edges in a graph.
3
"""
4
#    Copyright (C) 2004-2019 by
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    Dan Schult <dschult@colgate.edu>
7
#    Pieter Swart <swart@lanl.gov>
8
#    All rights reserved.
9
#    BSD license.
10
from __future__ import division
11

    
12
import math
13
from networkx.utils import py_random_state
14

    
15
import networkx as nx
16

    
17
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
18
                        'Pieter Swart (swart@lanl.gov)',
19
                        'Dan Schult (dschult@colgate.edu)',
20
                        'Joel Miller (joel.c.miller.research@gmail.com)',
21
                        'Ben Edwards'])
22

    
23
__all__ = ['double_edge_swap',
24
           'connected_double_edge_swap']
25

    
26

    
27
@py_random_state(3)
28
def double_edge_swap(G, nswap=1, max_tries=100, seed=None):
29
    """Swap two edges in the graph while keeping the node degrees fixed.
30

31
    A double-edge swap removes two randomly chosen edges u-v and x-y
32
    and creates the new edges u-x and v-y::
33

34
     u--v            u  v
35
            becomes  |  |
36
     x--y            x  y
37

38
    If either the edge u-x or v-y already exist no swap is performed
39
    and another attempt is made to find a suitable edge pair.
40

41
    Parameters
42
    ----------
43
    G : graph
44
       An undirected graph
45

46
    nswap : integer (optional, default=1)
47
       Number of double-edge swaps to perform
48

49
    max_tries : integer (optional)
50
       Maximum number of attempts to swap edges
51

52
    seed : integer, random_state, or None (default)
53
        Indicator of random number generation state.
54
        See :ref:`Randomness<randomness>`.
55

56
    Returns
57
    -------
58
    G : graph
59
       The graph after double edge swaps.
60

61
    Notes
62
    -----
63
    Does not enforce any connectivity constraints.
64

65
    The graph G is modified in place.
66
    """
67
    if G.is_directed():
68
        raise nx.NetworkXError(
69
            "double_edge_swap() not defined for directed graphs.")
70
    if nswap > max_tries:
71
        raise nx.NetworkXError("Number of swaps > number of tries allowed.")
72
    if len(G) < 4:
73
        raise nx.NetworkXError("Graph has less than four nodes.")
74
    # Instead of choosing uniformly at random from a generated edge list,
75
    # this algorithm chooses nonuniformly from the set of nodes with
76
    # probability weighted by degree.
77
    n = 0
78
    swapcount = 0
79
    keys, degrees = zip(*G.degree())  # keys, degree
80
    cdf = nx.utils.cumulative_distribution(degrees)  # cdf of degree
81
    discrete_sequence = nx.utils.discrete_sequence
82
    while swapcount < nswap:
83
        #        if random.random() < 0.5: continue # trick to avoid periodicities?
84
        # pick two random edges without creating edge list
85
        # choose source node indices from discrete distribution
86
        (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
87
        if ui == xi:
88
            continue  # same source, skip
89
        u = keys[ui]  # convert index to label
90
        x = keys[xi]
91
        # choose target uniformly from neighbors
92
        v = seed.choice(list(G[u]))
93
        y = seed.choice(list(G[x]))
94
        if v == y:
95
            continue  # same target, skip
96
        if (x not in G[u]) and (y not in G[v]):  # don't create parallel edges
97
            G.add_edge(u, x)
98
            G.add_edge(v, y)
99
            G.remove_edge(u, v)
100
            G.remove_edge(x, y)
101
            swapcount += 1
102
        if n >= max_tries:
103
            e = ('Maximum number of swap attempts (%s) exceeded ' % n +
104
                 'before desired swaps achieved (%s).' % nswap)
105
            raise nx.NetworkXAlgorithmError(e)
106
        n += 1
107
    return G
108

    
109

    
110
@py_random_state(3)
111
def connected_double_edge_swap(G, nswap=1, _window_threshold=3, seed=None):
112
    """Attempts the specified number of double-edge swaps in the graph `G`.
113

114
    A double-edge swap removes two randomly chosen edges `(u, v)` and `(x,
115
    y)` and creates the new edges `(u, x)` and `(v, y)`::
116

117
     u--v            u  v
118
            becomes  |  |
119
     x--y            x  y
120

121
    If either `(u, x)` or `(v, y)` already exist, then no swap is performed
122
    so the actual number of swapped edges is always *at most* `nswap`.
123

124
    Parameters
125
    ----------
126
    G : graph
127
       An undirected graph
128

129
    nswap : integer (optional, default=1)
130
       Number of double-edge swaps to perform
131

132
    _window_threshold : integer
133

134
       The window size below which connectedness of the graph will be checked
135
       after each swap.
136

137
       The "window" in this function is a dynamically updated integer that
138
       represents the number of swap attempts to make before checking if the
139
       graph remains connected. It is an optimization used to decrease the
140
       running time of the algorithm in exchange for increased complexity of
141
       implementation.
142

143
       If the window size is below this threshold, then the algorithm checks
144
       after each swap if the graph remains connected by checking if there is a
145
       path joining the two nodes whose edge was just removed. If the window
146
       size is above this threshold, then the algorithm performs do all the
147
       swaps in the window and only then check if the graph is still connected.
148

149
    seed : integer, random_state, or None (default)
150
        Indicator of random number generation state.
151
        See :ref:`Randomness<randomness>`.
152

153
    Returns
154
    -------
155
    int
156
       The number of successful swaps
157

158
    Raises
159
    ------
160

161
    NetworkXError
162

163
       If the input graph is not connected, or if the graph has fewer than four
164
       nodes.
165

166
    Notes
167
    -----
168

169
    The initial graph `G` must be connected, and the resulting graph is
170
    connected. The graph `G` is modified in place.
171

172
    References
173
    ----------
174
    .. [1] C. Gkantsidis and M. Mihail and E. Zegura,
175
           The Markov chain simulation method for generating connected
176
           power law random graphs, 2003.
177
           http://citeseer.ist.psu.edu/gkantsidis03markov.html
178
    """
179
    if not nx.is_connected(G):
180
        raise nx.NetworkXError("Graph not connected")
181
    if len(G) < 4:
182
        raise nx.NetworkXError("Graph has less than four nodes.")
183
    n = 0
184
    swapcount = 0
185
    deg = G.degree()
186
    # Label key for nodes
187
    dk = list(n for n, d in G.degree())
188
    cdf = nx.utils.cumulative_distribution(list(d for n, d in G.degree()))
189
    discrete_sequence = nx.utils.discrete_sequence
190
    window = 1
191
    while n < nswap:
192
        wcount = 0
193
        swapped = []
194
        # If the window is small, we just check each time whether the graph is
195
        # connected by checking if the nodes that were just separated are still
196
        # connected.
197
        if window < _window_threshold:
198
            # This Boolean keeps track of whether there was a failure or not.
199
            fail = False
200
            while wcount < window and n < nswap:
201
                # Pick two random edges without creating the edge list. Choose
202
                # source nodes from the discrete degree distribution.
203
                (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
204
                # If the source nodes are the same, skip this pair.
205
                if ui == xi:
206
                    continue
207
                # Convert an index to a node label.
208
                u = dk[ui]
209
                x = dk[xi]
210
                # Choose targets uniformly from neighbors.
211
                v = seed.choice(list(G.neighbors(u)))
212
                y = seed.choice(list(G.neighbors(x)))
213
                # If the target nodes are the same, skip this pair.
214
                if v == y:
215
                    continue
216
                if x not in G[u] and y not in G[v]:
217
                    G.remove_edge(u, v)
218
                    G.remove_edge(x, y)
219
                    G.add_edge(u, x)
220
                    G.add_edge(v, y)
221
                    swapped.append((u, v, x, y))
222
                    swapcount += 1
223
                n += 1
224
                # If G remains connected...
225
                if nx.has_path(G, u, v):
226
                    wcount += 1
227
                # Otherwise, undo the changes.
228
                else:
229
                    G.add_edge(u, v)
230
                    G.add_edge(x, y)
231
                    G.remove_edge(u, x)
232
                    G.remove_edge(v, y)
233
                    swapcount -= 1
234
                    fail = True
235
            # If one of the swaps failed, reduce the window size.
236
            if fail:
237
                window = int(math.ceil(window / 2))
238
            else:
239
                window += 1
240
        # If the window is large, then there is a good chance that a bunch of
241
        # swaps will work. It's quicker to do all those swaps first and then
242
        # check if the graph remains connected.
243
        else:
244
            while wcount < window and n < nswap:
245
                # Pick two random edges without creating the edge list. Choose
246
                # source nodes from the discrete degree distribution.
247
                (ui, xi) = nx.utils.discrete_sequence(2, cdistribution=cdf)
248
                # If the source nodes are the same, skip this pair.
249
                if ui == xi:
250
                    continue
251
                # Convert an index to a node label.
252
                u = dk[ui]
253
                x = dk[xi]
254
                # Choose targets uniformly from neighbors.
255
                v = seed.choice(list(G.neighbors(u)))
256
                y = seed.choice(list(G.neighbors(x)))
257
                # If the target nodes are the same, skip this pair.
258
                if v == y:
259
                    continue
260
                if x not in G[u] and y not in G[v]:
261
                    G.remove_edge(u, v)
262
                    G.remove_edge(x, y)
263
                    G.add_edge(u, x)
264
                    G.add_edge(v, y)
265
                    swapped.append((u, v, x, y))
266
                    swapcount += 1
267
                n += 1
268
                wcount += 1
269
            # If the graph remains connected, increase the window size.
270
            if nx.is_connected(G):
271
                window += 1
272
            # Otherwise, undo the changes from the previous window and decrease
273
            # the window size.
274
            else:
275
                while swapped:
276
                    (u, v, x, y) = swapped.pop()
277
                    G.add_edge(u, v)
278
                    G.add_edge(x, y)
279
                    G.remove_edge(u, x)
280
                    G.remove_edge(v, y)
281
                    swapcount -= 1
282
                window = int(math.ceil(window / 2))
283
    return swapcount