## 6 Composition of a BPMN Diagram
### Process Composition Based on Activity Graphs  
All the process mining techniques presented in Section 6.1 consist of generating a Petri-net based on a provided set of workflow traces. Converting such a net to a BPMN model is a complex task and may require additional model modifications [64]. Therefore, the other approach presented in this paper is based on activity graphs and is used to compose a BPMN model directly from a synthetic workflow log. An activity graph [65]\(G_{A}\) of a business process can be defined by Expression (5):  
\[G_{A}=(V_{A},E,deg^{-},deg^{+}), \tag{5}\]  
where:  
\(\bullet\)\(V_{A}\) is a finite set of vertices representing process activities,  
\(\bullet\)\(E\) is a set of directed edges,  
\(\bullet\)\(deg^{-}:V_{A}\longrightarrow\mathbb{N}_{0}\) determines the number of incoming edges for a vertex, and \(\mathbb{N}_{0}\) stands for non-negative integers,  
\(\bullet\)\(deg^{+}:V_{A}\longrightarrow\mathbb{N}_{0}\) determines the number of outgoing edges for a vertex. There are several relation templates [66] that describe dependencies between events in a workflow log and as a consequence relations between activities in a business process model. Let us recall those that correspond to the most strict ordering relations between two events, denoted as \(A\) and \(B\):  
\(\bullet\) chain response: if \(A\) occurs, then it is directly followed by \(B\),  
\(\bullet\) chain precedence: if \(B\) occurs, then it is directly preceded by \(A\),  
\(\bullet\) chain succession: \(A\) occurs if and only if \(B\) occurs directly afterwards. Activity graphs represent admissible chain response and chain precedence relations in a workflow log. The creation of such a graph \(G_{A}\) for a given workflow log \(W\) consists of defining an initial node, a terminal node and a separate intermediate node for every activity in the logs and then linking all the pairs of nodes with directed edges if a chain ordering relation occurs between them (see Algorithm 1 for details). ```
Input:Workflow log \(W\) Output:Activity graph \(G_{A}\) \(G_{A}\) := new Graph0; \(G_{A}\).addVertex(\(v_{s}\), type := \"Start Event\"); foreachTrace\(\sigma\) in \(W\)do \(v_{n}:=G_{A}\).addVertex(\(\tau^{(1)}\), type := \"Activity\"); \(G_{A}\).connect(\(v_{s}\),\(v_{n}\)); foreachActivity\(\tau\) in \(\tau^{(2)}\)...\(\tau^{(K)}\in\sigma\)do \(v_{n+1}:=G_{A}\).addVertex(\(\tau\), type := \"Activity\"); \(G_{A}\).connect(\(v_{n}\),\(v_{n+1}\)); \(v_{n}:=v_{n+1}\);  end foreach ifnot\(G_{A}\).contains(\"End Event\")then \(G_{A}\).addVertex(\(v_{t}\), type = \"End Event\"); \(G_{A}\).connect(\(v_{n+1}\),\(v_{t}\));  end foreach
```  
**Algorithm 1**Generation of an activity graph. Representing all the chain ordering relations in a log by a directed edge may lead to parallelism clutter [62]. This situation occurs when the process specification allows one or more activities to be executed in parallel. In the workflow log generated according to the method described in Section 5.2,such activities can appear in different order, depending on the workflow trace. As a result, given two activities \(A\) and \(B\), if \(A\) occurs directly before \(B\) in trace \(\sigma_{x}\) and at \(B\) occurs directly before \(A\) in trace \(\sigma_{y}\), then executing Algorithm 1 will cause the creation of two independent directed edges: one from \(A\) to \(B\) and the other from \(B\) to \(A\). The issue of doubled edges needs to be resolved in order to avoid doubled sequence flows between parallel activities in the generated BPMN model. The necessary refinement of the set of edges (\(E\)) consists of identifying potentially parallel activities and removing doubled connections between them. A relation of potential parallelism was defined in the \(\alpha\) algorithm: two tasks are likely to be parallel if they can follow each other directly in any order [67]. Although this rule is valid for models representing a simple workflow, it does not work perfectly if loops exist in the discovered process.