Skip to main content
`Ctrl`+`K`

# 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:
    G DiGraph

      A directed graph

    nswap integer (optional, default=1)

      Number of three-edge (directed) swaps to perform

    max_tries integer (optional, default=100)

      Maximum number of attempts to swap edges

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

  Returns:
    G DiGraph

      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.