生成所有具有 n 个顶点的有向无环图（DAG）。

Question

我希望能够生成所有具有n个顶点的DAG（有向无环图），在同构的情况下 - 也就是说，没有标记的DAG且没有重复。是的，我知道会有非常多这样的情况，但我的主要关注点是小数字（例如，n小于10），其中一切都还是可以处理的。

显然，添加所有可能的边组合等方法有两个主要缺点：

1. 这种方法比独特的图形生成更多的重复（同构），尤其是随着n的增加。
2. 每个生成的图形需要检查是否包含循环。

- BeeOnRope

---

请看：http://cs.stackexchange.com/questions/29552/enumerate-all-non-isomorphic-graphs-of-a-certain-size - Lior Kogan

据我所知，nauty只适用于无向图。理论上可以生成所有无向图，然后生成这些图的所有非同构定向，但是由于限制（如无循环），这种方法在实践中并不可行。 - BeeOnRope

Answer 1

你可以从一个简单完全图Kn开始，其中n是图的阶数，然后枚举它的生成树。 算法是一种修改过的DFS，它使用回溯并避免桥（以保持产生连接的树），同时探索所有可能的不同组合。

根据Cayley公式，在Kn上有n^(n-2)（其中^表示乘方）个生成树，因此您的最坏情况可能看起来像9^7=4782969，包括重复。

这也让人想起Motif Detection中的一个“子问题”，对于某些算法（或这个算法），目标是生成所有简单连通的图形（不仅限于树）的阶数n（motifs），以便将图分解为这些n个motifs。因此，那些文献对您也可能有所帮助。

希望这可以帮到您。

- A_A

---

主要问题是“有重复项”。我的问题表述不够清楚（我现在已经添加了澄清），但主要的技巧是避免大多数朴素方法中固有的重复项（即生成同构DAG）。此外，您对于n=9的估计似乎有误 - 的确，对于n=9，存在（没有重复项）20,286,025个无标签DAG - 已经超过了您的4,782,969个（其中有重复项） - 请参见[A003087]（https://oeis.org/A003087）。 - BeeOnRope

事实上，跨度树方法似乎行不通。例如，如何从（无向）跨度树转换为DAG？然后，如何将跨度树的边定向，以生成微不足道的“钻石DAG”，其中您有a -> {b，c}，{b，c} -> d？这样的DAG在其无向骨架中具有循环，因此我不明白如何定向树的边缘（没有循环）可以生成它。 - BeeOnRope

你能否用正则表达式捕获或规定问题，然后使用“反向”正则表达式生成所有可能的实现方式？（例如，请参见rstr（特别是Xeger部分）和exrex Python模块） - A_A

挺有趣的，但我怀疑正则表达式是否足够丰富，能够捕捉“连接”这样的概念？此外，似乎反向正则表达式方法并不能真正避免涉及同构的复杂图论问题，相比直接解决这些问题的方法。 - BeeOnRope

相对于“连接”，正则表达式是语法树的公式，因此它将始终生成连接的图形。 因此，像“f(f(x,y),y)”或“f(f(f(f(x,f(x,f(y)))))”这样的二元函数可以很容易地被正则表达式捕获。 挑战在于问题的制定。 至于“同构”，您当然是正确的，反向正则表达式是一种穷举搜索，但它不识别和避免对称以减少重复。 如果可能，请您添加这些详细信息到问题中。 - A_A