问题标签 [planar-graph]

我正在开发一个 c++ 程序，它计算和绘制所有可能的具有给定 E 数边的连接平面图。像这样 ：

我的第一个想法是通过在通过递归找到 (n-1) 的答案后添加一条边来找到 N 边的所有可能解决方案。

如图所示，n = 4 问题的解决方案基本上是解决方案 n = 3 的改进版本，多了一条边​​。

但这并不是一个非常有效的解决方案。我在特定算法中找不到这个问题。

有没有其他方法可以找到和绘制所有可能的带有 E 边缘的连接平面图？

我想编写一个算法，将图形作为输入，如果它是平面则返回 true，否则返回 false。我四处搜索，发现了大量的算法，但没有容易理解的实现。

有没有像 Boyer-Myrvold's 或 C++ 或 Java 中可用的任何其他实现，可以满足我的要求？

我有一个非常棘手的任务要解决：

给你一个 N * M 板（1 <= N，M <= 256）。您可以从每个字段移动到其相邻字段（不允许沿对角线移动）。一开始，有两种类型的字段：活动和阻塞。您可以通过活动场，但不能继续被阻止的场。您有 Q 个查询（1 <= Q <= 200）。有两种类型的查询：

1) 找到位于从字段 A 到 B 的最短路径上的下一个字段（与 A 相邻）

2) 将字段 A 从活动更改为阻塞或相反。

第一种查询可以用简单的 BFS 在 O(N * M) 时间内轻松解决。我们可以将活动字段和阻塞字段表示为 0 或 1，因此第二个查询可以在恒定时间内完成。

该算法的总时间为 O(Q (查询次数) * N * M)。

所以有什么问题？我有 1/60 秒的时间来解决所有的问题。如果我们将 1 秒视为 10^8 次计算，则剩下大约 1,5 * 10^6 次计算。一个 BFS 最多可能需要 N * M * 4 次，大约是 2,5 * 10^5。因此，如果 Q 为 200，则所需的计算可能高达 5 * 10^7，这太慢了。

据我所知，在这种情况下，没有比 BFS 更好的寻路算法（好吧，我可以选择 A*，但我不确定它是否比 BFS 快得多，它仍然是最坏情况 O(|E |) - 根据维基百科)。所以在这方面没有太多需要优化的地方。但是，我可以以某种方式更改我的图表以减少算法必须处理的边数（我不需要知道完整的最短路径，只知道我应该采取的下一步行动，所以剩下的最短路径可以非常简化）。我正在考虑一些预处理 - 将顶点分组并制作图形图，但我不确定如何以这种方式处理阻塞的字段。

我怎样才能更好地优化它？或者甚至有可能吗？

编辑：实际问题：我在板上有一些单元。我想开始将它们移动到选定的目的地。单位不能共享同一个领域，因此可以阻止其他人的路径或为他们开辟一条新的、更好的路径。可能有很多单位，这就是为什么我需要更好的优化。

基本上，我有一款游戏，其中包含 116 个地区的大地图。每个地区都有一个名称、一些其他属性以及一个关联的 String[] 及其邻居的名称。并非每个区域都相互连接（我认为一个区域至少有 1 个连接，最多有 9 个连接）。

因此，像图一样绘制区域应该会产生平面图。我尝试使用 JUNG 库（如本网站和其他网站上的建议）这样做，但他们拥有的每个布局算法只会导致一个有很多交叉边的图形，这正是我想要避免的。在我的代码下方（Territory 类再次具有 name 属性和其邻居名称的 String[]。传递给该方法的地图以区域名称作为键）。

所以我的问题是：有没有一种布局算法可以用来从领土地图中绘制平面图？我应该使用的另一个库？我可以遵循的教程？提前谢谢各位！

（使用 JUNG 库，我的进口清单：

game.getID() 方法是我在另一个类中编写的一种方法，用于将颜色（与区域相关，灰色、橙色、洋红色或蓝色）转换为整数。顶点也应该是我的代码实际完成的那种颜色！

