Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/swap.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
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
11 import math
12 from networkx.utils import py_random_state
13
14 import networkx as nx
15
16 __author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
17 'Pieter Swart (swart@lanl.gov)',
18 'Dan Schult (dschult@colgate.edu)',
19 'Joel Miller (joel.c.miller.research@gmail.com)',
20 'Ben Edwards'])
21
22 __all__ = ['double_edge_swap',
23 'connected_double_edge_swap']
24
25
26 @py_random_state(3)
27 def double_edge_swap(G, nswap=1, max_tries=100, seed=None):
28 """Swap two edges in the graph while keeping the node degrees fixed.
29
30 A double-edge swap removes two randomly chosen edges u-v and x-y
31 and creates the new edges u-x and v-y::
32
33 u--v u v
34 becomes | |
35 x--y x y
36
37 If either the edge u-x or v-y already exist no swap is performed
38 and another attempt is made to find a suitable edge pair.
39
40 Parameters
41 ----------
42 G : graph
43 An undirected graph
44
45 nswap : integer (optional, default=1)
46 Number of double-edge swaps to perform
47
48 max_tries : integer (optional)
49 Maximum number of attempts to swap edges
50
51 seed : integer, random_state, or None (default)
52 Indicator of random number generation state.
53 See :ref:`Randomness<randomness>`.
54
55 Returns
56 -------
57 G : graph
58 The graph after double edge swaps.
59
60 Notes
61 -----
62 Does not enforce any connectivity constraints.
63
64 The graph G is modified in place.
65 """
66 if G.is_directed():
67 raise nx.NetworkXError(
68 "double_edge_swap() not defined for directed graphs.")
69 if nswap > max_tries:
70 raise nx.NetworkXError("Number of swaps > number of tries allowed.")
71 if len(G) < 4:
72 raise nx.NetworkXError("Graph has less than four nodes.")
73 # Instead of choosing uniformly at random from a generated edge list,
74 # this algorithm chooses nonuniformly from the set of nodes with
75 # probability weighted by degree.
76 n = 0
77 swapcount = 0
78 keys, degrees = zip(*G.degree()) # keys, degree
79 cdf = nx.utils.cumulative_distribution(degrees) # cdf of degree
80 discrete_sequence = nx.utils.discrete_sequence
81 while swapcount < nswap:
82 # if random.random() < 0.5: continue # trick to avoid periodicities?
83 # pick two random edges without creating edge list
84 # choose source node indices from discrete distribution
85 (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
86 if ui == xi:
87 continue # same source, skip
88 u = keys[ui] # convert index to label
89 x = keys[xi]
90 # choose target uniformly from neighbors
91 v = seed.choice(list(G[u]))
92 y = seed.choice(list(G[x]))
93 if v == y:
94 continue # same target, skip
95 if (x not in G[u]) and (y not in G[v]): # don't create parallel edges
96 G.add_edge(u, x)
97 G.add_edge(v, y)
98 G.remove_edge(u, v)
99 G.remove_edge(x, y)
100 swapcount += 1
101 if n >= max_tries:
102 e = ('Maximum number of swap attempts (%s) exceeded ' % n +
103 'before desired swaps achieved (%s).' % nswap)
104 raise nx.NetworkXAlgorithmError(e)
105 n += 1
106 return G
107
108
109 @py_random_state(3)
110 def connected_double_edge_swap(G, nswap=1, _window_threshold=3, seed=None):
111 """Attempts the specified number of double-edge swaps in the graph `G`.
112
113 A double-edge swap removes two randomly chosen edges `(u, v)` and `(x,
114 y)` and creates the new edges `(u, x)` and `(v, y)`::
115
116 u--v u v
117 becomes | |
118 x--y x y
119
120 If either `(u, x)` or `(v, y)` already exist, then no swap is performed
121 so the actual number of swapped edges is always *at most* `nswap`.
122
123 Parameters
124 ----------
125 G : graph
126 An undirected graph
127
128 nswap : integer (optional, default=1)
129 Number of double-edge swaps to perform
130
131 _window_threshold : integer
132
133 The window size below which connectedness of the graph will be checked
134 after each swap.
135
136 The "window" in this function is a dynamically updated integer that
137 represents the number of swap attempts to make before checking if the
138 graph remains connected. It is an optimization used to decrease the
139 running time of the algorithm in exchange for increased complexity of
140 implementation.
141
142 If the window size is below this threshold, then the algorithm checks
143 after each swap if the graph remains connected by checking if there is a
144 path joining the two nodes whose edge was just removed. If the window
145 size is above this threshold, then the algorithm performs do all the
146 swaps in the window and only then check if the graph is still connected.
147
148 seed : integer, random_state, or None (default)
149 Indicator of random number generation state.
150 See :ref:`Randomness<randomness>`.
151
152 Returns
153 -------
154 int
155 The number of successful swaps
156
157 Raises
158 ------
159
160 NetworkXError
161
162 If the input graph is not connected, or if the graph has fewer than four
163 nodes.
164
165 Notes
166 -----
167
168 The initial graph `G` must be connected, and the resulting graph is
169 connected. The graph `G` is modified in place.
170
171 References
172 ----------
173 .. [1] C. Gkantsidis and M. Mihail and E. Zegura,
174 The Markov chain simulation method for generating connected
175 power law random graphs, 2003.
176 http://citeseer.ist.psu.edu/gkantsidis03markov.html
177 """
178 if not nx.is_connected(G):
179 raise nx.NetworkXError("Graph not connected")
180 if len(G) < 4:
181 raise nx.NetworkXError("Graph has less than four nodes.")
182 n = 0
183 swapcount = 0
184 deg = G.degree()
185 # Label key for nodes
186 dk = list(n for n, d in G.degree())
187 cdf = nx.utils.cumulative_distribution(list(d for n, d in G.degree()))
188 discrete_sequence = nx.utils.discrete_sequence
189 window = 1
190 while n < nswap:
191 wcount = 0
192 swapped = []
193 # If the window is small, we just check each time whether the graph is
194 # connected by checking if the nodes that were just separated are still
195 # connected.
196 if window < _window_threshold:
197 # This Boolean keeps track of whether there was a failure or not.
198 fail = False
199 while wcount < window and n < nswap:
200 # Pick two random edges without creating the edge list. Choose
201 # source nodes from the discrete degree distribution.
202 (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
203 # If the source nodes are the same, skip this pair.
204 if ui == xi:
205 continue
206 # Convert an index to a node label.
207 u = dk[ui]
208 x = dk[xi]
209 # Choose targets uniformly from neighbors.
210 v = seed.choice(list(G.neighbors(u)))
211 y = seed.choice(list(G.neighbors(x)))
212 # If the target nodes are the same, skip this pair.
213 if v == y:
214 continue
215 if x not in G[u] and y not in G[v]:
216 G.remove_edge(u, v)
217 G.remove_edge(x, y)
218 G.add_edge(u, x)
219 G.add_edge(v, y)
220 swapped.append((u, v, x, y))
221 swapcount += 1
222 n += 1
223 # If G remains connected...
224 if nx.has_path(G, u, v):
225 wcount += 1
226 # Otherwise, undo the changes.
227 else:
228 G.add_edge(u, v)
229 G.add_edge(x, y)
230 G.remove_edge(u, x)
231 G.remove_edge(v, y)
232 swapcount -= 1
233 fail = True
234 # If one of the swaps failed, reduce the window size.
235 if fail:
236 window = int(math.ceil(window / 2))
237 else:
238 window += 1
239 # If the window is large, then there is a good chance that a bunch of
240 # swaps will work. It's quicker to do all those swaps first and then
241 # check if the graph remains connected.
242 else:
243 while wcount < window and n < nswap:
244 # Pick two random edges without creating the edge list. Choose
245 # source nodes from the discrete degree distribution.
246 (ui, xi) = nx.utils.discrete_sequence(2, cdistribution=cdf)
247 # If the source nodes are the same, skip this pair.
248 if ui == xi:
249 continue
250 # Convert an index to a node label.
251 u = dk[ui]
252 x = dk[xi]
253 # Choose targets uniformly from neighbors.
254 v = seed.choice(list(G.neighbors(u)))
255 y = seed.choice(list(G.neighbors(x)))
256 # If the target nodes are the same, skip this pair.
257 if v == y:
258 continue
259 if x not in G[u] and y not in G[v]:
260 G.remove_edge(u, v)
261 G.remove_edge(x, y)
262 G.add_edge(u, x)
263 G.add_edge(v, y)
264 swapped.append((u, v, x, y))
265 swapcount += 1
266 n += 1
267 wcount += 1
268 # If the graph remains connected, increase the window size.
269 if nx.is_connected(G):
270 window += 1
271 # Otherwise, undo the changes from the previous window and decrease
272 # the window size.
273 else:
274 while swapped:
275 (u, v, x, y) = swapped.pop()
276 G.add_edge(u, v)
277 G.add_edge(x, y)
278 G.remove_edge(u, x)
279 G.remove_edge(v, y)
280 swapcount -= 1
281 window = int(math.ceil(window / 2))
282 return swapcount