Previous research is concerned with di erences in BPMN diagram layout, e.g., with regards to understandability. However, layouts have neither been formally described nor their classi cation been automated. We aim at formalizing BPMN layouts and automating diagram layout classi cation for BPMN diagrams: We calculate sequence ow directions and encode them. By using regular expressions, these are clustered to diagram layouts. This results in a set of formally described BPMN layouts and a corresponding algorithm which we implemented in a tool. The results are very similar to previous work of manual layout classi cation on the GitHub process set. Researchers can use our de nition when conducting BPMN diagram analysis and industry experts can use our tool for validating models against their layout guidelines.
BPMN is the standard modeling language for business processes [
One branch of BPMN understandability research is concerned with the layout of BPMN processes. The underlying hypothesis states that layout has a big impact on understandability. Besides small grained metrics like number of sequence ow crossings, the overall BPMN diagram layout has come into focus.
Up to now, layouts are only `speci ed' by giving examples and appealing to the intuitive understanding of the reader (\top-down layout", \left-right layout"). This makes it hard to a) fully understand ndings, b) replicate research and c) compare di erent research results. Furthermore, industry users cannot decide whether their diagrams are compliant to the latest research, thus preventing the implementation of scientists' recommendations for diagram layout.
In this paper, we want to outline a formal de nition of prevalent ow layouts
found in GitHub models and create an algorithm and followingly automated
tool support for classifying BPMN diagram layouts. The term ow layout is
chosen to clarify that the ow aspect of the Layout is considered. Other aspects,
such as edge crossings or arrow lengths are not relevant here. Previous work, that
investigated similar topics might use di erent terms such as \ ow direction" [
The paper is structured as follows: In the next section, we will introduce related work in the area of BPMN layouting, followed by a clear outline of our research questions in Sect. 3. In Sect. 4, we present the formalization and classi cation algorithm. The identi ed ow directions deducted from a large set of BPMN models found on GitHub are shown in Sect. 5 after which we conclude and provide an outlook. 2
One of the rst questions that arises in our context is how BPMN diagrams are laid out by practitioners. E nger et al. [7, p. 400] state that \[i]n BPMN diagrams the ow direction is usually top-to-bottom or left-to right." This statement is empirically validated by Lubke & Wutke [13, p. 52], who found that 79.52% of BPMN diagrams from their GitHub data set are laid out left-to-right. They also identi ed other layouts, like most prominently, top-down layouts and more complex layouts like multiline and snake layouts.
A more theoretical approach is taken by Figl & Strembeck. [11, p. 60] who state that \[b]asically, there are four main options for the overall direction: leftto-right, top-to-bottom, bottom-to-top, right-to-left.", i.e., they take all four possible main directions as principal layout directions. However, they have also added that \zigzag models" should be subject to future research, thereby recognizing the use of more complex layouts in practice.
All modeling guidelines we found recommend left-to-right layouts, e.g., [
al. [5, p. 49] de ne a guideline (number 43) that process modelers should make their models long and thin by aligning all edges with a general work ow direction as much as possible.
However, more recently, a study by Lubke et al. [12, p. 127] has shown that the understandability of large diagrams pro ts from more complex layouts like snake or multiline layouts in order to avoid the penalty of scrolling these diagrams on screen. For the case of smaller diagrams, this experiment found a slight advantage for left-to-right layouts in contrast to top-down layouts, afrming Figl & Strembeck's earlier experiment. However, the ndings are either minimal (some understandability metrics in the former experiment) or not signi cant (some metrics in the former experiment and all metrics in the latter experiment). 3
In this paper, we want to answer the following research questions.
RQ1: How can diagrams be classi ed automatically? The automatic classi cation of ow layouts has many applications in research to answer questions such as \does the layout choice depend on the size of the diagram" and industry for example to enforce a style guideline.
RQ2: How can ow layouts be formalized objectively? While formalizing all identi ed ow layouts is beyond the scope of this paper, we want to describe how such a formalization could be realized.
RQ3: Which are the most commonly used ow layouts, and are they worth formalizing? By analyzing a large set of diagrams, we identify the most common layouts. Afterwards, we attempt to generalize the layouts to remove any biases that may be introduced by the data set. 4
To classify BPMN diagrams automatically and thus answer the rst research
question, a modular algorithm is designed. Figure 1 illustrates the structure of
the algorithm. First, the BPMN le is parsed and some sanity checks are
performed to determine if the diagram can be classi ed at all. Since some BPMN
editors do not serialize the diagrams in a standard way [1, p. 12], BPMN les
exist, that are, e.g., missing layout data for the elements. For reference, an overview
of the symbols and elements used in the BPMN is shown in the `BPMN-Poster'
by the BPM O ensive Berlin [
The rst of four tasks performed on the layout path is converting it to a vector chain. This is a list of the vectors between the centers of the ow elements on the layout path from the start to the end element. Some special cases need to be considered here. This is demonstrated by the example diagram shown in Fig. 2. Every path in the diagram is directed as straight as possible left to right. Gateways and boundary events do not allow for precisely straight layouts without overlapping the di erent paths.
To handle these cases, the (x or y) component of the vector between the centers of the elements (where the source element is a boundary event or a split, or where the target element is a join) that points in the orthogonal direction to the direction of the split, join or boundary event is set to zero. The direction of one element is determined by the following rules depending on the element type. 1. The element is a boundary event: the direction is horizontal if it is connected to its parent at the top or bottom side; otherwise it is vertical. 2. The element is a split: two cases are di erentiated. Provided that the split element has an incoming sequence ow, the direction is horizontal, if the absolute value of the x component of the vector for the previous sequence ow is bigger than the absolute value of its y component. Otherwise it is vertical. The second case occurs if the split element is a start element. In this case, the direction is determined by constructing a vector that points into the average direction of the outgoing sequence ows of the split element (and comparing the x and y component as above). 3. The element is a join: here the direction is calculated similar as for a split, just in opposite order. First, the next sequence ow is considered, and, if it does not exist (the join is an end element), the average direction of the incoming sequence ows is used. Join elements pose a problem, as the vector for the next sequence ow is not determined when the direction of the join is needed. To circumvent this issue, the direction of the rst sequence ow, on the path from the join to the end element that is not entering another join, is used. If no such sequence ow exists, the average direction of the outgoing sequence ows of the join is used. The colored arrows in Fig. 2 showcase the vector chains which result from this step of the algorithm for each of the four layout paths. The vertical position of the vectors illustrates how each sequence ow is converted into a vector. In reality, only the vectors (x and y components) are relevant. Due to the rules explained above, all vertical (y) components of the vectors are set to zero, resulting in four straight vector chains from left to right.
In the next step, the vector chain is simpli ed by combining subsequent vectors with similar directions. The angle threshold is based on the number of 360 discrete vector directions (NODVD) and calculated by the formula NODVD . The vectors in the simpli ed chain which are a combination of at least two vectors get marked. Marked vectors are those that lay on a straight path in the diagram with at least one element between the start and the end of that path. This marking is important as it allows us to di erentiate between otherwise indistinguishable ow layouts, e.g., Multiline and Snake (see Sect. 5). After that, each vector in the resulting simpli ed vector chain is mapped to a discrete direction. Currently, the NODVD used in the reference implementation is 16. This value was chosen because it felt natural, as a smaller NODVD like 8 would restrict the classi cation to much and a higher value like 32 would prevent many combinations of vectors and thus require diagrams to adhere very closely to a speci c ow layout to be classi ed as that layout. The calculation of the angle threshold in the previous step guarantees that no two consecutive vectors have the same discrete direction.
To determine the ow layout for the path, the list of discrete vector directions is classi ed using regular expressions (see Sect. 5). In the end, the ow layout for the whole diagram is de ned as the ow layout that occurs for most of the paths. 5
Rather than trying to describe every possible ow layout, our goal is to nd
commonly used layouts, formulate their distinguishing features, and build a
classi cation algorithm that can detect these layouts and is extendable to possibly
handle other layouts that are deemed worthy of classi cation in the future. Lubke
and Wutke identi ed six ow layouts while manually classifying 5299 diagrams:
Left-Right, Top-Down, Snake Horizontal, Snake Vertical, Multiline Horizontal
and Multiline Vertical [
The seven categories of ow layouts that have been identi ed to answer RQ3, are: Straight, L, Multiline, Stairs, Snake, U and Z (Fig. 4). Multiple variants of ow layouts exist for each of these categories. Left-Right, Top-Down, Right-Left and Down-Top are the four variants of the straight category. Other categories can have more distinct ow layouts. One example is the multiline category. Eight variants can be di erentiated as shown in Fig. 5. Even though not all these variants occur in the data set, they are all possible multiline layouts and should thus be identi able. This extension allows us to generalize the usability of the classi cation by removing biases introduced by the data set as best as possible.
Figure 6 illustrates the distribution of the automatic classi cation for the large data set. The left diagram shows the seven ow layouts, the right diagram the four variants of the Straight ow layout. Diagrams that could be analyzed (no le reading error, no missing layout information,...) but not classi ed are shown as Other. The Mixed category in the right chart contains diagrams where two thirds of the layout paths where classi ed as Straight but no single variant of the Straight category occurred for this many paths. Not analyzable Diagrams are not shown, 5315 of the 53984 .bpmn les where not analyzable as they contained some syntactic error or missed layout information etc. The charts demonstrate how strongly the Straight ow layout is favored especially in the Left-Right and Top-Down variants (note the logarithmic scale). 6
By analyzing a large data set of BPMN diagrams, we demonstrated that there are many ow layouts which are used for multiple diagrams. Subsequently, we identi ed seven categories of commonly used layouts. Formalizing ow layout with the use of regular expressions on discretized vector chains for each layout path is sensible. The formalization allowed us to create an algorithm and a tool implementation that showed promising results and can, e.g., be used by researchers to answer questions such as how diagram layouting di ers between less experienced users and experts of BPMN. The tool can also be used by teams in the industry to validate models against their layout guidelines. This paper provides a concise overview of our work but fails to describe every detail of the complex subject that is layout detection. Examples of aspects that were considered but not explicitly reported in this paper are: the impact of swimlanes or subprocesses on ow layouts and how an accuracy score can be determined to indicate how exact a diagram is adhering to a particular ow layout. Furthermore some parts of the parameterization of the algorithm where chosen by feel and might appear arbitrary. For example determining the optimal NODVD based on more scienti c metrics than `does it feel natural' could be an interesting topic for future work to investigate.