工作流流程图并发单元的合法性校验方法

摘要

本发明公开一种工作流流程图并发单元的合法性校验方法。它通过灵活的组合运用图的的先深搜索算法来检查并发单元的非法出口、非法入口及各并发分支间的跳转；具体为：其数据结构采用正向、反向两个邻接表；在检验非法出口时使用正向邻接表，在检验非法入口时使用反向邻接表，在检验并发分支间的跳转时，分别使用到两个邻接表。本发明通过灵活的组合运用图的先深搜索算法检查出并发单元的非法出口、非法入口及各并发分支间的跳转。

说明书

技术领域

本发明属于工作流系统技术，具体地说是一种工作流流程图并发单元的合法性检验方法。

技术背景

在工作流系统的图形化流程定义工具中，所定义的流程图必须是合法的，不合法的流程工作流引擎无法解释，从而也就无法控制流程实例的运行，在流转过程中会出现不可预知的错误。流程实例不能按照用户的预期运行，就不能实现用户的预定目标。人们可以在画流程图时做出种种限制来保证它的正确性，但是有时候做出这样的限制是不可能的，通常做图是随意的，这样流程图的合法性就不能保证。现有技术常通过模拟运行来检验流程的正确性，但是模拟需要耗费大量时间和资源，而且穷举所有可能的运行情况是非常困难的，所以需要对流程图的合法性进行校验。

并发单元的合法性校验是流程图的合法性校验中的重要一环。并发单元的校验主要有两个方面：一是并发单元的封闭性，即一个并发单元只能有一个入口一个出口；一是各并发分支间的互斥性，即不能由一个并发分支进入另一个并发分支。检验并发单元的合法性必须能够检查出并发单元的非法出口、非法入口及各并发分支间的跳转。有了对并发单元的合法性校验，保证了流程图中并发单元的正确性，才能保证流程实例按照用户的期望正确运行。然而，目前对并发单元的合法性校验还没见报道。

发明内容

本发明的目的是提供一种能够保证流程图中并发单元的正确性、流程实例按照用户的期望正确运行的工作流流程图并发单元的合法性检验方法。

为了实现上述目的，本发明的技术解决方案如下：

通过灵活的组合运用图的的先深搜索算法来检查并发单元的非法出口、非法入口及各并发分支间的跳转；具体为：其数据结构采用正向、反向两个邻接表；其中：在检验非法出口时使用正向邻接表，在检验非法入口时使用反向邻接表，在检验并发分支间的跳转时，分别使用到两个邻接表，正向搜索时使用正向邻接表，反向搜索时使用反向邻接表。

在检验非法出口和非法入口时，每个节点需要对应一个搜索标识，在检验并发分支间的跳转时，每个节点需要对应两个搜索标识，使用正向标识表示正向搜索和使用反向标识表示反向搜索。

检验非法出口的算法为：一个并发单元只有一个入口一个出口，并发开始节点是它的入口，并发结束节点是它的出口，从并发开始节点起进行先深搜索，至对应的并发结束节点，在到达并发结束节点之前就到达了叶子节点(没有出边)或是回到了并发开始节点时，表明并发单元存在非法出口；具体为：1)整个流程图创建一个邻接表；2)邻接表中每一个并发开始节点V执行如下步骤：

a)把邻接表中每个节点对应的搜索标识f置为0；

b)由并发开始节点V出发调用遍历子算法进行遍历。

