Attempt nswap doubleedge swaps on the graph G. Returns count of successful swaps. Enforces connectivity. The graph G is modified in place. A doubleedge swap removes two randomly choseen edges uv and xy and creates the new edges ux and vy: uv u v becomes   xy x y If either the edge ux or vy 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{gkantsidis03markov, 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 doubleedge swaps on the graph G. Returns count of successful swaps. Enforces connectivity. The graph G is modified in place. A doubleedge swap removes two randomly choseen edges uv and xy and creates the new edges ux and vy: uv u v becomes   xy x y If either the edge ux or vy 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{gkantsidis03markov, 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):
