如何在 python 中给定顶点数生成所有 3 个正则图

Question

我想生成所有具有给定顶点数的 3-正则图，以检查某些属性是否适用于所有这些图。检查属性很容易，但首先我必须有效地生成图表。

有人可以帮我生成这些图（作为邻接矩阵）或给我一个包含此类图的文件。顶点数小于24.

谢谢

Answer 1

可以将 scd 文件作为二进制文件读入 python，并以与 readscd.c 文件相同的方式转换数据。这是一个例子：

import numpy

def convert(filename, n, k=3):
    num_edges = n*k/2
    f = open(filename, "r")
    values = numpy.fromfile(f, dtype=numpy.uint8)
    read_values = 0
    code = []
    while read_values < len(values):
        # dekomp(file,code)
        samebits = values.item(read_values)
        read_values += 1
        readbits = num_edges - samebits
        code = code[:samebits] + list(values[read_values:read_values+readbits])
        read_values += readbits
        # codetonlist(code,l)
        graph = numpy.zeros((n, n), dtype=numpy.uint8)
        v = 0
        count = [0] * n
        for w in code:
            w -= 1  # We are indexing from 0
            while(count[v] == k):
                v += 1
            # edge (v, w)
            graph.itemset((v, w), 1)
            graph.itemset((w, v), 1)
            count[v] += 1
            count[w] += 1
        yield graph

if __name__ == '__main__':
    import sys
    filename = sys.argv[1]
    nk = filename.split('.')[0].split('_')
    for g in convert(filename, int(nk[0]), int(nk[1])):
        print g

文件 18_3_3.scd 在几秒钟内处理完毕。打印花了几分钟。

如何在 python 中给定顶点数生成所有 3 个正则图

how to generate all 3 regular graphs given number of vertices in python

python

graph-theory