所述遍历子算法为：首先把遍历起始节点V0的遍历标识f设为1；然后判断遍历起始节点V0是否还有下一个相邻节点；如有下一个相邻节点，设遍历起始节点V0的下一个相邻节点为V2，再对所述下一个相邻节点V2进行如下判断：1)如果遍历起始节点V0的下一个相邻节点V2是并发开始节点V对应的并发结束节点V1，继续判断遍历起始节点V0是否还有下一个相邻节点；2)如果遍历起始节点V0的下一个相邻节点V2的遍历标识f为1，继续判断遍历起始节点V0是否还有下一个相邻节点；3)如果遍历起始节点V0的下一个相邻节点V2是并发开始节点V，则并发单元有非法出口，打印遍历路径，继续判断遍历起始节点V0是否还有下一个相邻节点；4)如果遍历起始节点V0的下一个相邻节点V2是叶子节点(没有出边)，则并发单元有非法出口，打印遍历路径，继续判断遍历起始节点V0是否还有下一个相邻节点；5)其它情况则递归调用遍历子算法，由遍历起始节点V0的下一个相邻节点V2出发继续进行遍历。

检验非法入口的算法为：一个并发单元只有一个入口一个出口，并发开始节点是它的入口，并发结束节点是它的出口，从并发结束节点起进行逆向先深搜索，至到达对应的并发开始节点，如果在到达并发开始节点之前就到达了根节点(没有入边)或是回到了并发结束节点，则表明并发单元存在非法入口；具体算法为：首先对整个流程图创建一个逆向邻接表；然后对邻接表中每一个并发结束节点V执行如下步骤：

1)把邻接表中每个节点对应的搜索标识f置为0；

2)由并发结束节点V出发调用逆向遍历子算法进行遍历。

所述逆向遍历子算法为：首先把遍历起始节点V0的遍历标识f设为1；再判断遍历起始节点V0是否还有下一个相邻节点；如有的话，设遍历起始节点V0的下一个相邻节点为V2，对所述下一个相邻节点V2进行如下判断：1)如果遍历起始节点V0的下一个相邻节点V2是并发结束节点V对应的并发开始节点V1，则继续判断遍历起始节点V0是否还有下一个相邻节点；2)如果遍历起始节点V0的下一个相邻节点V2的遍历标识f为1，则继续判断遍历起始节点V0是否还有下一个相邻节点；3)如果遍历起始节点V0的下一个相邻节点V2是并发结束节点V，则并发单元有非法入口，打印遍历路径，则继续判断遍历起始节点V0是否还有下一个相邻节点；4)如果遍历起始节点V0的下一个相邻节点V2是根节点(没有入边)，则并发单元有非法入口，打印遍历路径，则继续判断遍历起始节点V0是否还有下一个相邻节点；5)其它情况则递归调用逆向遍历子算法，由遍历起始节点V0的下一个相邻节点V2出发继续进行遍历。

检验并发分支间跳转的算法为：从并发开始节点起进行遍历，遇到有多个入口的节点时，从这个节点起进行反向遍历，如果可以不经过已正向遍历的节点就能回到并发开始节点，则并发分支间存在跳转；其算法：1)整个流程图创建一个正向邻接表，一个逆向邻接表；2)对邻接表中每一个并发开始节点V执行如下步骤：

1)把邻接表中每个节点对应的正向遍历标识f设为0；

2)由并发开始节点V出发调用正向遍历子算法进行遍历。

所述正向遍历子算法为：首先把遍历起始节点V0的正向遍历标识f、逆向遍历标识f1设为1；然后判断遍历起始节点V0是否还有下一个相邻节点，如有的话，设遍历起始节点V0的下一个相邻节点为V2，再对所述下一个相邻节点V2执行步骤为：1)如果下一个相邻节点V2与并发开始节点V直接相邻，把邻接表中每个节点对应的逆向遍历标识f1设为0；2)如果下一个相邻节点V2的逆向遍历标识f1为0，且下一个相邻节点V2不是并发开始节点V，也不是并发开始节点V对应的并发结束节点V1，且下一个相邻节点V2的入边数大于1，由下一个相邻节点V2出发调用逆向遍历子算法进行逆向遍历；3)对下一个相邻节点V2进行如下判断：a.如果下一个相邻节点V2是并发开始节点V，则对遍历起始节点V0是否还有下一个相邻节点V2继续执行判断；b.如果下一个相邻节点V2是并发开始节点V对应的并发结束节点V1，则对遍历起始节点V0是否还有下一个相邻节点V2继续执行判断；c.如果下一个相邻节点V2的正向遍历标识f为1，则对遍历起始节点V0是否还有下一个相邻节点V2继续执行判断；d.如果下一个相邻节点V2是叶子节点(没有出边)，则对遍历起始节点V0是否还有下一个相邻节点V2继续执行判断；e.其它情况(不是a～d四种)则递归调用正向遍历子算法，由下一个相邻节点V2出发继续进行遍历。

