分层绘图模型(Layered graph drawing):也就是题主给出的图片所用的算法。分层绘图算法的本质很简单,就是算出每个节点在图中的“阶级”,然后按阶级从上向下(或者其他方向也行)依次画出各个节点以及连线。这个算法最适合的图的类型是有向无环图(Directed Acyclic Graph,简称 DAG),因为这样的图可以轻易用“与根节点的最大距离”(米尔斯基定理 Mirsky’s theorem)等方法来分配层级。如果图不是 DAG 的话,分层绘图算法会先通过某些 Heuristics(不要吐槽英文,这个真的不知道怎么说) 规则来发现并去掉一些违背 DAG 性质的连线,把原图变成一个比较接近原图的 DAG。分层绘图适用于跟有向无环图比较接近的节点图,缺点是环一多就比较容易乱包,而且对于无向图来说,找到适合绘图的根节点也比较困难。
力场绘图模型(Force-directed graph drawing):力场模型是这些年出来的数据可视化框架中比较受欢迎的一种算法。力场算法的本质就是给节点和连线之间、节点和节点之间赋予受力关系,然后对整个图的势能做最小化。最常见的力场模型是把节点模拟为带相同电荷的带电粒子(这样节点和节点之间就有了斥力,不会挤在一起),把连线模拟为弹簧(这样可以平衡节点间的距离)。当然力场绘图还有很多其他模型,也不只有势能最小化一种优化方法,但是鉴于这只是个简介我就不详述了。力场绘图模型相对分层模型的好处是处理环比较多的节点图,或者无向图的时候效果很出色,缺点是节点一多,最小化势能就非常困难。
如果要为这种算法归类的话,应该是属于最优化算法。给定一些约束(如节点间的最小距离),以及目标函数(如总边线距离最短等),找出最优解(如节点的位置)。
[1] Ellson, John, et al. "Graphviz and dynagraph—static and dynamic graph drawing tools." Graph drawingsoftware.SpringerBerlinHeidelberg,2004.127-148. http://www.researchgate.net/profile/Emden_Gansner/publication/216633938_Graphviz_and_Dynagraph_--_Static_and_Dynamic_Graph_Drawing_Tools/links/0fcfd5107f9a6280ef000000.pdf
知道一个力场绘图模型,来自这本书最后一章节优化部分, 线上有代码,不多。
Eloquent JavaScript :: Code Sandbox
(圆环图引用的是与关注关系图,我觉得很合适,哈哈)
最后无耻地说一句,最近正在学习d3.js,马上就要变得很厉害了,我就回答了一下。
形状为先的绘图模型:事实上这个名字是我编出来的,可视化里并没有这个术语。这里说的主要有两大类常见绘图模型,中心绘图和圆环绘图。顾名思义,中心绘图就是找到一个中心点,把其他所有节点都画成从中心节点发散出来的射线,而圆环绘图则是把所有的节点放在一个圆环上,连线都从圆环内部走。这两种模型的共同点都是形状为先,各只适用于某种特别的目的和特别的节点图类型。例子:(上面是中心绘图,下面是圆环绘图)




