# A Novel Process Recommendation Method That Integrates Disjoint Paths and Sequential Patterns
## 3 Proposed Method
### Edge-Disjoint Path Extraction Method  
The disjoint paths in a process model represent one of the execution paths, and thus, a process's behavior can be expressed by its set of disjoint paths. While process similarity comparison methods based on disjoint paths [2,26] are highly interpretable and easy to implement, all current methods rely on vertex-disjoint paths. However, as per the literature [27,28], each execution of a vertex-disjoint path has at least one unexecuted node, which ignores the disorder of 'And' structures whose child nodes are disordered. For example, consider the TPST1 shown in Figure 4, which includes an 'And' structure with child nodes 'C' and 'Xor', where the child nodes 'D' and 'E' of 'Xor' select one to execute. When using the vertex-disjoint path to express the behavioral semantics of a process, the resulting vertex-disjoint path extraction are \(<\)A,C,D,B\(>\) and \(<\)A,C,E,B\(>\), indicating that the execution order of the process is \(\mathrm{A}\rightarrow\mathrm{C}\rightarrow\mathrm{D}\rightarrow\mathrm{B}\) or \(\mathrm{A}\rightarrow\mathrm{C}\rightarrow\mathrm{E}\rightarrow\mathrm{B}\). This approach cannot distinguish the semantics of the 'And' structure or the 'Sequence' structure since the execution order of node 'C' always comes before nodes 'D' and 'E'. In contrast, edge-disjoint paths allow nodes to be repeated, and thus, this study introduced edge-disjoint paths to express the behavioral semantics of processes. The corresponding edge-disjoint path extraction results in Figure 1 are \(<\)A,C,D,B\(>\), \(<\)A,C,E,B\(>\), \(<\)A,D,C,B\(>\), and \(<\)A,E,C,B\(>\), which meet the requirements for process recommendation. Inspired by the vertex-disjoint path extraction algorithm (VPE) [26] and based on the definition of TPST structure and edge-disjoint path, this study proposed the EPE for the process model. A breadth-first search traverses each node of the TPST. The edge-disjoint path extraction is carried out according to the parent nodes of different types of current nodes and the characteristics of each gateway node. In addition to the above improvement for the disorderly characteristics of the child nodes in the 'And' structure, the problem that occurs when the original algorithm has infinite disjoint paths in the loop structure is also solved. The implementation of the EPE is performed in the following steps shown in Figure 5.  
Figure 4: TPST structure corresponding to the business process in Figure 1.  
Algorithm 1 uses BFS to parse the TPST into edge-disjoint paths. The input for Algorithm 1 is a process library model, and the output is an edge-disjoint path table. ```
Input: process model library \(F\) Output: edge-disjoint path table \(R\) FOR (each process \(p\) in \(F\)) do{  Initialize set of edge-disjoint path \(r\); \(k=1\); convert \(p\) to TPSP;  FOR \(l\) do BFS{  IF current node \(Pi\) in layer1 [r[k-0]\(\_\)add(\(Pi\))  ELSE IF \(Pi\)'s parent node \(P\)] is Xor FOR (each \(\mathbf{r[i]}\) that contains \(P\)) do{  IF Pi = P[i]s stack child node [replace \(P\)] in \(\mathbf{r[i]}\) with \(P_{i}\)]  ELSE {copy r[k] = r[i]; replace \(P\)] in r[k] with \(P_{i}\); \(k\)++}] ELSE IF \(P\)) is And{  IF \(Pi\) = P[i]s first child node [FOR (each \(\mathbf{r[i]}\) that contains \(P\)) do[replace \(P\)] in \(\mathbf{r[i]}\) with \(P_{i}\)]]  ELSE FOR (each r[i] that contains \(P\)'s sibling node \(P\)) do{  Insert \(Pi\) in front of \(P\) in r[i]; copy r[k] = r[i]; insert \(Pi\) after \(P\) in r[k]; \(k\)++}] ELSE IF \(P\) is Loop{  IF \(Pi\) = P[i]s first child node [FOR (each \(\mathbf{r[i]}\) that contains \(P\))] do{  Replace \(P\)] in r[i] with \(P_{i}\)}] ELSE FOR (each r[i] that contains \(P\)) do{  If \(P_{i}\) = \(P_{i}\)'s last child node[r[i]].add(\(P\)); insert \(P\) after \(Pi\) in r[i]] ELSE {r[i].add(\(P\))}]]  Return \(R\rightarrow\mathbf{r[i].r[k]}\)
```  
**Algorithm 1**EPE for the process model  
First, the top-level nodes are directly placed into the corresponding edge-disjoint path r[k-1].