| 229 | @patch_docstring(nxa.watts_strogatz_graph) |
| 230 | @py_random_state(3) |
| 231 | def watts_strogatz_graph(n, k, p, seed=None): |
| 232 | if k > n: |
| 233 | raise nx.NetworkXError("k>n, choose smaller k or larger n") |
| 234 | |
| 235 | # If k == n, the graph is complete not Watts-Strogatz |
| 236 | if k == n: |
| 237 | return nx.complete_graph(n) |
| 238 | |
| 239 | G = nx.Graph() |
| 240 | nodes = list(range(n)) # nodes are labeled 0 to n-1 |
| 241 | # connect each node to k/2 neighbors |
| 242 | for j in range(1, k // 2 + 1): |
| 243 | targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list |
| 244 | G.add_edges_from(zip(nodes, targets)) |
| 245 | # rewire edges from each node |
| 246 | # loop over all nodes in order (label) and neighbors in order (distance) |
| 247 | # no self loops or multiple edges allowed |
| 248 | for j in range(1, k // 2 + 1): # outer loop is neighbors |
| 249 | targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list |
| 250 | # inner loop in node order |
| 251 | for u, v in zip(nodes, targets): |
| 252 | if seed.random() < p: |
| 253 | w = seed.choice(nodes) |
| 254 | # Enforce no self-loops or multiple edges |
| 255 | while w == u or G.has_edge(u, w): |
| 256 | w = seed.choice(nodes) |
| 257 | if G.degree(u) >= n - 1: |
| 258 | break # skip this rewiring |
| 259 | else: |
| 260 | G.remove_edge(u, v) |
| 261 | G.add_edge(u, w) |
| 262 | return G |
| 263 | |
| 264 | |
| 265 | @patch_docstring(nxa.connected_watts_strogatz_graph) |