枚举图

Question

我想与Ñ顶点，其中每个顶点有ķ直接后继者和ķ直接前任创建该组的所有有向图的。 Ñ和ķ不会那么大，而围绕Ñ = 8和ķ = 3该集包括环状和无环图。每个图形将作为抽样大量加权图形的模板。

我的兴趣是在拓扑图案的作用，所以我不想品尝任何两个图是相互对称，重量在那里对称意味着没有顶点的排列在它变换一个图形存在进入另一个。

甲幼稚的解决方案是考虑2 ^（Ñ *（Ñ - 1））邻接矩阵和消除所有那些（大部分），用于其中直接后继者或前导者限制被违反。对于ñ = 8，这仍然有足够的位来表示，并简单地枚举每个矩阵在uint64_t内舒适。

跟踪行数和列数将是另一个改进，但真正的瓶颈是将图添加到结果集中，此时我们需要测试集合中已存在的每个其他图的对称性。对于n = 8每个插入操作已经超过40,000个排列。

任何人都可以引用我的算法，我可以阅读，可以以更聪明的方式做到这一切？是否有C，C++，Java或Python的图库，已经实现了这样一个全面的图形生成器？是否有一个存储库，其中某人已经“合理”列出所有图表n和k？

Answer 1

在我看来，图同构不是你应该考虑实现自己的东西。我相信目前最先进的技术是Brendan McKay的Nauty（及相关程序/库）。这与工作有点相似，但避免做自己的天真图同构可能是值得的。此外，它主要面向无向图，但它也可以做有向图。您可能想查看与Nauty一起提供的geng（其生成无向图）和（它生成有底图的有向图）实用程序。

Answer 2

这是一个评论比一个答案更多，因为它似乎我错过了你的问题。

首先，这样的图可能是非循环的吗？

我也想知道你的对称性约束。这不会使所有这些图形彼此对称吗？它是否允许排列连接矩阵的行和列？

例如，如果我们允许图中的自连接，下面的连接矩阵是否满足您的条件？

1  1  0  0  0  0  0  1 
1  1  1  0  0  0  0  0 
0  1  1  1  0  0  0  0 
0  0  1  1  1  0  0  0 
0  0  0  1  1  1  0  0 
0  0  0  0  1  1  1  0 
0  0  0  0  0  1  1  1 
1  0  0  0  0  0  1  1 

从这个矩阵开始，是那么不可能置换它的行和列，以获得所有这样的图，所有的行和列有三个的总和？

这样的矩阵的一个例子可以通过以下方式（使用MATLAB）从上述矩阵A获得。

>> A(randperm(8),randperm(8)) 

ans = 

    0  1  0  0  0  1  1  0 
    0  0  1  0  1  0  1  0 
    1  1  0  1  0  0  0  0 
    1  1  0  0  0  1  0  0 
    1  0  0  1  0  0  0  1 
    0  0  1  1  0  0  0  1 
    0  0  1  0  1  0  0  1 
    0  0  0  0  1  1  1  0 

PS。在这种情况下，为了获得对角线上只有零点的矩阵，我重复了几次该命令。:)

编辑

啊，我从你的意见，我是不正确见。当然，排列索引必须与行和列相同。我至少应该注意到，当我开始与自我连接图并获得一个没有他们排列后。

随机排列同构而是将这个样子：

idx = randperm(8); 
A(idx,idx); 

这将让所有的自我连接。

也许这可能在矩阵生成时有些用处，但它并不像我想象的那样有用。