图压实算法

一、定义

将一个原本较为稀疏的图布局，进行压实操作，从而提高画布空间利用率，便于用户理解。

二、适用场景

1. 图面积最小化：即移除多余的空间，将稀疏图变为紧密图。
2. 布局编译：从符号布局生成蒙版布局，电路板。
3. 重新设计：自动清除违反设计规则的情况。
4. 重新缩放：将蒙版级别的布局从一种技术转换到另一种。

在实际场景中，通常用于电路板的排版中。

三、操作

在压实操作中，可以通过控制以下因素来进行：

1. 节点之间的间隔
2. 节点的大小
3. 节点的形状

四、压实算法

1. 算法种类

算法根据考虑的因素不同分为两类：

• 第一类，基于最小化节点间的距离。

  • Constraint graph based，基于约束图
  • Virtual grid based，基于虚拟网格

• 第二类，基于节点的移动方向。

  • 1-D compaction
  • 2-D compaction
  • 1/1/2-D compaction

2. 基于约束图的压实

将节点之间的关联，构建成一个约束图 。约束条件一般分为两种：

2.1 最小距离约束（分隔约束）

即两个元件之间的最小距离，需要大于指定值。
指定最小距离为b，节点的最小宽度为a，则需要满以下约束条件：

构建约束图，

• 上图中每一个变量表示成约束图中的节点，
• 对于每个条件，换成为约束图的一条边，边的权重为。
• 新增一个额外的虚拟节点，0表示节点的x坐标是0，从而所有的节点都在该节点的右侧。
• 把所有的不等式条件约束，全都转化为最小距离约束，就会生成一个dag。

如上图最终生成的约束图为：

2.2 最大距离约束（关联约束）

即两个元件的距离，需要保持在一个指定范围内。满足，等价于
最大距离约束，在约束图中用反向边来表示。如下图：

• [ ]

3. 基于虚拟网格的压实

假设，节点的布局是在网格上进行的。每一个元件都在网格线上，两条平行相邻轴线之间的距离为，两个轴线上元素之间的最大间距。

通过移动轴线距离，来达到压实的目的。缺点: 最终生成的图的紧密程度较差，不如约束图的结果。

4. 切分网格压实

基于网格压实的进一步改进，即同一行或同一列上的节点可以进行拆分，拆分到不同的行列上。从而增加图的紧密性。

效果：

五、压实维度

1. 维度

• 一维，在一次压实操作中，元素的移动方向只能是水平或者垂直。通常会结合一次横向压实，一次纵向压实使用。
• 二维，即在压实操作中，元素可以同时在水平和垂直方向上发生移动。复杂度较高，NP问题

2. 一维（先x后y）

即通过两次一维压实组合，先进行水平方向上的压实，再进行垂直方向上的压实。

• 每个节点大小都是2*2，
• 节点间的最小间距是1，
• 初始布局容器大小是11*11，
• 优化完后大小是8*11

3. 一维（先y后x）

即通过两次一维压实组合，先进行垂直方向上的压实，再进行水平方向上的压实。

• 每个节点大小都是2*2，
• 节点间的最小间距是1，
• 初始布局容器大小是11*11，
• 优化完后大小是11*8

4. 二维

• 每个节点大小都是2*2，
• 节点间的最小间距是1，
• 初始布局容器大小是11*11，
• 优化完后大小是8*8

优点: 二维压实的效果很明显比一维的效果好。
缺点：耗时

5. 一又二分之一维

一维和二维方式的中间方案，在x轴压实操作中，考虑少量的y轴压实。
根据节点，以及节点之间的位置关系，构建X-Y邻接图。

• 如果两个相邻的节点在同一个水平线上，就在两个节点间增加一条水平线。
• 如果两个相邻的节点在同一个垂直线上，就在两个节点间增加一条垂直线。
• 线上的label，标记两个节点之间的最短距离。
• 分别在上下左右增加四个虚拟节点，以保证节点在一个限定范围内。

六、布局应用

上述布局是在电路排版中的应用到的算法，算法中会为了极致的缩小空间，从而损失掉一部分节点的相对位置信息，比如层次信息等。回归到正常图布局中（如建模ER图），可以借鉴一部分的方式，比如基于虚拟网格的一维压实操作。

七、参考资料

http://cas.et.tudelft.nl/~nick/courses/eda-0809/slides/04_compaction.pdf
http://www.doe.carleton.ca/~pavan/Public/Courses_files/04%20layout_compaction.pdf
https://www.youtube.com/watch?v=JHDuTYeOTZg