具有指定边长的图形的弹簧/静电绘图的实现
假设我有一些非平面图 $G$ ，其边长 $(r_1,...,r_N) \in R$ 完全指定，但我没有指定顶点坐标。我想通过将边缘指定为一定长度的弹簧，在顶点之间具有静电斥力，然后执行类似于模拟退火的操作，在二维表面上绘制 $G$。
Mathematica 似乎具有上述所有功能，但它不允许您指定边长。是否有任何软件（无论是否属于公共领域）可以实现所有这些功能？我尝试过 Tulip 和 GraphViz。 Tulip 根本不允许您指定边长，而 Graphviz 在指定边长和为模拟退火步骤设置任何类型的参数方面的功能非常有限。
更新 - 我碰巧提前知道我的特定边长集有效！该图以前是在二维平面上绘制的，但我无法访问坐标。
我想我真的在寻找一个可以模拟球和弹簧的二维网络的包。分子动力学软件可以做到这一点，但开销是巨大的......
Suppose I have some non-planar graph $G$ with fully specified edge lengths $(r_1,...,r_N) \in R$, but where I do not have specified coordinates for the vertices. I want to draw $G$ on a two dimensional surface by specifying the edges as springs of some length, having electrostatic repulsion between the vertices, and then doing something akin to simulated annealing.
Mathematica seems to have functionality for all of the above, but it doesn't let you specify edge lengths. Is there any software, in the public domain or not, that does all of this? I've tried Tulip and GraphViz. Tulip simply doesn't let you specify edge lengths, and Graphviz has very limited functionality in terms of specifying edge lengths and setting any sort of parameters for the simulated annealing step.
Update - I happen to know ahead of time that my particular set of edge lengths work! The graph was previously drawn on a two-dimensional plain, but I don't have access to the coordinates.
I suppose I'm really looking for a package that can simulate a two-dimensional network of balls and springs. Molecular dynamics software can do this, but the overhead there is enormous...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
正如马克所说，你并不总是能做你想做的事。但是，我建议尝试 LevelScheme 绘制看起来像弹簧的波浪箭头。这是一个示例：
然后您可以通过单独更改箭头的波长来修饰它，这可以代表不同的波长弹簧的张力并添加代表顶点的小圆盘等。这是核物理中水平方案图的混用，但我想接近你想要的。
Like Mark said, it won't be always possible to do what you want. However, I would suggest trying LevelScheme to draw squiggly arrows which look like springs. Here's an example:
You can then embellish this by changing the wavelength of the arrows individually, which could represent different tension in the springs and add little disks that represent the vertices, etc. This is a bastardization of the level scheme diagrams in nuclear physics, but I guess is close to what you want.
没有理由期望能够做到这一点。例如，您无法将 4 个距离均相距的点放置在平面上。
There's no reason to expect to be able to do this. You can't place 4 points all distance one apart in the plane, for example.
好的，围绕我之前的答案的讨论清楚地表明 OP 具有有效的边长。在这种情况下，可以用代数方式指定问题，然后求解。这是执行此操作的一种方法。当然，在问题中给出具体的例子总是好的。缺少这一点，我们就可以生成该示例的要点。
这是一个有 10 个顶点和 20 条边的随机图。
我们把它画出来并提取出顶点位置信息。因此，我们将知道有效的长度。
对于具有这些长度的任何配置，以下表达式将为零。
不幸的是，这个表达很难被最小化。假设我们对原始顶点位置的估计不准确。 （也许这是可能的，也许不是。）我们可以这样模拟。请注意，我们只是随机扰动原始图片。
现在，以下应该会产生有效的顶点位置。
OK, the discussion surrounding my previous answer makes it clear that the OP has edge lengths that work. In this case, the problem can be specified algebraically and then solved. Here's one approach to doing that. Of course, it's always good to have a specific example stated in the question. Lacking that, we can generate the essentials of the example.
Here's a random graph with 10 vertices and 20 edges.
Let's draw it and extract out the vertex location information. Thus, we will know lengths that work.
For any configuration with those lengths, the following expression will be zero.
Unfortunately, the expression is quite hard to minimize. Let's suppose that we have inexact estimates of the original vertex locations. (Perhaps this is possible, perhaps not.) We could simulate this like so. Note that we are simply randomly perturbing the original picture.
Now, the following should yield vertex locations that work.
也许 郁金香 能满足您的需求？
Maybe tulip does what you want?
您也可以尝试自己实现。这并不难，而且很有趣。在这种情况下，“模拟退火”只是应用带有摩擦的静电物理。
关键点是使用Kd-Tree或八叉树来限制模拟的复杂度。否则 O(n²) 复杂度会打败你:)
You could also try to implement it yourself. It's not that hard and a lot of fun. "Simulated annealing" in this case is simply applying electrostatic physics with friction.
The key point is to use a Kd-Tree or an Octree to limit the complexity of the simulation. Otherwise O(n²) complexity will defeat you :)