directed_edge_swap(G, *, nswap=1, max_tries=100, seed=None)[source]#

Swap three edges in a directed graph while keeping the node degrees fixed.

A directed edge swap swaps three edges such that a -> b -> c -> d becomes a -> c -> b -> d. This pattern of swapping allows all possible states with the same in- and out-degree distribution in a directed graph to be reached.

If the swap would create parallel edges (e.g. if a -> c already existed in the previous example), another attempt is made to find a suitable trio of edges.


A directed graph

nswapinteger (optional, default=1)

Number of three-edge (directed) swaps to perform

max_triesinteger (optional, default=100)

Maximum number of attempts to swap edges

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.


The graph after the edges are swapped.


If G is not directed, or If nswap > max_tries, or If there are fewer than 4 nodes or 3 edges in G.


If the number of swap attempts exceeds max_tries before nswap swaps are made


Does not enforce any connectivity constraints.

The graph G is modified in place.

A later swap is allowed to undo a previous swap.



Erdős, Péter L., et al. “A Simple Havel-Hakimi Type Algorithm to Realize Graphical Degree Sequences of Directed Graphs.” ArXiv:0905.4913 [Math], Jan. 2010. Published 2010 in Elec. J. Combinatorics (17(1)). R66.


“Combinatorics - Reaching All Possible Simple Directed Graphs with a given Degree Sequence with 2-Edge Swaps.” Mathematics Stack Exchange, Accessed 30 May 2022.