Logo Search packages:      
Sourcecode: python-networkx version File versions  Download package

def networkx::generators::degree_seq::connected_double_edge_swap (   G,
  nswap = 1 
)

Attempt nswap double-edge swaps on the graph G.

Returns count of successful swaps.  Enforces connectivity.
The graph G is modified in place.

A double-edge swap removes two randomly choseen 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 so
the actual count of swapped edges is always <= nswap

The initial graph G must be connected and the resulting graph is connected.

Reference:

 @misc{gkantsidis-03-markov,
  author = "C. Gkantsidis and M. Mihail and E. Zegura",
  title = "The Markov chain simulation method for generating connected
           power law random graphs",
  year = "2003",
  url = "http://citeseer.ist.psu.edu/gkantsidis03markov.html"
  }

Definition at line 396 of file degree_seq.py.

00396                                           :
    """Attempt nswap double-edge swaps on the graph G.

    Returns count of successful swaps.  Enforces connectivity.
    The graph G is modified in place.

    A double-edge swap removes two randomly choseen 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 so
    the actual count of swapped edges is always <= nswap

    The initial graph G must be connected and the resulting graph is connected.

    Reference:

     @misc{gkantsidis-03-markov,
      author = "C. Gkantsidis and M. Mihail and E. Zegura",
      title = "The Markov chain simulation method for generating connected
               power law random graphs",
      year = "2003",
      url = "http://citeseer.ist.psu.edu/gkantsidis03markov.html"
      }

    """
    import math
    if not networkx.is_connected(G):
       raise networkx.NetworkXException("Graph not connected")

    n=0
    swapcount=0
    deg=G.degree(with_labels=True)
    dk=deg.keys() # key labels 
    ideg=G.degree()
    cdf=networkx.utils.cumulative_distribution(G.degree()) 
    if len(cdf)<4:
        raise networkx.NetworkXError, \
          "Graph has less than four nodes."
    window=1
    while n < nswap:
        wcount=0
        swapped=[]
        while wcount < window and n < nswap:
            # pick two randon edges without creating edge list
            # chose source nodes from discrete distribution
            (ui,xi)=networkx.utils.discrete_sequence(2,cdistribution=cdf) 
            if ui==xi: continue # same source, skip
            u=dk[ui] # convert index to label
            x=dk[xi] 
            v=random.choice(G[u]) # choose target uniformly from nbrs
            y=random.choice(G[x]) 
            if v==y: continue # same target, skip
            if (not G.has_edge(u,x)) and (not G.has_edge(v,y)):
                G.delete_edge(u,v)
                G.delete_edge(x,y)
                G.add_edge(u,x)
                G.add_edge(v,y)
                swapped.append((u,v,x,y))
                swapcount+=1
            n+=1
            wcount+=1
        if networkx.is_connected(G): # increase window
            window+=1
        else: # undo changes from previous window, decrease window
            while swapped:
                (u,v,x,y)=swapped.pop()
                G.add_edge(u,v)
                G.add_edge(x,y)
                G.delete_edge(u,x)
                G.delete_edge(v,y)
                swapcount-=1
            window = int(math.ceil(float(window)/2))
        assert G.degree() == ideg
    return swapcount



def li_smax_graph(degree_seq):


Generated by  Doxygen 1.6.0   Back to index