图压实算法-阿里云开发者社区

开发者社区> 云原生> 正文
登录阅读全文

图压实算法

简介: ## 一、定义 将一个原本较为稀疏的图布局,进行压实操作,从而提高画布空间利用率,便于用户理解。 ## 二、适用场景 1. 图面积最小化:即移除多余的空间,将稀疏图变为紧密图。 1. 布局编译:从符号布局生成蒙版布局,电路板。 1. 重新设计:自动清除违反设计规则的情况。 1. 重新缩放:将蒙版级别的布局从一种技术转换到另一种。 在实际场景中,通常用于电路板的排版中。

一、定义

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

二、适用场景

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

在实际场景中,通常用于电路板的排版中。
image.png

三、操作

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

  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,则需要满以下约束条件:

image.png


构建约束图,

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

如上图最终生成的约束图为:
image.png

2.2 最大距离约束(关联约束)

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

  • [ ] image.png

3. 基于虚拟网格的压实

假设,节点的布局是在网格上进行的。每一个元件都在网格线上,两条平行相邻轴线之间的距离为,两个轴线上元素之间的最大间距。
image.png
通过移动轴线距离,来达到压实的目的。缺点: 最终生成的图的紧密程度较差,不如约束图的结果。


image.png

4. 切分网格压实

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

五、压实维度

1. 维度

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

2. 一维(先x后y)

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

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

image.png

3. 一维(先y后x)

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

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

image.png

4. 二维

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

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

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: