边约束和对称约束下的枚举图

Question

我想要创建所有有向图的集合，其中每个顶点都有k个直接继承者和k个直接前辈。N和k不是那么大，而是n=8和k= 3。集合包括循环图和无圈图。每一张图依次作为抽样大量加权图的模板。

我感兴趣的是拓扑学主题的作用，所以我不想对任何两个对称图的权值进行采样，其中对称性意味着在一个图中不存在顶点的排列，并将其转化为另一个图。

一个简单的解决方案是考虑2^ (n *(n-1))邻接矩阵，并消除所有违反直接后继或前任约束的矩阵(大多数)。对于n= 8，这仍然是足够少的位来表示，并且简单地在一个uint64_t中简单地枚举每个矩阵。

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

有人能给我推荐一种我能读懂的算法吗?它能以一种更聪明的方式完成这一切吗？是否有一个用于C、C++、Java或Python的图库已经实现了这样一个全面的图形生成器？是否有一个存储库，其中某人已经为合理的n和k“列表”了所有图？

Answer 1

在我看来，图同构不是你应该考虑实现自己的东西。我认为目前最先进的是布兰登·麦凯的诺蒂 (以及相关的程序/库)。这是一个有点熊的工作，但它可能是值得的，以避免做你自己的，天真的图同构。而且，它主要面向无向图，但也可以做有向图。您可能需要查看Nauty附带的geng (生成无向图)和directg (生成给定基础图的有向图)实用程序。

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

从这个矩阵开始，难道就不可能改变它的行和列，从而得到所有行和列之和为3的所有这样的图吗？

从上述矩阵A中可以得到这样一个矩阵的示例(使用MATLAB)。

>> 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);

这将保持所有的自我联系。

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