所述逆向遍历子算法为：首先将遍历起始节点V0的逆向遍历标识f1设为1；再判断遍历起始节点V0是否还有下一个相邻节点，如有的话，设遍历起始节点V0的下一个相邻节点为V3，再对该下一个逆向邻接节点V3进行判断：1)如果逆向邻接节点V3是并发开始节点V对应的并发结束节点V1，则继续判断下一个逆向邻接节点；2)如果逆向邻接节点V3是根节点(没有入边)，则继续判断下一个逆向邻接节点；3)如果逆向邻接节点V3的逆向遍历标识f1为1，则继续判断下一个逆向邻接节点；4)如果逆向邻接节点V3是并发开始节点V，则并发分支间存在跳转，打印遍历路径，再继续判断下一个逆向邻接节点；5)其它情况则递归调用逆向遍历子算法，由逆向邻接节点V3出发继续进行逆向遍历。

本发明具有如下优点：

1.本发明通过灵活的组合运用图的先深搜索算法能够检查出并发单元的非法出口、非法入口及各并发分支间的跳转，实现了对并发单元的合法性校验，从而保证了流程图中并发单元的正确性，使流程实例可以按照用户的期望正确运行。

2.本发明通过在定义时对流程图进行校验，在很大程度上保证了流程实例的正确运行，降低了出错的可能。

3.本发明通过在流程图完成后对其合法性进行校验，免去了在作图时做出种种限制，使用户在作图时更加灵活，且便于修改。

4.本发明通过在定义时对流程图的校验，免去了为保证流程的正确性而进行模拟运行，为用户节省了资源。

5.本发明方法简单，可靠。

附图说明

图1为本发明检验非法出口的正向遍历子算法的流程图。

图2为本发明检验非法入口的逆向遍历子算法流程图。

图3为本发明检验分支间跳转的正向遍历子算法流程图。

图4为本发明检验分支间跳转的逆向遍历子算法流程图。

图5为本发明有非法出口的并发单元示例。

图6为本发明有非法入口的并发单元示例。

图7为本发明分支间存在跳转的并发单元示例。

具体实施方式

下面结合附图和实施例对本发明作进一步详细说明。

本发明的数据结构采用邻接表。需要有两个邻接表，一个正向的邻接表，一个反向的邻接表。在检验非法出口时使用正向邻接表，在检验非法入口时使用反向邻接表，在检验并发分支间的跳转时，分别使用到两个邻接表。在检验非法出口和非法入口时，每个节点需要对应一个搜索标识，在检验并发分支间的跳转时，每个节点需要对应两个搜索标识，分别表示正向搜索(使用正向邻接表)和反向搜索(使用反向邻接表)。

检验非法出口的算法：一个并发单元只有一个入口一个出口，并发开始节点是它的入口，并发结束节点是它的出口，这样从并发开始节点起进行先深搜索，一定可以到达对应的并发结束节点，如果在到达并发结束节点之前就到达了叶子节点(没有出边)或是回到了并发开始节点，就表明并发单元存在非法出口。

算法步骤如下：

1.整个流程图创建一个邻接表。

2.对邻接表中每一个并发开始节点V执行如下步骤：

1)把邻接表中每个节点对应的搜索标识f置为0；

2)由并发开始节点V出发调用遍历子算法进行遍历。