我尝试使用以下布局：KKLayout、FRLayout、SpringLayout、ISOMLayout、CircleLayout。

在 d3.js 的帮助下，我尝试绘制一个力导向图的示例。

我有 3 个大问题。这是代码（您可以在下面运行代码片段，它可能有效）：

图像如下所示：

第一个问题是：如何避开这个路口？ 我知道我无法避开所有边缘交叉点，但我想尽量减少它们。这个例子是一个没有循环的树形图。我知道有一种方法可以在没有边缘交叉的情况下构建它。但我不知道如何用这个算法来做到这一点。
但还是烦人的路口。

第二个问题是：不及时模拟力（我不需要动画）而只是绘制最终结果怎么办？当我使用forceSimulation.on("end", cb)它时很好，但是启动和停止之间的延迟很大..但这只是一个小例子。我等不及要大一次了。

第三个问题是..如何应用强制定向设置？力能，刚度，排斥力，阻尼等？在 d3@5 上找不到它们

我的项目负责人想要的最终结果是：

• 没有节点重叠；
• 最小化边-边交叉点；
• 最小化边缘节点的交叉点。

我准备好对话了。

有人可以用一个例子向我解释 Borradaile-Klein 的最大流量算法是如何工作的吗？ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6392&rep=rep1&type=pdf

有很多 Ford-Fulkerson 的示例（https://www.youtube.com/watch?v=Tl90tNtKvxs），但我没有找到 Borradaile-Klein 算法的示例。

谢谢你。

我正在尝试编写一种算法来获取无向图的面。我在输入中收到的图形已知是平面的和双连接的。但是，图形的邻接列表没有以任何方式排序（顺时针或逆时针）。

我已经对该主题进行了一些研究，一些 StackOverflow 线程建议对图形进行平面嵌入。我找到了这篇文章：Efficient Planarity Testing，由 Tarjan 和 Hopcroft 撰写。本文介绍了边缘加法算法。

另一方面，我发现仅验证图形的平面性的代码非常费力。我不想画图，我不在乎是否有很多嵌入，我只想列出我的图的面。为此，我需要一种方法来订购我的边缘。然而，文章本身并没有指定任何顺时针排序，但它确实显示了一个子进程，其工作是对边缘进行排序（第 5 节，第 8 页），它似乎不是顺时针排序，而是按它们的 LOWPT 值排序.

我的问题是：是否有任何算法可以对我的边缘进行排序，或者我是否必须生成图形的平面嵌入，我已经知道它是平面和双连接的？

谢谢

我有一个顶点列表，我知道它们之间的连接。我试图找到顶点的所有多边形。这些多边形不应重叠。

我做了一些研究，我认为我可以检测多边形形状，如果我可以顺时针遍历顶点，（或逆时针，没有区别）。所以，我寻找解决方案以顺时针遍历顶点。我发现了一个类似的主题并尝试了建议的解决方案。但问题是在遍历顶点时，当有多个顺时针选项时，我无法决定选择哪条路径。

基本上，我想找到以下多边形：

当我从 A 开始然后到达 E 顶点时，我如何决定选择 G 路径？

PS：如果我的方法不适合这个问题或者有更好/更简单的解决方案，我愿意接受与我不同的方法

有没有办法使用 C# 的 QuickGraph 来查找图形的面，类似于 Boost C++ 图形库中的平面面遍历函数？

https://www.boost.org/doc/libs/1_51_0/libs/graph/doc/planar_face_traversal.html

我正在构建一个视频游戏，其中一个 2D 平面图是边接边构建的，并且在任何给定点都需要知道图形的面。“面”是指在 2D 平面上没有任何边穿过它们的图形循环。

我知道循环基础并实现了它并取得了很好的结果，但我想知道是否有算法/数据结构在构建一组面的同时保持不变，同时也在构建图形。

作为参考，这是我在YouTube 上找到的视频。

我希望了解如何/是否可以在每次向图中添加一条边时进行最少的计算。我还尝试查看 2D 平面图的半边和翼边实现，但到目前为止我还没有发现任何可以让我深入了解这一点的东西。非常感谢！