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