directed_edge_swap#
- 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.
- 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 inG
.- NetworkXAlgorithmError
If the number of swap attempts exceeds
max_tries
beforenswap
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.