在可视化动态图时保留心理地图

2023 年 6 月 12 日

此处介绍的工作是作为 Oracle、乌普萨拉大学和 KTH 之间的联合研究项目的一部分进行的。关注 inside.java 上的博客系列，以了解更多关于在斯德哥尔摩的 Oracle 开发办公室进行的 JVM 研究。

C2 Java 编译器中的中间表示方法

我叫 Emmy Yin，目前正在 KTH 完成我的理论计算机科学工程学位。在 2023 年春季，我有机会在 Oracle 撰写我的硕士论文。我的论文围绕 理想图可视化器 (IGV) 展开，目的是探索用于可视化动态图的图布局算法。

在 Oracle 撰写我的论文是一次有意义的经历。我要感谢 Oracle 斯德哥尔摩和苏黎世的员工。我在项目中真正学到了很多东西。特别感谢 Roberto Castañeda Lozano 和 Tobias Holenstein 在整个论文过程中指导我！

背景

IGV 是一种图可视化工具，是 OpenJDK 的一部分。它被开发出来帮助工程师理解、调试和增强 OpenJDK 的主要即时 (JIT) 编译器 C2。JVM 将正在编译的程序表示为动态中间表示 (IR) 图，该图在程序编译时会发生变化。IGV 是用于可视化 IR 图的工具。更多信息可以在这里找到 这里。为了可视化图形，IGV 使用静态图形布局算法。这意味着仅考虑要可视化的图形的当前状态，而不考虑为获得图形而发生的任何更改。好处是算法可以专注于绘制高质量的布局，易于阅读和理解。然而，缺点是图形的微小变化会导致重大重新布局，难以看到实际发生的更改。

让我们用一个例子来说明这一点。图形 G 可视化如下：

节点被分组到层中，以便从最顶层向下流动。在此布局中，我们总共有九层，节点 7、405、105 和 467 在最顶层，节点 334 在最后一层。

一个节点与一条边一起添加到图形中，创建一个新的图形 G'。静态算法绘制 G' 的布局如下，其中添加的节点用红色圆圈标出：

乍一看，布局看起来非常相似。但是，当更仔细地分析它们时，可以注意到每层中节点的顺序发生了变化。节点重新排序的原因是为了最大限度地减少边交叉，使布局稍微更容易阅读。然而，重新排序可能会误导和混淆查看者。

动态图布局算法

在我的论文中，我实现了一个动态布局算法作为静态算法的替代方案。该算法背后的想法是逐步对先前布局应用更新操作以获得新布局。算法的步骤是

  1. 识别先前图形状态和新图形状态之间的所有更改。
  2. 将更改划分为一系列更新操作。每个操作都是以下之一
    • 增加节点大小
    • 删除节点
    • 添加节点
    • 删除边
    • 添加短边（相邻层节点之间的边）
    • 添加长边（跨越多层的边）
    • 添加同一层节点之间的边
  3. 按以下顺序应用操作
    1. 调整节点大小
    2. 删除节点和边 3. 添加节点
    3. 添加边
  4. 可视化结果布局

因此，先前布局和新布局中都出现的节点的相对位置得以保留。继续上面的例子，动态算法绘制的 G' 布局如下所示。同样，添加的节点用红色圆圈标出。

很明显，图形 G 布局中节点的顺序得以保留，这使得更容易识别 G' 中添加的节点。

比较算法

我在大量图形上运行了这两种算法，以评估和比较它们。结果表明，动态布局算法移动节点的次数更少，从而导致布局更具动态稳定性。对于具有少量更改的小图形，结果很强。但是，随着图形大小的增加或更改过大，稳定性下降。关于布局质量，似乎动态算法会导致更多边交叉、反向边、弯曲程度更大的边以及总体上更长的边。这意味着与静态算法绘制的布局相比，布局更加杂乱，更难阅读。

结论

当预期更改较小或查看者优先考虑动态稳定性时，动态算法可能是更好的选择，而当布局质量很重要时，静态算法很有用。布局质量和动态稳定性之间存在权衡，这可能值得进一步探索。