结合多人输入的智能图布局算法

---

在此工作中我们提出了一个基于拉普拉斯变换的图布局保持算法。该工作能自动生成初始图布局，允许用户在图中任意选取子图并进行个性化编辑。收集多用户编辑的子图，对这些子图进行合理的缩放，保存子图中任意两点间的距离，结合图的初始布局运用拉普拉斯子图保持算法得到结合了多用户输入的更满足用户需求、易于理解的图布局。如下图所示，用户定义了许多形状各异的子图，该算法可以有效的解决子图编辑冲突，以及将编辑过的子图布局融入到初始布局中，衔接处流畅自然，而且子图布局保持效果非常好。图中数字表示经过算法融合后的子图布局与用户输入的子图布局的相似度，完全一样为100%.

由于在实际问题中，人们对图布局总有些特殊要求，而大部分自动的布局算法无法嵌入用户自定义的子图布局。受图形学领域有关边缘融合工作的启发，我们提出了基于拉普拉斯变换的距离内嵌子图保持算法（Laplacian Constrained Distance Embedding algorithm, 即LCDE）。我们把用户定义的子图结构当作布局算法要考虑的限制条件，做优化时要优先保持用户输入的子图结构。对于初始布局我们采用拉普拉斯矩阵来描述图的拓扑结构和节点间的相对位置，对于用户编辑过的子图，我们对其中的任意两点记录其欧拉距离，若两点间无边相连，则构建虚拟边，如下图(c)中红色虚线。下图中(a)是一个简单的图，(b)是其对应的拉普拉斯系数矩阵，(c)中红色节点为用户编辑过的子图节点，图中的虚线表示虚拟边，(d)是加入子图信息的拉普拉斯系数矩阵。

最后我们采用共轭梯度算法求解如下目标方程的最优解，得到尽量满足子图布局限制的新的图布局。

为了对比LCDE的算法效果，我们还提出了CFDP，即有限制的力导向算法（Constrained Force Directed Placement algorithm）,此算法是将用户编辑题图中节点间的相对距离作为力导向算法中节点间的理想距离。由于CFDP是通过限制节点间的理想边长来间接保持子图布局的，其算法效果没有LCDE更精准。从下面的案例中我们也可以看到LCDE要明显由于CFDP算法。

这是一个生化代谢反应图。(a)中的左图为教科书上的代谢过程图，中间为维基百科上对于呼吸作用和光合作用代谢图的布局，右图为用户参照维基百科对子图进行编辑的结果,(b)是采用力导向自动算法得到的布局效果,(c)采用CFDP算法，(d)采用LCDE算法布局，数字表示保持住的子图与用户输入子图的相似度。可见拉普拉斯布局保持算法效果明显由于有限制的力导向算法，且子图保持率非常高。

基于此算法，我们还开发了北京大学智能图布局编辑软件，该软件可以自动生成图布局，并且允许用户交互的对子图进行编辑，还提供了算法参数调节和边捆绑等功能。

视频

文章

软件下载

使用说明

引用

Xiaoru Yuan, Limei Che, Yifan Hu, and Xin Zhang . Intelligent Graph Layout Using Many Users’ Input. IEEE Transactions on Visualization and Computer Graphics (InfoVis’12), 18(12):2699-2708, 2012.