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