1. 概述
本文将探讨多种图（Graph）布局设计技术。
我们会首先了解在绘制图时应遵循的便利性和美观性原则，然后探讨图的多种替代表示方式。
最后，我们将研究两种在平面上自动布局图的算法。
学完本文后，你将熟悉图布局设计的标准，并掌握如何自动绘制图。
2. 图在平面上的表示
2.1. 表示、人类感知与意义
图的表示问题与“图像在人类感知中需要被解释才能产生理解”这一理念相关。图像本身是对现实世界对象的抽象表示，使观察者能够在脑海中唤起这些对象：
然而，由于其固有的多样性，代表同一现实世界对象的不同图像可能在读者脑海中唤起不同的心理对象。如果我们把图像视为现实世界对象的映射 
，使得 
，我们可以认为这个映射 是满射（surjective）的，因为多个图像可以映射到同一个现实。
这就是那句老话“地图不是领土”的含义。如果我们把这个观点扩展到图上，可以说“图像不是图，图也不是领土”。
我们知道，图 
可以表示为顶点集合 
和边集合 
。我们也知道存在多种图的表示方法，例如：
- 边列表（Edge List）
- 邻接矩阵（Adjacency Matrix）
- 邻接表（Adjacency List）
在本节中，我们使用一个示例有向图 
，其邻接表如下：
除非另有说明，否则边列表不会改变。我们很快将看到如何以多种方式表示同一图，以及这些表示方式对理解的影响。
2.2. 但那不就是个图吗！
我们也可以不同意前面提出的概念框架。我们可以天真地认为，任何对图的任意表示都与其他表示一样具有信息量。
这被称为朴素现实主义（naive realism）的理论，它指出，无论感知对象是什么，人类都能立即理解它，而不需要任何预处理或先验偏见：
该理论还暗示，随后，任何两个人在感知同一对象时都会获得相同的理解：
然而，这一理论已经被理论推理和实证研究证伪，尤其是在图和图表的理解方面。这也意味着，当我们绘制图时，使用的技巧确实会影响读者的理解。
3. 几何约束
3.1. 什么是几何约束？
图的表示首先受到我们对其施加的几何约束限制。这是因为，如果我们不选择任何约束，那么存在无限多种可能的表示方式，每种方式都对应于某种特定的边和节点位置组合。相反，如果我们施加某种限制，就可以选择一个在这些约束下最能增强图可视化的表示方式。
存在多种类型的约束：
- 最小化图所占的水平或垂直空间
- 最小化总表面积
- 最有趣的是对边的放置或形状的限制
我们可以研究相对于前面示例图，存在哪些类型的边几何约束。
3.2. 平面直线图（Planar Straight-Line Graphs）
我们只讨论平面图，因为这类图的约束更容易理解。平面图是指所有顶点和边都位于同一二维平面上，且边之间不交叉的图。
我们施加的第一个限制是：所有边必须是连接顶点的直线段：
这种表示方式称为平面直线绘制（planar straight-line drawing）。这种图便于识别顶点之间的环路，因为它们通常位于绘制区域的同一部分。
3.3. 正交图（Orthogonal Graphs）
我们也可以限制所有线条、边或其部分必须正交或平行于其他边：
这种表示方式称为正交绘制（orthogonal drawing）。正交图强调每个顶点的度数，因为很容易计算与之相连的边数。其主要限制是：如果至少有一个顶点的度数 
，则无法用正交方式表示该图。
3.4. 正交且直线图（Orthogonal and Straight-Line Graphs）
我们也可以绘制一个同时符合正交性且边为直线的图。由于我们使用的特定图无法实现这种表示，这次我们去掉第一个节点的两条边：
这种图称为平面正交直线图（planar orthogonal straight-line graph）。这种技术强调图的“面”（faces），即由图的边围成的有限区域，包括包围它们的无限区域。
3.5. 向上流动图（Upward Flow Graphs）
我们也可以以突出顶点之间方向流动的方式表示图：
由于边的流动方向向上，这种图称为向上平面图（upward planar graph）。在文献中有时也称为分层网络（hierarchical networks），因为它们常用于表示组织中的层次结构。但需要注意的是，“分层网络”其实是一个误称，因为真正的分层网络具有无标度特性（scale-free properties），而向上图不一定具有这些特性。
3.6. 非平面图中的约束
我们在这里看到的是用于指导图结构选择的主要几何约束。请注意，选择平面图作为示例只是为了说明方便，非平面图也可以共享相同类型的约束。在这种情况下，图需要表示在超曲面（hypersurface）中，而不是二维平面中。
有趣的是，在三维空间中，正交直线图允许任一顶点最多有 6 条边。这意味着，如果图的某个顶点最多有 6 条边但不超过 4 条，则我们可以考虑将其表示为三维正交直线图。
4. 图表示的美学标准
4.1. 什么是美学？
我们还需要一些标准来决定在特定约束下使用哪种具体配置。这些标准被称为美学（aesthetic），因为它们表明图的表示不应仅仅是准确的，还应在观察者的审美中具有吸引力。
这些美学标准与前面讨论的几何约束一起，决定了我们最终选择哪种表示方式。
4.2. 最小化边交叉（Minimization of Edge Crossings）
第一个美学标准是最小化边之间的交叉次数。该标准建议：如果图有多种表示方式，应选择边交叉最少的那一种，以提高可读性：
在这种情况下，我们更倾向于右侧的表示方式。
4.3. 最小化图面积（Minimization of Graph Area）
第二个标准是最小化图所占面积。这个标准在应用时有一定的灵活性，因为图的可读性和面积紧凑性之间必然存在权衡。
看这个例子：
这三个图是等价的。右侧图占用面积过大，而中间图可能难以阅读（特别是视力有问题的读者）。左侧图则在面积最小化和可读性之间取得了良好的平衡。
4.4. 最小化边弯曲（Minimization of Bends）
第三个标准是最小化正交图中边的弯曲次数。理论上，弯曲次数可以任意增加：
但该标准建议应尽量保持边的弯曲次数最少：
4.5. 最大化最小角度（Maximization of the Smallest Angle）
下一个标准指出：图中任意两条边之间的最小角度应尽可能大。来看一个 4 阶图：
在这个图中，最小角度是边 !(1,2) 和 !(1,4) 之间的角 
。通过重新定位顶点，可以增大这个角度：
因为 
，根据该美学标准，第二种表示方式更优。
4.6. 最大化显示对称性（Maximization of the Shown Symmetries）
最后一个标准是显示图中存在的最大对称性。看这个例子：
此图满足边交叉最小化的美学标准（无边交叉），并显示了等边三角形的三条对称轴。我们可以通过将顶点排列为正方形来增加对称轴数量：
根据该标准，第二种表示更优。需要注意的是，并非总能同时满足多个美学标准。因此，当多个标准对图的表示都很重要时，我们可能需要在它们之间做出取舍。
5. 自动布局算法
在了解了几何约束和美学标准后，我们可以寻找能够根据这些约束和标准自动在平面上放置节点的算法。这些算法大致分为以下几类：
- 树绘制算法（Tree Drawing Algorithms）
- 基于力的算法（Force-Based Algorithms）
- 弯曲最小化算法（Bend Minimization Algorithms）
- 支配绘制算法（Dominance Drawing Algorithms）
本文将重点介绍前三类算法。
5.1. 二叉树递归布局算法
如果我们要绘制的是二叉树，可以使用递归算法来将节点分布在水平层级中：
这是该算法生成的一个树示例：
5.2. 基于力的算法（Force-Based Algorithms）
对于一般类型的图，我们可以使用基于力的算法。这些算法的核心思想是：图中的边像弹簧一样拉动顶点，图的表示是使系统势能最小的状态。
在物理学中，弹簧具有平衡长度，当被压缩或拉伸时，会施加与变形量成正比的力。在图论中，我们可以将边视为平衡长度为零的弹簧，其施加的力与长度成正比：
因此，每个顶点都会受到其边长度决定的力的作用。顶点会沿着这些力的合力方向移动。如果我们固定某些顶点的位置，就可以运行这个动态系统。
例如，我们固定顶点 2 和 3，移动顶点 1：
5.3. 弯曲最小化与网络流（Bend Minimization and Network Flow）
另一种用于将图转换为正交图的算法是弯曲最小化算法。我们首先从任意平面图开始：
然后将其转换为高可见性形式，即将顶点转换为平行的水平线：
接着，将每个顶点放在对应线上的任意位置，并用弯曲边替换多余的线段：
最后，我们可以拉直这些弯曲，从而最小化它们：
如果我们将顶点位置限制在笛卡尔平面的整数坐标上，该算法可以在 
时间内计算。
6. 总结
在本文中，我们学习了图布局绘制背后的基本原理。
我们了解了图表示如何影响人类的理解，以及不同表示方式对图的解释带来的差异。
我们还学习了几种常见的几何约束和美学标准，并探讨了它们在图可视化中的作用。
最后，我们介绍了几种自动布局图的算法，包括递归布局、基于力的布局和弯曲最小化算法。这些算法可以帮助我们更高效地实现图的自动可视化。