[メモ] バイアスのないランダム正則グラフの生成

英語版Wikiから参照
ノード数Nで次数kの正則グラフが O(n^2)くらいで計算できる。

import random
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

def random_pair(n: int, m: int) -> list[list[int]]:
    assert n % m == 0
    
    mem = list(range(n))
    random.shuffle(mem)
    pairs = [[mem[m * i + j] for j in range(m)] for i in range(n // m)]
    
    return pairs

def _random_regular_graph_impl(n: int, k: int) -> list[list[int]] | None:
    pairs = random_pair(n * k, 2)
    clusters = random_pair(n * k, k)
    
    ntwk = [[0 for j in range(n)] for i in range(n)]
    for (e_in, e_out) in pairs:
        idx_in = None
        for idx, cluster in enumerate(clusters):
            if e_in in cluster:
                idx_in = idx
        
        idx_out = None
        for idx, cluster in enumerate(clusters):
            if e_out in cluster:
                idx_out = idx
        
        if ntwk[idx_in][idx_out] != 0:
            return None
        if idx_in == idx_out:
            return None
        
        ntwk[idx_in][idx_out] = 1
        ntwk[idx_out][idx_in] = 1
    
    return ntwk
    

def random_regular_graph(n: int , k: int) -> None:
    res = None
    while res is None:
        res = _random_regular_graph_impl(n, k)
    
    return res
    

if __name__ == "__main__":
    A = np.asarray(random_regular_graph(20, 3))
    
    G = nx.Graph(A)

    nx.draw(G)
    plt.show()

データ構造が適当なところがあるので、そこら辺を治すを早くなるはず。