s.b*_*ara 6 algorithm graph-algorithm
我想创建具有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的存储库？