5

在一个系统中，我有一个节点列表，这些节点像普通图中一样连接。我们了解整个系统及其所有联系，我们也有一个起点。我所有的边缘都有一个方向。

现在我想自动绘制所有这些节点和边。问题不是实际绘图，而是计算 (x,y) 坐标。所以基本上我想画出整个图表，这样看起来不错。

我的数据结构将类似于：

class node:
string text
List<edge> connections

这个问题一定有一些众所周知的算法吗？我找不到任何东西，但我可能使用了错误的关键字。

我的想法：

一种方法是将我们的起始节点定位在 (0,0)，然后有一些常数，即“距离”。然后对于每个邻居，它会将距离添加到 y 位置，并且对于作为邻居的每个节点，设置 x= distance*n。

但这确实会带来很多问题——所以这绝对不是要走的路。

4

2 回答 2

10

到目前为止，最常见的方法是使用强制导向布局而不是确定性布局。要点是每个节点都相互排斥（反重力），并且任何连接的节点对相互吸引。经过几次物理模拟迭代后，您可以获得合理的布局。

您可以使用许多布局算法，但结果大相径庭。GraphViz fdp ( Fruchterman & Reingold '91 ) 和neato ( Kamada & Kawai '89 ) 算法有效，但相当陈旧，还有更好的替代方案。Fruchterman & Reingold '91算法也可用于NetworkX中的Python 。

Prefuse提供了一个非常快速和良好的ForceDirectedLayout Java 类。Hachul & Jünger '05详细介绍了 FM^3 算法，该算法在实践中似乎做得相当好（Hachul & Jünger '06 ），并且在Tulip的 C++ 中可用。

还有大量其他开源工具可以可视化图表，例如 NodeXL (C#)，这是一个很棒的入门工具，将网络分析集成到 Excel 2007/2010 中（免责声明：我是它的顾问）。其他很棒的工具包括Gephi (Java) 和Cytoscape (Java)，而Pajek、UCINet、yEd和Tom Sawyer是一些专有的替代品。

于 2012-10-25T16:37:36.840 回答
2

一般来说，这是一个棘手的问题，特别是如果你想开始处理边缘路由并使事情看起来很漂亮。您可以查看http://www.graphviz.org/并使用他们的命令行工具，或使用 graphviz 库进行布局并在应用程序中获取 x,y 坐标。

于 2012-10-24T18:18:51.670 回答