| 276 | @patch_docstring(nxa.random_regular_graph) |
| 277 | @py_random_state(2) |
| 278 | def random_regular_graph(d, n, seed=None): |
| 279 | if (n * d) % 2 != 0: |
| 280 | raise nx.NetworkXError("n * d must be even") |
| 281 | |
| 282 | if not 0 <= d < n: |
| 283 | raise nx.NetworkXError("the 0 <= d < n inequality must be satisfied") |
| 284 | |
| 285 | if d == 0: |
| 286 | return empty_graph(n) |
| 287 | |
| 288 | def _suitable(edges, potential_edges): |
| 289 | # Helper subroutine to check if there are suitable edges remaining |
| 290 | # If False, the generation of the graph has failed |
| 291 | if not potential_edges: |
| 292 | return True |
| 293 | for s1 in potential_edges: |
| 294 | for s2 in potential_edges: |
| 295 | # Two iterators on the same dictionary are guaranteed |
| 296 | # to visit it in the same order if there are no |
| 297 | # intervening modifications. |
| 298 | if s1 == s2: |
| 299 | # Only need to consider s1-s2 pair one time |
| 300 | break |
| 301 | if s1 > s2: |
| 302 | s1, s2 = s2, s1 |
| 303 | if (s1, s2) not in edges: |
| 304 | return True |
| 305 | return False |
| 306 | |
| 307 | def _try_creation(): |
| 308 | # Attempt to create an edge set |
| 309 | |
| 310 | edges = set() |
| 311 | stubs = list(range(n)) * d |
| 312 | |
| 313 | while stubs: |
| 314 | potential_edges = defaultdict(lambda: 0) |
| 315 | seed.shuffle(stubs) |
| 316 | stubiter = iter(stubs) |
| 317 | for s1, s2 in zip(stubiter, stubiter): |
| 318 | if s1 > s2: |
| 319 | s1, s2 = s2, s1 |
| 320 | if s1 != s2 and ((s1, s2) not in edges): |
| 321 | edges.add((s1, s2)) |
| 322 | else: |
| 323 | potential_edges[s1] += 1 |
| 324 | potential_edges[s2] += 1 |
| 325 | |
| 326 | if not _suitable(edges, potential_edges): |
| 327 | return None # failed to find suitable edge set |
| 328 | |
| 329 | stubs = [ |
| 330 | node |
| 331 | for node, potential in potential_edges.items() |
| 332 | for _ in range(potential) |
| 333 | ] |
| 334 | return edges |
| 335 | |