其中：如图1所示，所述遍历子算法描述如下：

1.把遍历起始节点V0的遍历标识f设为1；

2.判断遍历起始节点V0是否还有下一个相邻节点；如有下一个相邻节点，设遍历起始节点V0的下一个相邻节点为V2，然后对该下一个相邻节点V2进行如下判断：

1)如果遍历起始节点V0的下一个相邻节点V2是并发开始节点V对应的并发结束节点V1，继续判断遍历起始节点V0是否还有下一个相邻节点；

2)如果遍历起始节点V0的下一个相邻节点V2的遍历标识f为1，继续判断遍历起始节点V0是否还有下一个相邻节点；

3)如果遍历起始节点V0的下一个相邻节点V2是并发开始节点V，则并发单元有非法出口，打印遍历路径，继续判断遍历起始节点V0是否还有下一个相邻节点；

4)如果遍历起始节点V0的下一个相邻节点V2是叶子节点(没有出边)，则并发单元有非法出口，打印遍历路径，继续判断遍历起始节点V0是否还有下一个相邻节点；

5)其它情况(不是上述四种情况时)则递归调用遍历子算法，由遍历起始节点V0的下一个相邻节点V2出发继续进行遍历。

检验非法入口的算法：一个并发单元只有一个入口一个出口，并发开始节点是它的入口，并发结束节点是它的出口，这样从并发结束节点起进行逆向先深搜索，一定可以到达对应的并发开始节点，如果在到达并发开始节点之前就到达了根节点(没有入边)或是回到了并发结束节点，就表明并发单元存在非法入口。

算法步骤如下：

1.对整个流程图创建一个逆向邻接表；

2.对邻接表中每一个并发结束节点V执行如下步骤：

1)把邻接表中每个节点对应的搜索标识f置为0；

2)由并发结束节点V出发调用逆向遍历子算法进行遍历。

其中所述逆向遍历子算法描述如下(参见图2)：

1.把遍历起始节点V0的遍历标识f设为1。

2.判断遍历起始节点V0是否还有下一个相邻节点，如有的话，设遍历起始节点V0的下一个相邻节点为V2，再对该下一个相邻节点V2进行如下判断：

1)如果遍历起始节点V0的下一个相邻节点V2是并发结束节点V对应的并发开始节点V1，则继续判断遍历起始节点V0是否还有下一个相邻节点。

2)如果遍历起始节点V0的下一个相邻节点V2的遍历标识f为1，则继续判断遍历起始节点V0是否还有下一个相邻节点。

3)如果遍历起始节点V0的下一个相邻节点V2是并发结束节点V，则并发单元有非法入口，打印遍历路径，则继续判断遍历起始节点V0是否还有下一个相邻节点。

4)如果遍历起始节点V0的下一个相邻节点V2是根节点(没有入边)，则并发单元有非法入口，打印遍历路径，则继续判断遍历起始节点V0是否还有下一个相邻节点。

5)其它情况(不是上述四种情况)则递归调用逆向遍历子算法，由遍历起始节点V0的下一个相邻节点V2出发继续进行遍历。

检验并发分支间跳转的算法：由于各并发分支间不应存在跳转，所以从并发开始节点到并发单元内的任一节点不能存在两条不相交的路径；本发明从并发开始节点起进行遍历，遇到有多个入口的节点，即从这个节点起进行反向遍历，如果可以不经过已正向遍历的节点就能回到并发开始节点，则并发分支间存在跳转。

算法步骤如下：

1.整个流程图创建一个正向邻接表，一个逆向邻接表。

2.对邻接表中每一个并发开始节点V执行如下步骤：

1)把邻接表中每个节点对应的正向遍历标识f设为0；

2)由并发开始节点V出发调用正向遍历子算法进行遍历。

如图3所示，正向遍历子算法描述如下：

1.把遍历起始节点的正向遍历标识f、逆向遍历标识f1设为1。

