Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/swap.py: 8%
165 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Swap edges in a graph.
2"""
4import math
6import networkx as nx
7from networkx.utils import py_random_state
9__all__ = ["double_edge_swap", "connected_double_edge_swap", "directed_edge_swap"]
12@nx.utils.not_implemented_for("undirected")
13@py_random_state(3)
14@nx._dispatch
15def directed_edge_swap(G, *, nswap=1, max_tries=100, seed=None):
16 """Swap three edges in a directed graph while keeping the node degrees fixed.
18 A directed edge swap swaps three edges such that a -> b -> c -> d becomes
19 a -> c -> b -> d. This pattern of swapping allows all possible states with the
20 same in- and out-degree distribution in a directed graph to be reached.
22 If the swap would create parallel edges (e.g. if a -> c already existed in the
23 previous example), another attempt is made to find a suitable trio of edges.
25 Parameters
26 ----------
27 G : DiGraph
28 A directed graph
30 nswap : integer (optional, default=1)
31 Number of three-edge (directed) swaps to perform
33 max_tries : integer (optional, default=100)
34 Maximum number of attempts to swap edges
36 seed : integer, random_state, or None (default)
37 Indicator of random number generation state.
38 See :ref:`Randomness<randomness>`.
40 Returns
41 -------
42 G : DiGraph
43 The graph after the edges are swapped.
45 Raises
46 ------
47 NetworkXError
48 If `G` is not directed, or
49 If nswap > max_tries, or
50 If there are fewer than 4 nodes or 3 edges in `G`.
51 NetworkXAlgorithmError
52 If the number of swap attempts exceeds `max_tries` before `nswap` swaps are made
54 Notes
55 -----
56 Does not enforce any connectivity constraints.
58 The graph G is modified in place.
60 References
61 ----------
62 .. [1] Erdős, Péter L., et al. “A Simple Havel-Hakimi Type Algorithm to Realize
63 Graphical Degree Sequences of Directed Graphs.” ArXiv:0905.4913 [Math],
64 Jan. 2010. https://doi.org/10.48550/arXiv.0905.4913.
65 Published 2010 in Elec. J. Combinatorics (17(1)). R66.
66 http://www.combinatorics.org/Volume_17/PDF/v17i1r66.pdf
67 .. [2] “Combinatorics - Reaching All Possible Simple Directed Graphs with a given
68 Degree Sequence with 2-Edge Swaps.” Mathematics Stack Exchange,
69 https://math.stackexchange.com/questions/22272/. Accessed 30 May 2022.
70 """
71 if nswap > max_tries:
72 raise nx.NetworkXError("Number of swaps > number of tries allowed.")
73 if len(G) < 4:
74 raise nx.NetworkXError("DiGraph has fewer than four nodes.")
75 if len(G.edges) < 3:
76 raise nx.NetworkXError("DiGraph has fewer than 3 edges")
78 # Instead of choosing uniformly at random from a generated edge list,
79 # this algorithm chooses nonuniformly from the set of nodes with
80 # probability weighted by degree.
81 tries = 0
82 swapcount = 0
83 keys, degrees = zip(*G.degree()) # keys, degree
84 cdf = nx.utils.cumulative_distribution(degrees) # cdf of degree
85 discrete_sequence = nx.utils.discrete_sequence
87 while swapcount < nswap:
88 # choose source node index from discrete distribution
89 start_index = discrete_sequence(1, cdistribution=cdf, seed=seed)[0]
90 start = keys[start_index]
91 tries += 1
93 if tries > max_tries:
94 msg = f"Maximum number of swap attempts ({tries}) exceeded before desired swaps achieved ({nswap})."
95 raise nx.NetworkXAlgorithmError(msg)
97 # If the given node doesn't have any out edges, then there isn't anything to swap
98 if G.out_degree(start) == 0:
99 continue
100 second = seed.choice(list(G.succ[start]))
101 if start == second:
102 continue
104 if G.out_degree(second) == 0:
105 continue
106 third = seed.choice(list(G.succ[second]))
107 if second == third:
108 continue
110 if G.out_degree(third) == 0:
111 continue
112 fourth = seed.choice(list(G.succ[third]))
113 if third == fourth:
114 continue
116 if (
117 third not in G.succ[start]
118 and fourth not in G.succ[second]
119 and second not in G.succ[third]
120 ):
121 # Swap nodes
122 G.add_edge(start, third)
123 G.add_edge(third, second)
124 G.add_edge(second, fourth)
125 G.remove_edge(start, second)
126 G.remove_edge(second, third)
127 G.remove_edge(third, fourth)
128 swapcount += 1
130 return G
133@py_random_state(3)
134@nx._dispatch
135def double_edge_swap(G, nswap=1, max_tries=100, seed=None):
136 """Swap two edges in the graph while keeping the node degrees fixed.
138 A double-edge swap removes two randomly chosen edges u-v and x-y
139 and creates the new edges u-x and v-y::
141 u--v u v
142 becomes | |
143 x--y x y
145 If either the edge u-x or v-y already exist no swap is performed
146 and another attempt is made to find a suitable edge pair.
148 Parameters
149 ----------
150 G : graph
151 An undirected graph
153 nswap : integer (optional, default=1)
154 Number of double-edge swaps to perform
156 max_tries : integer (optional)
157 Maximum number of attempts to swap edges
159 seed : integer, random_state, or None (default)
160 Indicator of random number generation state.
161 See :ref:`Randomness<randomness>`.
163 Returns
164 -------
165 G : graph
166 The graph after double edge swaps.
168 Raises
169 ------
170 NetworkXError
171 If `G` is directed, or
172 If `nswap` > `max_tries`, or
173 If there are fewer than 4 nodes or 2 edges in `G`.
174 NetworkXAlgorithmError
175 If the number of swap attempts exceeds `max_tries` before `nswap` swaps are made
177 Notes
178 -----
179 Does not enforce any connectivity constraints.
181 The graph G is modified in place.
182 """
183 if G.is_directed():
184 raise nx.NetworkXError(
185 "double_edge_swap() not defined for directed graphs. Use directed_edge_swap instead."
186 )
187 if nswap > max_tries:
188 raise nx.NetworkXError("Number of swaps > number of tries allowed.")
189 if len(G) < 4:
190 raise nx.NetworkXError("Graph has fewer than four nodes.")
191 if len(G.edges) < 2:
192 raise nx.NetworkXError("Graph has fewer than 2 edges")
193 # Instead of choosing uniformly at random from a generated edge list,
194 # this algorithm chooses nonuniformly from the set of nodes with
195 # probability weighted by degree.
196 n = 0
197 swapcount = 0
198 keys, degrees = zip(*G.degree()) # keys, degree
199 cdf = nx.utils.cumulative_distribution(degrees) # cdf of degree
200 discrete_sequence = nx.utils.discrete_sequence
201 while swapcount < nswap:
202 # if random.random() < 0.5: continue # trick to avoid periodicities?
203 # pick two random edges without creating edge list
204 # choose source node indices from discrete distribution
205 (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
206 if ui == xi:
207 continue # same source, skip
208 u = keys[ui] # convert index to label
209 x = keys[xi]
210 # choose target uniformly from neighbors
211 v = seed.choice(list(G[u]))
212 y = seed.choice(list(G[x]))
213 if v == y:
214 continue # same target, skip
215 if (x not in G[u]) and (y not in G[v]): # don't create parallel edges
216 G.add_edge(u, x)
217 G.add_edge(v, y)
218 G.remove_edge(u, v)
219 G.remove_edge(x, y)
220 swapcount += 1
221 if n >= max_tries:
222 e = (
223 f"Maximum number of swap attempts ({n}) exceeded "
224 f"before desired swaps achieved ({nswap})."
225 )
226 raise nx.NetworkXAlgorithmError(e)
227 n += 1
228 return G
231@py_random_state(3)
232@nx._dispatch
233def connected_double_edge_swap(G, nswap=1, _window_threshold=3, seed=None):
234 """Attempts the specified number of double-edge swaps in the graph `G`.
236 A double-edge swap removes two randomly chosen edges `(u, v)` and `(x,
237 y)` and creates the new edges `(u, x)` and `(v, y)`::
239 u--v u v
240 becomes | |
241 x--y x y
243 If either `(u, x)` or `(v, y)` already exist, then no swap is performed
244 so the actual number of swapped edges is always *at most* `nswap`.
246 Parameters
247 ----------
248 G : graph
249 An undirected graph
251 nswap : integer (optional, default=1)
252 Number of double-edge swaps to perform
254 _window_threshold : integer
256 The window size below which connectedness of the graph will be checked
257 after each swap.
259 The "window" in this function is a dynamically updated integer that
260 represents the number of swap attempts to make before checking if the
261 graph remains connected. It is an optimization used to decrease the
262 running time of the algorithm in exchange for increased complexity of
263 implementation.
265 If the window size is below this threshold, then the algorithm checks
266 after each swap if the graph remains connected by checking if there is a
267 path joining the two nodes whose edge was just removed. If the window
268 size is above this threshold, then the algorithm performs do all the
269 swaps in the window and only then check if the graph is still connected.
271 seed : integer, random_state, or None (default)
272 Indicator of random number generation state.
273 See :ref:`Randomness<randomness>`.
275 Returns
276 -------
277 int
278 The number of successful swaps
280 Raises
281 ------
283 NetworkXError
285 If the input graph is not connected, or if the graph has fewer than four
286 nodes.
288 Notes
289 -----
291 The initial graph `G` must be connected, and the resulting graph is
292 connected. The graph `G` is modified in place.
294 References
295 ----------
296 .. [1] C. Gkantsidis and M. Mihail and E. Zegura,
297 The Markov chain simulation method for generating connected
298 power law random graphs, 2003.
299 http://citeseer.ist.psu.edu/gkantsidis03markov.html
300 """
301 if not nx.is_connected(G):
302 raise nx.NetworkXError("Graph not connected")
303 if len(G) < 4:
304 raise nx.NetworkXError("Graph has fewer than four nodes.")
305 n = 0
306 swapcount = 0
307 deg = G.degree()
308 # Label key for nodes
309 dk = [n for n, d in G.degree()]
310 cdf = nx.utils.cumulative_distribution([d for n, d in G.degree()])
311 discrete_sequence = nx.utils.discrete_sequence
312 window = 1
313 while n < nswap:
314 wcount = 0
315 swapped = []
316 # If the window is small, we just check each time whether the graph is
317 # connected by checking if the nodes that were just separated are still
318 # connected.
319 if window < _window_threshold:
320 # This Boolean keeps track of whether there was a failure or not.
321 fail = False
322 while wcount < window and n < nswap:
323 # Pick two random edges without creating the edge list. Choose
324 # source nodes from the discrete degree distribution.
325 (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
326 # If the source nodes are the same, skip this pair.
327 if ui == xi:
328 continue
329 # Convert an index to a node label.
330 u = dk[ui]
331 x = dk[xi]
332 # Choose targets uniformly from neighbors.
333 v = seed.choice(list(G.neighbors(u)))
334 y = seed.choice(list(G.neighbors(x)))
335 # If the target nodes are the same, skip this pair.
336 if v == y:
337 continue
338 if x not in G[u] and y not in G[v]:
339 G.remove_edge(u, v)
340 G.remove_edge(x, y)
341 G.add_edge(u, x)
342 G.add_edge(v, y)
343 swapped.append((u, v, x, y))
344 swapcount += 1
345 n += 1
346 # If G remains connected...
347 if nx.has_path(G, u, v):
348 wcount += 1
349 # Otherwise, undo the changes.
350 else:
351 G.add_edge(u, v)
352 G.add_edge(x, y)
353 G.remove_edge(u, x)
354 G.remove_edge(v, y)
355 swapcount -= 1
356 fail = True
357 # If one of the swaps failed, reduce the window size.
358 if fail:
359 window = math.ceil(window / 2)
360 else:
361 window += 1
362 # If the window is large, then there is a good chance that a bunch of
363 # swaps will work. It's quicker to do all those swaps first and then
364 # check if the graph remains connected.
365 else:
366 while wcount < window and n < nswap:
367 # Pick two random edges without creating the edge list. Choose
368 # source nodes from the discrete degree distribution.
369 (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
370 # If the source nodes are the same, skip this pair.
371 if ui == xi:
372 continue
373 # Convert an index to a node label.
374 u = dk[ui]
375 x = dk[xi]
376 # Choose targets uniformly from neighbors.
377 v = seed.choice(list(G.neighbors(u)))
378 y = seed.choice(list(G.neighbors(x)))
379 # If the target nodes are the same, skip this pair.
380 if v == y:
381 continue
382 if x not in G[u] and y not in G[v]:
383 G.remove_edge(u, v)
384 G.remove_edge(x, y)
385 G.add_edge(u, x)
386 G.add_edge(v, y)
387 swapped.append((u, v, x, y))
388 swapcount += 1
389 n += 1
390 wcount += 1
391 # If the graph remains connected, increase the window size.
392 if nx.is_connected(G):
393 window += 1
394 # Otherwise, undo the changes from the previous window and decrease
395 # the window size.
396 else:
397 while swapped:
398 (u, v, x, y) = swapped.pop()
399 G.add_edge(u, v)
400 G.add_edge(x, y)
401 G.remove_edge(u, x)
402 G.remove_edge(v, y)
403 swapcount -= 1
404 window = math.ceil(window / 2)
405 return swapcount