生成一个大的随机平面图

Question

生成一个大的（〜300k顶点）随机平面图（这里的“随机”意味着均匀分布）的最有效方法是什么？

Answer 1

那么一种方法是尝试生成一个满足与平面图形类似的约束条件的随机图（例如，边< = 3 *顶点-6）并检查它是否在O（n）时间内是平面的Tarjan的平面度测试算法。如果它不是平面的，则再次生成。不知道这对300K顶点有多高效！（或者它甚至会给你统一概率的图表）。

有一些关于生成平面图的文献，我可以在这里找到一篇文章：Generating Labeled Planar Graphs这显然具有预期的O（n^4）运行时间，并且可能不值得。也许那里的参考资料会帮助你找到可能有用的东西。

祝你好运！

Answer 2

没有任何其他的要求，我会说查找随机迷宫一代。如果你想在图表中循环，从一个简单的迷宫中随机移除一些墙。迷宫中的交叉点成为图形中的节点，被移除的墙壁是边缘。这意味着您可以通过选择迷宫的大小来选择节点的数量。

迷宫通常在2d网格上完成，最多有4个连接从一个点到另一个点，但没有任何东西阻止您在六角形瓷砖上做迷宫或其他事情。

Answer 3

如果通过统一你的意思是均匀分布在空间中，那么这是一个相当快的算法，我开发的用于生成空间生态/进化模拟器的平面图。它会生成具有您指定的期望程度的随机平面图，当然还有其周围的一些变化。你可以扩展它来选择基于统一的随机数的期望程度，而不是你想要在你的平面图中统一随机度。

https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py

Answer 4

另一种可能性在于，随机选择坐标，然后计算Delaunay三角网，它是一个平面图形（和看起来不错以及）。见http://en.wikipedia.org/wiki/Delaunay_triangulation有O（n log（n））算法来计算这种三角测量。

Answer 5

你看了玻尔兹曼抽样吗？请参阅Eric Fusy的文章“线性时间内平面图的均匀随机采样”。这篇文章和实现可以在他的homepage中找到，这篇文章说可以在几秒钟内生成大小为100K的实例。