directed_edge_swap

directed_edge_swap(G, *, nswap=1, max_tries=100, seed=None)

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.

Parameters:

GDiGraph

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.

Returns:

GDiGraph

The graph after the edges are swapped.

Raises:

NetworkXError

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

NetworkXAlgorithmError

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

Notes

Does not enforce any connectivity constraints.

The graph G is modified in place.

A later swap is allowed to undo a previous swap.

References

[1]

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. https://doi.org/10.48550/arXiv.0905.4913. Published 2010 in Elec. J. Combinatorics (17(1)). R66. http://www.combinatorics.org/Volume_17/PDF/v17i1r66.pdf

[2]

“Combinatorics - Reaching All Possible Simple Directed Graphs with a given Degree Sequence with 2-Edge Swaps.” Mathematics Stack Exchange, https://math.stackexchange.com/questions/22272/. Accessed 30 May 2022.