从连接节点列表中绘制图形

Question

在一个系统中,我有一个节点列表,它们像普通图一样连接.我们知道整个系统及其所有连接,我们也有一个起点.我所有的边都有一个方向.

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

我的数据结构类似于:

class node:
string text
List<edge> connections

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

我的想法:

一种方法是将我们的startnode定位在(0,0),然后得到一些常量,即"距离".然后,对于每个邻居,它将向y位置添加距离,并且对于作为邻居的每个节点,设置x =距离*n.

但这确实会带来很多问题 - 所以这肯定不是要走的路.

Answer 1

到目前为止,最常见的方法是使用力导向布局而不是确定性布局.要点是你让每个节点相互排斥(反重力)并让任何连接的节点对彼此吸引.经过几次物理模拟迭代后,您可以获得合理的布局.

您可以使用许多布局算法,结果大不相同.该GraphViz的 FDP(Fruchterman&莱因戈尔德'91)和NEATO(镰田川井和89年)的算法工作,但都比较老有更好的替代品.该Fruchterman&莱因戈尔德'91算法也是在Python中可供NetworkX.

Prefuse提供了一个非常快速和良好的ForceDirectedLayout Java类.Hachul和Jünger'05详细介绍了FM ^ 3算法,该算法在实践中表现得相当不错(Hachul&Jünger'06),并且在Tulip的 C++中可用.

还有大量其他开源工具可视化图形,如 NodeXL(C#),这是一个很棒的入门工具,它将网络分析集成到Excel 2007/2010中(免责声明:我是它的顾问).其他真棒工具包括Gephi(JAVA)和Cytoscape中(爪哇),而Pajek,UCINET,YED和汤姆·索亚是一些专有的替代品.