类似Graphviz的工具是怎么样自动排版的?
发布网友
发布时间：2022-06-05 11:09
共2个回答
热心网友
时间：2023-11-18 05:16
分层绘图模型（Layered graph drawing）：也就是题主给出的图片所用的算法。分层绘图算法的本质很简单，就是算出每个节点在图中的“阶级”，然后按阶级从上向下（或者其他方向也行）依次画出各个节点以及连线。这个算法最适合的图的类型是有向无环图（Directed Acyclic Graph，简称 DAG），因为这样的图可以轻易用“与根节点的最大距离”（米尔斯基定理 Mirsky's theorem）等方法来分配层级。如果图不是 DAG 的话，分层绘图算法会先通过某些 Heuristics（不要吐槽英文，这个真的不知道怎么说） 规则来发现并去掉一些违背 DAG 性质的连线，把原图变成一个比较接近原图的 DAG。分层绘图适用于跟有向无环图比较接近的节点图，缺点是环一多就比较容易乱包，而且对于无向图来说，找到适合绘图的根节点也比较困难。
力场绘图模型（Force-directed graph drawing）：力场模型是这些年出来的数据可视化框架中比较受欢迎的一种算法。力场算法的本质就是给节点和连线之间、节点和节点之间赋予受力关系，然后对整个图的势能做最小化。最常见的力场模型是把节点模拟为带相同电荷的带电粒子（这样节点和节点之间就有了斥力，不会挤在一起），把连线模拟为弹簧（这样可以平衡节点间的距离）。当然力场绘图还有很多其他模型，也不只有势能最小化一种优化方法，但是鉴于这只是个简介我就不详述了。力场绘图模型相对分层模型的好处是处理环比较多的节点图，或者无向图的时候效果很出色，缺点是节点一多，最小化势能就非常困难。
热心网友
时间：2023-11-18 05:16
形状为先的绘图模型：事实上这个名字是我编出来的，可视化里并没有这个术语。这里说的主要有两大类常见绘图模型，中心绘图和圆环绘图。顾名思义，中心绘图就是找到一个中心点，把其他所有节点都画成从中心节点发散出来的射线，而圆环绘图则是把所有的节点放在一个圆环上，连线都从圆环内部走。这两种模型的共同点都是形状为先，各只适用于某种特别的目的和特别的节点图类型。例子：（上面是中心绘图，下面是圆环绘图）
