当前位置:首页 > 开发 > 系统架构 > 架构 > 正文

[原创]JWFD工作流引擎设计----节点匹配搜索算法(用于初步解决条件异步汇聚问题) 补充

发表于: 2009-10-23   作者:comsci   来源:转载   浏览:
摘要: 本文主要介绍在JWFD工作流引擎设计中遇到的一个实际问题的解决方案,请参考我的博文"带条件选择的并行汇聚路由问题"中图例A2描述的情况(http://comsci.iteye.com/blog/339756),我现在把我对图例A2的一个解决方案公布出来,请大家多指点 节点匹配搜索算法(用于解决标准对称流程图条件汇聚点运行控制参数的算法) 需要解决的问题:已知分支
本文主要介绍在JWFD工作流引擎设计中遇到的一个实际问题的解决方案,请参考我的博文"带条件选择的并行汇聚路由问题"中图例A2描述的情况(http://comsci.iteye.com/blog/339756),我现在把我对图例A2的一个解决方案公布出来,请大家多指点

节点匹配搜索算法(用于解决标准对称流程图条件汇聚点运行控制参数的算法)

需要解决的问题:已知分支点的运行路径数值S,求流程图中一个汇聚点的实际访问(实际汇聚)数值,通过获取该数值,使得流程引擎控制器能够准确的控制流程的运转,即准确的控制对条件异步汇聚点放行的时机(对于该问题,国内另外一个开源工作流 Fireworkflow的作者非也有另外一个思路 请参考 http://www.fireflow.org/viewthread.php?tid=9&extra=page%3D3 )

1:  算法设计思路: 对于标准的对称的流程图而言,一个汇聚点一般来讲是应该对应一个分支点的,也就是说汇聚支路数应该和它前面的分支支路数相吻合(当然,这只是对很规则的对称流程图模型来讲),那么如果在分支节点中如果出现了条件选择公式(或者智能脚本),那么从这个分支节点所分出来的支路,就不一定都会被选中(简单举例,我们在分支节点中嵌入了一个条件表达式a>2,那么如果分支实际有三条支路,在流程运行过程中,a的数值大于2,符合嵌入的条件,三条支路其中的2条就会运行下去,而另外一条就不会运行,这样一来,在该节点的后驱汇聚点那里,我们就需要知道具体运行下去的支路数到底是几条? 怎么才能够获取这个支路数呢? 我们在流程运行控制器(流程引擎)中加入一段算法,使得我们确定的知道一个条件汇聚点的前驱分支点是哪个节点,然后我们先计算一次嵌入条件公式,预先知道该前驱分支点具体要走几条支路,然后再把这个支路数值作为参数传递给用于控制条件汇聚点的控制器中,使得汇聚点按照实际运行的支路来判断是否该继续运行到下一个节点去,那么我们按照这个思路设计伪代码算法

  混合伪代码5步描述法
 
1: 条件表达式解析函数 public java.util.ArrayList CFS(SID,GID)() 
  这个函数是流程控制器中用于解析流程嵌入的条件表达式,并根据流程的变量数值计算出流程嵌入公式的结果,函数参数SID是传递给流程控制器中的需要处理的节点ID,GID是流程图的ID,下面一致

2:  获取输入汇聚节点的所有前驱汇聚点函数  public java.util.ArrayList GAS(SID,GID)()   这个函数用于获取该节点前面出现的所有汇聚点

3: 获取输入汇聚节点的所有前驱分支点函数  public java.util.ArrayList GAJ(SID,GID)()   这个函数用于获取该节点前面出现的所有分支点

4: 对该节点的所有前驱分支点集合和前驱汇聚点集合进行计算,找出该汇聚节点的匹配分支点SSID  public String GRN(GAS,GAJ,GID)()  节点匹配算法的实质是对称集合配对差算法

5: 在找到这个匹配的分支点SSID之后,我们就可以对其中嵌入的条件公式进行提前计算
   public int PCSF(SSID,GID)(
      CFS(SSID,GID)()
      return K;
   )

     这样获得了一个int数值k,然后我们就在流程控制器中在流程汇聚点进行控制的过程中使用这个数值,那么前面提到得问题就这样初步解决了,离圆满的解决这个问题,我们又近了一步............


2:潜在的问题

对于寻找汇聚节点的匹配分支点这个算法,我的思路是,通过递归查找所有该节点的前驱分支点和前驱汇聚点,并将这两个节群放入两个数组中,因为我们假设在一个对称的流程图中,分支点和汇聚点的个数是匹配的,也就是说一个汇聚点必须要对应一个分支点,那么根据这个假设,我们把两个集合中的节点进行配对,配对剩下来的那个孤独点,我们就把它当做我们要查找的与那个汇聚点匹配的分支点......这种算法有点类似于-算法导论中计算几何学中的那个寻找最近点对的算法,但是在设计这个算法的过程中,我还没有考虑到算法对各种流程图的有效性和合理性的问题,也就是说我还没有对这个算法做一个严密的数学上面的证明,使得这个算法在各种情况下都是合理和有效的,希望有朋友能够对此提出有益的意见和建议。。。。
   

这个算法的实例包含在JWFD v0.96开源版本的引擎下面的算法包中
org.jwfd.workflowEngines.Algorithm.TopologyAnalysis.java

请在JWFD官方下载中下载本文所介绍的程序和文档
http://www.cnblogs.com/comsci/favorite/260690.html
==============================================================================

一般来说是实践检验真理,但是我想用理论来检验真理,怎么办呢?这种情况下该使用什么数学语言来证明这个算法的有效性,灵敏性和稳健性呢?

(后两个词是“数学建模方法与分析”这本书中的词汇,我只是借鉴,这个算法不一定需要灵敏性证明)
 

 

 

[原创]JWFD工作流引擎设计----节点匹配搜索算法(用于初步解决条件异步汇聚问题) 补充

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
本文主要介绍在JWFD工作流引擎设计中遇到的一个实际问题的解决方案,请参考我的博文"带条件选择的并
JWFD工作流引擎设计--节点匹配搜索算法(再讨论) NMSA Node matching search algorithm--节点匹配搜索
JWFD工作流引擎设计--节点匹配搜索算法(再讨论) NMSA Node matching search algorithm--节点匹配搜
非常抱歉,由于在JWFD0.96的引擎中使用的自动运行控制器中的节点匹配搜索算法在运行过程中出现问题
暂时忽略工作流状态的问题,仅仅表示工作流的拓扑结构 为什么要搞这样的东东,jwfd v0.96版本中的引
JWFDv0.96工作流引擎设计 ----节点回退算法说明 注:这篇文章中所使用的“函数”就是指JAVA语言中的
今天在普元工作流的论坛上面,有一个帖子,上面有一个流程图,如下 这个流程图的拓扑结构,如果采用
作者: comsci 发表于 2010-08-18 11:41 原文链接 阅读: 43 评论: 0 JWFD工作流引擎设计--简单矩阵建
暂时忽略工作流状态的问题,仅仅表示工作流的拓扑结构 为什么要搞这样的东东,jwfd v0.96版本中的引
今天在普元工作流的论坛上面,有一个帖子,上面有一个流程图,如下 这个流程图的拓扑结构,如果采用
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号