6

我想创建具有n个顶点的所有有向图的集合，其中每个顶点有k个直接后继和k个直接前任。n和k不会那么大，而是在n = 8 和k = 3 左右。该集合包括循环图和非循环图。每个图依次将用作对大量加权图进行采样的模板。

我的兴趣是拓扑基序的作用，所以我不想为任何两个彼此对称的图采样权重，其中对称意味着一个图中不存在顶点排列，将其转换为另一个图。

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

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

任何人都可以向我推荐一种我可以阅读的算法，它可以以更智能的方式完成所有这些工作吗？是否有用于 C、C++、Java 或 Python 的图形库已经实现了如此全面的图形生成器？是否有一个存储库，其中有人已经“列出”了合理n和k的所有图表？

4

2 回答 2

1

这更像是评论而不是答案，因为我似乎错过了您的问题中的某些内容。

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

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

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

 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。在这种情况下，我重复了几次该命令，以获得对角线中只有零的矩阵。:)

编辑

Ah, I see from your comments that I was not correct. Of course the permutation index must be the same for rows and columns. I at least should have noticed it when I started out with a graph with self-connections and obtained one without them after the permutation.

A random isomorphic permutation would instead look like this:

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

which will keep all the self-connections.

Perhaps this could be of some use when the matrices are generated, but it is not at all as useful as I thought it would be.

于 2013-01-18T16:13:30.833 回答
1

在我看来，图同构不是你应该考虑自己实现的东西。我相信当前最先进的是 Brendan McKay 的Nauty（以及相关的程序/库）。使用它有点麻烦，但避免做你自己的、幼稚的图同构可能是值得的。此外，它主要面向无向图，但它也可以处理有向图。您可能想查看Nauty附带的 geng（生成无向图）和directg（在给定基础图的情况下生成有向图）实用程序。

于 2013-01-18T17:20:26.297 回答