MyException - 我的异常网
当前位置:我的异常网» 开源软件 » 工作流引擎设计中的遍历算法的有关问题

工作流引擎设计中的遍历算法的有关问题

www.myexceptions.net  网友分享于:2013-06-27  浏览:17次
工作流引擎设计中的遍历算法的问题

 

  今天在普元工作流的论坛上面,有一个帖子,上面有一个流程图,如下

 

 

 

   这个流程图的拓扑结构,如果采用图形深度优先遍历算法来遍历一遍,遍历顺序的部分应该是 

   开始活动-> A-1=>B-4=>E-5=>NEXT

 

   这种运行顺序在实际流程运行过程中显然有问题,实际运行过程中从流程A-1节点分支到后面的四个并行节点,这四个并行节点应该是同时被引擎触发,但是如果采用深度优先遍历算法,算法是从第一个分支一直往最深的支路上面遍历,直到走到该分支的最后一个节点,然后才往回复到最初分支的第二个分支支路上面,继续往这个分支的最深处遍历,如此往复,遍历完所有节点,这样的遍历过程显然和流程实际运行过程是不吻合的

 

   那么如果用广度优先遍历算法呢? 似乎也有问题

 

   开始活动->A-1 然后 四个分支节点全部依次被访问,注意,广度优先遍历算法是和深入优先算法相对应,即从图的起点开始遍历,遍历的顺序是先把同一层次的所有并行点都依次访问,然后再访问第二层次的所有并行点,这样的话,访问顺序就是  开始活动->A-1->B-4->C-3->D-未完成->F-2->E-5->NEXT  ,这个遍历顺序也和实际运行过程不相符合,所以流程引擎在应用图形遍历算法的时候,必须对算法进行自定义的改造,才能够让流程引擎在遍历流程的过程中,做到符合流程的实际业务运行过程。。。。。

 

  因此我在05年设计JWFD工作流引擎的时候,就采用对广度优先算法进行改造的方法,实现了一个很初级的基于遍历算法的引擎,现在我手上的代码不是当时的代码,因为最初的设计思路好像和这个伪代码不一样,05年的时候,苏州大学一个硕士研究生做毕业设计,用到JWFD,他在测试过程中,发现算法在并行汇聚的时候会出问题,然后我们两个就这个问题,进行多很多次的沟通和交流,后来在他的协助下,把这个算法又修改了,才解决了并行汇聚的问题,但是当时的修改过程没有做文字的记录,所以为什么要这样修改,怎么修改的过程就没有记录下来,很可惜。。。

 

          DFS伪码描述算法--修改版本
       
          前驱路由点: 该点是N个节点的source点(N>1)

          分支属性判断: 是单节点支路还是多节点串行支路

          后驱路由点: 该点有N个节点的target点(N>1)

       在返回访问序列的时候,当遇到有支路的时候,整个该支路用符号Nx表示,遍历的时候把这一路做为一个单节点来处理
       在最后返回序列的时候,用支路的串行序列代替Nx,返回完整的访问序列

       这个算法基本上可以解决分支和发散,与汇聚的流程图遍历问题

         for(int i =0  i <  当前节点的邻接点个数){

          if (该点是个前驱路由点) {
              if (该点没有被访问过) {
                  设置访问次数加(从递归方法中获得的循环控制变量)
                  返回
              }
              else if( 如果已经访问过,但是访问次数<它的前驱节点总数){
                   设置访问次数加(从递归方法中获得的循环控制变量+1)
                   返回
              }
              else if(总计访问次数=它的前驱节点总数){
                  递归进入下一个节点的访问(把大循环体的,循环变量带进去递归方法中)
              }

              }
              else if(如果是普通节点){
                  设置访问标志
                  递归进入下一个节点的访问(把大循环体的,循环变量带进去递归方法中)
              }
              }
       }

 

  最初的引擎算法DFS其实还比现在的这个版本的更加自动化,因为当时出发点是设计一个运行后不需要人工干预的引擎,所以整个遍历的过程都是全自动的,但是后来有新的需求,要求加入人工触发的节点,所以慢慢的,这个自动引擎就变成半自动,后来彻底抛弃自动的过程了。。。。。做产品,哪怕是开源的,如果要考虑来自各种用户的需求,那么有一个现象就是:你最初的设计理念会逐渐的走样,逐渐的变成连你自己都无法理解的模型,哈哈。。。。

 

 

 

文章评论

当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
每天工作4小时的程序员
每天工作4小时的程序员
代码女神横空出世
代码女神横空出世
 程序员的样子
程序员的样子
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
如何成为一名黑客
如何成为一名黑客
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
10个调试和排错的小建议
10个调试和排错的小建议
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
鲜为人知的编程真相
鲜为人知的编程真相
漫画:程序员的工作
漫画:程序员的工作
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
中美印日四国程序员比较
中美印日四国程序员比较
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
一个程序员的时间管理
一个程序员的时间管理
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
为什么程序员都是夜猫子
为什么程序员都是夜猫子
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Java程序员必看电影
Java程序员必看电影
程序员和编码员之间的区别
程序员和编码员之间的区别
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
我是如何打败拖延症的
我是如何打败拖延症的
程序员必看的十大电影
程序员必看的十大电影
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
老程序员的下场
老程序员的下场
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员的鄙视链
程序员的鄙视链
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
旅行,写作,编程
旅行,写作,编程
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
编程语言是女人
编程语言是女人
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员都该阅读的书
程序员都该阅读的书
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有