2.判断V0是否还有下一个相邻节点，如有的话，设V0的下一个相邻节点为V2，再对该下一个相邻节点V2执行如下步骤：

1)如果下一个相邻节点V2与并发开始节点V直接相邻(存在一条从并发开始节点V到下一个相邻节点V2的边)，把邻接表中每个节点对应的逆向遍历标识f1设为0；

2)如果下一个相邻节点V2的逆向遍历标识f1为0，且下一个相邻节点V2不是并发开始节点V，也不是并发开始节点V对应的并发结束节点V1，且下一个相邻节点V2的入边数大于1，由下一个相邻节点V2出发调用逆向遍历子算法进行逆向遍历；

3)对下一个相邻节点V2进行如下判断：

a.如果下一个相邻节点V2是并发开始节点V，则对遍历起始节点V0是否还有下一个相邻节点继续执行判断；

b.如果下一个相邻节点V2是并发开始节点V对应的并发结束节点V1，则对遍历起始节点V0是否还有下一个相邻节点V2继续执行判断；

c.如果下一个相邻节点V2的正向遍历标识f为1，则对遍历起始节点V0是否还有下一个相邻节点V2继续执行判断；

d.如果下一个相邻节点V2是叶子节点(没有出边)，则对遍历起始节点V0是否还有下一个相邻节点V2继续执行判断；

e.其它情况(不是a～d四种)则递归调用正向遍历子算法，由下一个相邻节点V2出发继续进行遍历。

3)对下一个相邻节点V2进行如下判断：

如图4所示，逆向遍历子算法描述如下：

1.将遍历起始节点V0的逆向遍历标识f1设为1；

2.判断遍历起始节点V0是否还有下一个相邻节点，如有的话，设遍历起始节点V0的下一个相邻节点为V3，再对该下一个逆向邻接节点V3进行以下判断：

1)如果逆向邻接节点V3是并发开始节点V对应的并发结束节点V1，则继续判断下一个逆向邻接节点；

2)如果逆向邻接节点V3是根节点(没有入边)，则继续判断下一个逆向邻接节点；

3)如果逆向邻接节点V3的逆向遍历标识f1为1，则继续判断下一个逆向邻接节点；

4)如果逆向邻接节点V3是并发开始节点V，则并发分支间存在跳转，打印遍历路径，再继续判断下一个逆向邻接节点；

5)其它情况(不是1)～5)内容)则递归调用逆向遍历子算法，由逆向邻接节点V3出发继续进行逆向遍历。

下面举例说明如何使用该方法检验并发单元的合法性。

如图5所示，一个有非法出口的并发单元由并发单元内的行为节点A2可以直接到达并发单元外的行为节点A3。采用本发明检验并发单元非法出口的方法，由并发开始节点V出发进行遍历，遍历的顺序依次是V、A1、A2、A3、E，这样就存在一条由并发开始节点V出发，不经过它对应的并发结束节点V1，即可到达叶节点的路径，说明该并发单元存在非法出口。

如图6所示，一个有非法入口的并发单元由并发单元外的行为节点A3可以直接到达并发单元内的行为节点A2。采用本发明检验并发单元非法入口的方法，由并发结束节点V出发进行逆向遍历，遍历的顺序依次是V、A1、A2、A3、S，这样就存在一条由并发结束节点V出发，不经过它对应的并发开始节点V1，即可到达根节点的逆向路径，说明该并发单元存在非法入口。

如图7所示，一个分支间存在跳转的并发单元由并发开始节点有两条完全不重合的路径可以到达行为节点A1。采用本发明检验并发单元分支间跳转的方法，先由并发开始节点V出发进行正向遍历，遍历的顺序是V、A1，当到达A1时发现它有两个入口，由A1出发进行逆向遍历，遍历的顺序是A1、A2、V，这样从并发开始节点V出发，有两条完全不重合的路径到达行为节点A1，说明该并发单元分支间存在跳转。