Module Expr Str ImportFrom alias Import alias Import alias Import alias identifier Assign NameStore Call AttributeLoad Str attr ListLoad Str Str Str Str Str Assign NameStore ListLoad Str Str FunctionDef arguments args NameParam NameParam NameParam defaults Num Num body Expr Str If Call AttributeLoad NameLoad attr body Raise Call AttributeLoad NameLoad attr Str If CompareGt NameLoad NameLoad body Raise Call AttributeLoad NameLoad attr Str If CompareLt Call NameLoad NameLoad Num body Raise Call AttributeLoad NameLoad attr Str Assign NameStore Num Assign NameStore Num Assign TupleStore NameStore NameStore Call NameLoad Call AttributeLoad NameLoad attr Assign NameStore Call AttributeLoad AttributeLoad NameLoad attr attr NameLoad While CompareLt NameLoad NameLoad body Assign TupleStore NameStore NameStore Call AttributeLoad AttributeLoad NameLoad attr attr Num keyword NameLoad If CompareEq NameLoad NameLoad body Continue Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call NameLoad SubscriptLoad NameLoad Index NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call NameLoad SubscriptLoad NameLoad Index NameLoad If CompareEq NameLoad NameLoad body Continue If BoolOpAnd CompareNotIn NameLoad SubscriptLoad NameLoad Index NameLoad CompareNotIn NameLoad SubscriptLoad NameLoad Index NameLoad body Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad AugAssignAdd NameStore Num If CompareGtE NameLoad NameLoad body Assign NameStore BinOpAdd BinOpMod Str NameLoad BinOpMod Str NameLoad Raise Call AttributeLoad NameLoad attr NameLoad AugAssignAdd NameStore Num Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults Num Num body Expr Str If UnaryOpNot Call AttributeLoad NameLoad attr NameLoad body Raise Call AttributeLoad NameLoad attr Str If CompareLt Call NameLoad NameLoad Num body Raise Call AttributeLoad NameLoad attr Str Assign NameStore Num Assign NameStore Num Assign NameStore Call AttributeLoad NameLoad attr Assign NameStore Call NameLoad GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr Assign NameStore Call AttributeLoad AttributeLoad NameLoad attr attr Call NameLoad GeneratorExp NameLoad comprehension TupleStore NameStore NameStore Call AttributeLoad NameLoad attr Assign NameStore Num While CompareLt NameLoad NameLoad body Assign NameStore Num Assign NameStore ListLoad If CompareLt NameLoad NameLoad body Assign NameStore NameLoad While BoolOpAnd CompareLt NameLoad NameLoad CompareLt NameLoad NameLoad body Assign TupleStore NameStore NameStore Call AttributeLoad AttributeLoad NameLoad attr attr Num keyword NameLoad If CompareEq NameLoad NameLoad body Continue Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call NameLoad Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call NameLoad Call AttributeLoad NameLoad attr NameLoad If CompareEq NameLoad NameLoad body Continue If BoolOpAnd CompareNotIn NameLoad SubscriptLoad NameLoad Index NameLoad CompareNotIn NameLoad SubscriptLoad NameLoad Index NameLoad body Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad NameLoad NameLoad AugAssignAdd NameStore Num AugAssignAdd NameStore Num If Call AttributeLoad NameLoad attr NameLoad NameLoad NameLoad body AugAssignAdd NameStore Num orelse Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad AugAssignSub NameStore Num Assign NameStore NameLoad If NameLoad body Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr BinOpDiv NameLoad Num orelse AugAssignAdd NameStore Num orelse While BoolOpAnd CompareLt NameLoad NameLoad CompareLt NameLoad NameLoad body Assign TupleStore NameStore NameStore Call AttributeLoad AttributeLoad NameLoad attr attr Num keyword NameLoad If CompareEq NameLoad NameLoad body Continue Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call NameLoad Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call AttributeLoad NameLoad attr Call NameLoad Call AttributeLoad NameLoad attr NameLoad If CompareEq NameLoad NameLoad body Continue If BoolOpAnd CompareNotIn NameLoad SubscriptLoad NameLoad Index NameLoad CompareNotIn NameLoad SubscriptLoad NameLoad Index NameLoad body Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad NameLoad NameLoad AugAssignAdd NameStore Num AugAssignAdd NameStore Num AugAssignAdd NameStore Num If Call AttributeLoad NameLoad attr NameLoad body AugAssignAdd NameStore Num orelse While NameLoad body Assign TupleStore NameStore NameStore NameStore NameStore Call AttributeLoad NameLoad attr Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad AugAssignSub NameStore Num Assign NameStore Call NameLoad Call AttributeLoad NameLoad attr BinOpDiv NameLoad Num Return NameLoad decorator_list
N/A N/A Swap edges in a graph.
 __future__ division N/A math N/A random N/A networkx nx N/A __author__ N/A N/A join N/A Aric Hagberg (hagberg@lanl.gov) Pieter Swart (swart@lanl.gov) Dan Schult (dschult@colgate.edu) Joel Miller (joel.c.miller.research@gmail.com) Ben Edwards N/A __all__ N/A double_edge_swap connected_double_edge_swap double_edge_swap N/A N/A G nswap max_tries N/A 1 100 N/A N/A Swap two edges in the graph while keeping the node degrees fixed.

    A double-edge swap removes two randomly chosen edges u-v and x-y
    and creates the new edges u-x and v-y::

     u--v            u  v
            becomes  |  |
     x--y            x  y

    If either the edge u-x or v-y already exist no swap is performed
    and another attempt is made to find a suitable edge pair.

    Parameters
    ----------
    G : graph
       An undirected graph

    nswap : integer (optional, default=1)
       Number of double-edge swaps to perform

    max_tries : integer (optional)
       Maximum number of attempts to swap edges

    Returns
    -------
    G : graph
       The graph after double edge swaps.

    Notes
    -----
    Does not enforce any connectivity constraints.

    The graph G is modified in place.
     N/A N/A N/A G is_directed N/A N/A N/A N/A nx NetworkXError double_edge_swap() not defined for directed graphs. N/A N/A nswap max_tries N/A N/A N/A N/A nx NetworkXError Number of swaps > number of tries allowed. N/A N/A N/A len G 4 N/A N/A N/A N/A nx NetworkXError Graph has less than four nodes. N/A n 0 N/A swapcount 0 N/A N/A keys degrees N/A zip N/A N/A G degree N/A cdf N/A N/A N/A nx utils cumulative_distribution degrees N/A N/A swapcount nswap N/A N/A N/A ui xi N/A N/A N/A nx utils discrete_sequence 2 cdistribution cdf N/A N/A ui xi N/A N/A N/A u N/A keys N/A ui N/A x N/A keys N/A xi N/A v N/A N/A random choice N/A list N/A G N/A u N/A y N/A N/A random choice N/A list N/A G N/A x N/A N/A v y N/A N/A N/A N/A N/A x N/A G N/A u N/A y N/A G N/A v N/A N/A N/A N/A G add_edge u x N/A N/A N/A G add_edge v y N/A N/A N/A G remove_edge u v N/A N/A N/A G remove_edge x y N/A swapcount 1 N/A N/A n max_tries N/A N/A e N/A N/A Maximum number of swap attempts (%s) exceeded  n N/A before desired swaps achieved (%s). nswap N/A N/A N/A nx NetworkXAlgorithmError e N/A n 1 N/A G N/A connected_double_edge_swap N/A N/A G nswap _window_threshold N/A 1 3 N/A N/A Attempts the specified number of double-edge swaps in the graph `G`.

    A double-edge swap removes two randomly chosen edges `(u, v)` and `(x,
    y)` and creates the new edges `(u, x)` and `(v, y)`::

     u--v            u  v
            becomes  |  |
     x--y            x  y

    If either `(u, x)` or `(v, y)` already exist, then no swap is performed
    so the actual number of swapped edges is always *at most* `nswap`.

    Parameters
    ----------
    G : graph
       An undirected graph

    nswap : integer (optional, default=1)
       Number of double-edge swaps to perform

    _window_threshold : integer

       The window size below which connectedness of the graph will be checked
       after each swap.

       The "window" in this function is a dynamically updated integer that
       represents the number of swap attempts to make before checking if the
       graph remains connected. It is an optimization used to decrease the
       running time of the algorithm in exchange for increased complexity of
       implementation.

       If the window size is below this threshold, then the algorithm checks
       after each swap if the graph remains connected by checking if there is a
       path joining the two nodes whose edge was just removed. If the window
       size is above this threshold, then the algorithm performs do all the
       swaps in the window and only then check if the graph is still connected.

    Returns
    -------
    int
       The number of successful swaps

    Raises
    ------

    NetworkXError

       If the input graph is not connected, or if the graph has fewer than four
       nodes.

    Notes
    -----

    The initial graph `G` must be connected, and the resulting graph is
    connected. The graph `G` is modified in place.

    References
    ----------
    .. [1] C. Gkantsidis and M. Mihail and E. Zegura,
           The Markov chain simulation method for generating connected
           power law random graphs, 2003.
           http://citeseer.ist.psu.edu/gkantsidis03markov.html
     N/A N/A N/A N/A nx is_connected G N/A N/A N/A N/A nx NetworkXError Graph not connected N/A N/A N/A len G 4 N/A N/A N/A N/A nx NetworkXError Graph has less than four nodes. N/A n 0 N/A swapcount 0 N/A deg N/A N/A G degree N/A dk N/A list N/A n N/A N/A n d N/A N/A G degree N/A cdf N/A N/A N/A nx utils cumulative_distribution N/A list N/A d N/A N/A n d N/A N/A G degree N/A window 1 N/A N/A n nswap N/A N/A wcount 0 N/A swapped N/A N/A N/A window _window_threshold N/A N/A fail False N/A N/A N/A wcount window N/A n nswap N/A N/A N/A ui xi N/A N/A N/A nx utils discrete_sequence 2 cdistribution cdf N/A N/A ui xi N/A N/A N/A u N/A dk N/A ui N/A x N/A dk N/A xi N/A v N/A N/A random choice N/A list N/A N/A G neighbors u N/A y N/A N/A random choice N/A list N/A N/A G neighbors x N/A N/A v y N/A N/A N/A N/A N/A x N/A G N/A u N/A y N/A G N/A v N/A N/A N/A N/A G remove_edge u v N/A N/A N/A G remove_edge x y N/A N/A N/A G add_edge u x N/A N/A N/A G add_edge v y N/A N/A N/A swapped append N/A u v x y N/A swapcount 1 N/A n 1 N/A N/A N/A nx has_path G u v N/A N/A wcount 1 N/A N/A N/A N/A G add_edge u v N/A N/A N/A G add_edge x y N/A N/A N/A G remove_edge u x N/A N/A N/A G remove_edge v y N/A swapcount 1 N/A fail True N/A fail N/A N/A window N/A int N/A N/A math ceil N/A window 2 N/A N/A window 1 N/A N/A N/A N/A wcount window N/A n nswap N/A N/A N/A ui xi N/A N/A N/A nx utils discrete_sequence 2 cdistribution cdf N/A N/A ui xi N/A N/A N/A u N/A dk N/A ui N/A x N/A dk N/A xi N/A v N/A N/A random choice N/A list N/A N/A G neighbors u N/A y N/A N/A random choice N/A list N/A N/A G neighbors x N/A N/A v y N/A N/A N/A N/A N/A x N/A G N/A u N/A y N/A G N/A v N/A N/A N/A N/A G remove_edge u v N/A N/A N/A G remove_edge x y N/A N/A N/A G add_edge u x N/A N/A N/A G add_edge v y N/A N/A N/A swapped append N/A u v x y N/A swapcount 1 N/A n 1 N/A wcount 1 N/A N/A N/A nx is_connected G N/A N/A window 1 N/A N/A swapped N/A N/A N/A u v x y N/A N/A swapped pop N/A N/A N/A G add_edge u v N/A N/A N/A G add_edge x y N/A N/A N/A G remove_edge u x N/A N/A N/A G remove_edge v y N/A swapcount 1 N/A window N/A int N/A N/A math ceil N/A window 2 N/A swapcount N/A