一、定義
将一個原本較為稀疏的圖布局，進行壓實操作，進而提高畫布空間使用率，便于使用者了解。
二、适用場景
- 圖面積最小化：即移除多餘的空間，将稀疏圖變為緊密圖。
- 布局編譯：從符号布局生成蒙版布局，電路闆。
- 重新設計：自動清除違反設計規則的情況。
- 重新縮放：将蒙版級别的布局從一種技術轉換到另一種。
在實際場景中，通常用于電路闆的排版中。
三、操作
在壓實操作中，可以通過控制以下因素來進行：
- 節點之間的間隔
- 節點的大小
- 節點的形狀
四、壓實算法
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）
即通過兩次一維壓實組合，先進行垂直方向上的壓實，再進行水準方向上的壓實。
- 優化完後大小是11*8
4. 二維
- 優化完後大小是8*8
優點: 二維壓實的效果很明顯比一維的效果好。
缺點：耗時
5. 一又二分之一維
一維和二維方式的中間方案，在x軸壓實操作中，考慮少量的y軸壓實。
根據節點，以及節點之間的位置關系，建構X-Y鄰接圖。
- 如果兩個相鄰的節點在同一個水準線上，就在兩個節點間增加一條水準線。
- 如果兩個相鄰的節點在同一個垂直線上，就在兩個節點間增加一條垂直線。
- 線上的label，标記兩個節點之間的最短距離。
- 分别在上下左右增加四個虛拟節點，以保證節點在一個限定範圍内。
六、布局應用
上述布局是在電路排版中的應用到的算法，算法中會為了極緻的縮小空間，進而損失掉一部分節點的相對位置資訊，比如層次資訊等。回歸到正常圖布局中（如模組化ER圖），可以借鑒一部分的方式，比如基于虛拟網格的一維壓實操作。