工作流设计器之自动布局


第 21 章 自动布局

21.1. 排序

排序的过程中要解决闭环,遇到闭环就要将循环入口的连线设置为反向,就是将一个闭环修改为并发形式。

首先准备三个变量:已排序列表,待排序列表,被设置为反向的连线列表。

找到开始节点,添加到待排序列表中。

注意

在BPMN中可能有多个开始节点,所以在oryx中创建了一个临时的GlobalStart,再将所有开始节点都挂接在GlobalStart上,等待排序结束后,再删除GlobalStart。jPDL不存在这种问题。

将所有需要排序的节点添加到待排序列表中。

下面开始循环排序,每次找出一个只有外出连线的节点,我们管这种只有外出连线,没有进入连线的节点叫做自由节点。

这样首先找到的肯定是开始节点,因为开始节点都是没有进入连线的。

注意

在BPMN中最先找到的是GlobalStart。

每当找到一个自由节点,就把这个自由节点的连线删除,也删除外出连线另一侧节点对应的进入连线,然后将自由节点从待排序列表中删除,添加到已排序列表中。然后进入下一次循环。

判断循环

何时会出现循环呢?当待排序列表不为空,但是没有自由节点的时候,就说明出现循环了。意味着所有的待排序节点都至少拥有一个进入连线。

这时就要打破循环,第一步要找到循环的入口,查找入口的方法是循环待排序列表,找到原本就有多个进入连线的节点,然后判断原始的进入连线数目是不是比现在的多,如果多了,就找到入口了。

如果找不到入口,就要抛异常了,因为流程中出现了孤立的闭环,流程是无法连通的,这种流程是错误的。

找到循环入口以后就简单了,只要把入口节点上的所有进入连线都改成外出连线就行了。这样这个入口节点就变成了一个自由节点,可以使用正常的方法继续处理了。

在处理循环入口的时候,还要记录一下反转的连线,以便排序过后恢复原状。

在反转连线时,还需要考虑两种情况,如果反转的连线的原来起点是split或是join,说明只需要反转一条线就可以回到主干流程了。

   ▁▁▁▁▁▁▁▁                ▁▁▁▁▁▁▁▁
  ↓             ▕              ▕               ↓
┏━┓  ┏━┓  ┏━┓  -----→ ┏━┓  ┏━┓  ┏━┓
┃  ┃→┃  ┃→┃  ┃          ┃  ┃→┃  ┃→┃  ┃
┗━┛  ┗━┛  ┗━┛          ┗━┛  ┗━┛  ┗━┛

如果反转的连线的原来起点既不是split也不是join,说明还要继续反转后面的连线,直到反转到主干为止。

        ┏━┓                           ┏━┓
   ---- ┃  ┃←---                 --→ ┃  ┃-----
  ↓    ┗━┛   ▕               ▕     ┗━┛    ↓
┏━┓  ┏━┓  ┏━┓  -----→  ┏━┓  ┏━┓  ┏━┓
┃  ┃→┃  ┃→┃  ┃           ┃  ┃→┃  ┃→┃  ┃
┗━┛  ┗━┛  ┗━┛           ┗━┛  ┗━┛  ┗━┛

这样最终得到一个数组,数组中的元素是按照流程的先后顺序排列的。

提示

目前还不明白的是,为何要执行两次排序,第一次将闭环反转,第二次不进行这种递归反转,实际测试发现第一次闭环反转后,第二次不会出现闭环,感觉这两次操作存在冗余。

21.2. 布局

进行布局时,实际上是将流程中的每个节点放到一个二维网格中,这里使用的是从左向右依次顺排的方式。

首先通过上边获得的已排序id,对流程中的节点进行遍历。

对于每个节点,都会根据它的前驱节点决定当前节点的摆放位置。

当前节点没有前驱节点时,就会放在grid的startCell位置。

placeElement()用于决定节点在grid中放置的位置,它会尝试先从grid中读取当前节点,如果当前节点还没放到网格中,而且只有唯一前驱时,就会把唯一前驱节点当做leftCell,也就是说,会把当前节点放在leftCell的右侧,具体放在右侧的什么位置就要再进行决定了。

中间还有一步判断,如果获得的cell位置已经被填充了,而且填充内容并不是当前节点,那么就在当前行下面插入一个新行,然后在这一行对应的列中的cell放入当前节点。

如果当前节点还没有放到grid里,而且这个节点是join类型,就要先进行特殊处理,不能使用上述单纯的方法直接决定位置。

判断join的情况,其实也很简单,就是先找到与join对应的fork节点,找到fork节点后,再将join节点放在与fork节点的同一行,并且保证在最右侧就可以。

筛选过程,首先从join向前遍历,查找split节点,如果至少存在一个split节点,就沿着join节点的前驱节点一起向前搜索,查找所有可能的split节点,然后开始按照距离进行判断,找到到达join节点路径最短的split节点作为对应节点。

对于fork节点,放到grid之后还要进行后续处理,因为fork后面有多条连线,多个路径,我们希望fork能处于这些路径的中央位置,所以要对fork的后续节点进行预先布局,就是以fork所在的row为中心,向上,向下创建新row,然后把fork节点后续的节点从上到下放到右侧,这样就实现了preLayout的效果。

布局完成后,重新遍历整个grid,找到每行每列的最大值。

最后,根据grid每个cell的宽高,计算出放在grid中每个节点的实际坐标。

21.3. 压缩

为了避免在布局之后出现太多空白,需要在布局之后对grid进行合并,实际我们会比较相邻的两行,如果两行可以合并为一行,就进行合并操作。

在合并过程中,要避免出现把原来排列好的fork, join之间的空行给合并掉,所以grid的每个cell都拥有三种装填,filled,packable和empty。

filled表示这个cell中已经放置了节点,这个节点只能和empty状态的cell进行合并。

packable表示当前cell是否可以压缩,默认情况下packable=true是可以进行合并的,在需要的时候我们可以手工设置packable=false,这样这个cell就被标记为不可压缩,这个cell会最终被保留下来。

如果一个cell中既没有放置节点,也没有设置为packable=false,这个cell的状态就是empty,可以与合并到任何cell上。

在以下几种情况,我们会为cell设置packable=false。

如果当前节点是join节点,那么这个节点左侧的连线所对应的cell要设置成packable=false。。

在找到摆放join节点时,如果可以找到对应的split节点,那么在split和join节点之间的中间节点所在的cell都要设置成packable=false,这是为了中间的连线部分不重复

在摆放好join后,要把join前面所有进入连线的路径都设置为packable=false,这也是为了避免中间连线出现重复。

21.4. 立即结束节点

警告

还需要对立即结束节点进行特殊判断。

21.5. 模拟退火算法

21.5.1. 简介

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动。退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置。

模拟退火的原理也和金属退火的原理近似:我们将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样带有“能量”,以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始:每一步先选择一个“邻居”,然后再计算从现有位置到达“邻居”的概率。

21.5.2. 演算步骤

模拟退火算法新解的产生和接受可分为如下四个步骤:

  1. 由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。

  2. 计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。

  3. 判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropolis准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。

  4. 当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。

当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。

21.5.3. 伪代码

寻找能量E(s)最低的状态s

s := s0; e := E(s)                           // 设定目前状态为s0,其能量E(s0)
k := 0                                       // 评估次数k
while k < kmax and e > emax                  // 若还有时间(评估次数k还不到kmax)且结果还不够好(能量e不够低)则:
  sn := neighbour(s)                         //   随机选取一临近状态sn
  en := E(sn)                                //   sn的能量为E(sn)
  if random() < P(e, en, temp(k/kmax)) then  //   决定是否移至临近状态sn
    s := sn; e := en                         //     移至临近状态sn
  k := k + 1                                 //   评估完成,次数k加一
return s                                     // 回传状态s


上一篇 下一篇

评论



分享