Implement new features: skipping elements and modeling backwards

till-stadtler commented 2 months ago

Proposed Changes

Unfortunately, creating multiple commits would not have made much sense. I will explain all changes in as much detail as possible.

File: Grid.js The grid now keeps track of its extend, starting from [0,0] to [highestRow,highestColumn]. If an element is added, these numbers are updated via updateHighest. As new rows need to be added to the grid specifically, the function ensureRow has been introduced. When modeling backwards, the column index might go below 0. The function ensureColumn shifts the entire grid, to keep the lowest column index at 0.

Previous addAfter and addBelow functions have been replaced with a collection of more complex functions. These functions search for empty row and/or columns forwards and backwards, taking the extend of the grid into account.

File: Layouter.js The starting elements are now sorted to have start events in front, if they exist. Next to the stack, there is a skipped and reversedSkipped list to keep track of elements that need to be revisited later to either model forwards or backwards. The stack is empty at first. We start looping through the start element, but not to place them all directly, but to place as many as possible from a single start event. As modeling backwards is possible, additional "startingElements" are placed directly in a new row only if they are disjunct from the model, e.g., data objects.

When going through the stack and skipped lists, we work on the stack first. Only if the stack is empty, we visit the skipped list, and only if the skipped list is empty, we visit the reversedSkipped list. The addToGrid function keeps track of the lists, of "forcing" the placement of an element (e.g., because of a merging element that is part of a loop), and if it should model backwards or not.

The elements in the skipped and reversedSkipped lists are sorted before popped, to work with "simpler" and left-most elements first.

File: attacherHandler This was deleted, as all addToGrid functionality had to be put into one function. This is because when one element is forced to be placed, we want to go back and restart from the stack, and not run the other handler with force being true.

File: index.js Adapted because attacherHandler was removed.

File: outgoingHandler The outgoing handler has three parts: working with the attached elements, with standard outgoing elements and with incoming elements (last) to model backwards. The elements are sorted by first, because we want to place splitting elements before merging elements. All three parts check if an element should be skipped to wait for other elements to be placed first. Depending on the type of nextElement, different grid functions are used to place the element (empty row and or column).

If one element is placed, no other element is forced to be placed. Instead we go back and work with the stack again.

Attacher functionality has been integrated. We could keep the attacher handler alive to keep the other functions separate. This is up to you to decide.

File: LayoutUtil.js The cell width was reduced to a more even number (divisible by 4). This placed elements on the grid. The cell height was increased for sequence flows to have more space between elements.

If the source or target is a gateway, we can leave them at different docking points. This behavior can be improved further.

When connecting horizontally, we go via the bottom when going left to right, and via the top when going right to left. This improves readability.

The last path construction has been changed to accommodate source and target gateways. This function has not been tested thoroughly yet. I hope that with all my changes, sequence flows will become simpler in most scenarios!

Visual demo

I will post some example layouts, starting with the bug issues. On top, my own design is shown, below the layouted process. To see the "bad" examples, check the bug issues!

Regarding issue #48:

Example 1: Explanation: The start event is always placed first because the starting elements are sorted. The merging gateway is placed next (from skipped). The following elements are placed. At last, the left intermediate element is placed by modeling backwards.

Example 2: Explanation: Similar to example 1, but with clear illustration why modeling backwards is helpful. If this was not done, the "starting" intermediate event would have been placed below the start event.

Example 3: Explanation: In contrast to before, no new row is created here. When trying to place the merging gateway after the splitting gateway, we skip it first to wait for the activity to be placed. When placing the merging gateway, we take all incoming elements into account.

Regarding issue #49:

Example 4: Explanation: We skip the second splitting gateway and wait for the other branch to be placed first. We then search for an empty column for the second splitting gateway. The order of the elements in the XML is taken into account: This could also be modeled differently with the second merging gateway being placed in the second row.

Regarding issue #50:

Example 5: Explanation: The placement of the second splitting gateway is improved as described before. When connecting element to the top and left, we now go downwards, as we assume it to be a proper loop and not a misplaced merging gateway.

Example 6: Explanation: This example shows the tool waiting to place the merging gateway.

Other examples

Example 7: Explanation: A rather complex linear process being modeled without a second row. The sequence flows are overlapping quite a lot, but that is difficult to improve upon.

Example 8: Explanation: A complex process with modeling many steps backwards, including a splitting gateway.

Example 9: Explanation: Another complex process with many aspects handled well by the tool, including the left link event and the complex middle part.

Checklist

To ensure you provided everything we need to look at your PR:

[x] Brief textual description of the changes present
[x] Visual demo attached
[ ] Steps to try out present, i.e. using the @bpmn-io/sr tool
[x] Related issue linked via Closes {LINK_TO_ISSUE} or Related to {LINK_TO_ISSUE}

till-stadtler commented 2 months ago

This PR still contains the error around the tool failing when boundary events have no outgoing elements.

philippfromme commented 2 months ago

Hey @till-stadtler, first of all, thanks for your contribution and the effort you put into this. It would have been nice if you had assigned yourself to the issues you worked on because in the meantime we assigned @abdul99ahad to them so two people were working on them at the same time - not ideal. Just to manage expectations in terms of reviewing your pull request: It's a complex one and (as you mentioned) it's one big commit making the review a lot more challenging. Why didn't you think it made sense to separate it into several commits?

till-stadtler commented 2 months ago

Hi @philippfromme, Having just one commit might be because of my understanding of commits and of not wanting to commit a broken code base. As the changes are all connected, separating the commit into several commits would lead to the layout failing:

if I change the grid functions to search for empty rows and columns, but not add the "skipped" list to wait with placing certain elements, the layout would be worse than before or even break
if I change the way I handle the startingElements, but not add the "modeling backwards" functionality, again, the layout might be worse or fail

In the end, getting to the current code took a lot of trial and error, especially with sorting the various lists (sortingUtils), so I don't have a meaningful commit history right now. Instead, I would need to artificially separate my changes into commits that might not make much sense on their own.

If I understand commits differently compared to how it is handled in your team, I am sorry. If you have an idea of how I should break up the code changes, I will try to do that!

Sorry for not assigning myself. I was unsure if I was able to create a PR eventually. I communicated with @abdul99ahad a bit, so I hope that he did not work for nothing.

nikku commented 1 month ago

@till-stadtler We'll be able to sort this out. Thanks for your contribution :).

nikku commented 1 month ago

@till-stadtler We created our very own playground for testing the layouter, available online via https://bpmn-io.github.io/bpmn-auto-layout/.

philippfromme commented 1 month ago

@abdul99ahad Does this PR contain features/bug fixes that we haven't covered with any of https://github.com/bpmn-io/bpmn-auto-layout/pulls?q=is%3Apr+is%3Aclosed+author%3Aabdul99ahad? If not, we can close this PR.

abdul99ahad commented 1 month ago

@abdul99ahad Does this PR contain features/bug fixes that we haven't covered with any of https://github.com/bpmn-io/bpmn-auto-layout/pulls?q=is%3Apr+is%3Aclosed+author%3Aabdul99ahad? If not, we can close this PR.

All the issues covered by this PR has been fixed except Example 2.

Example 2: Explanation: Similar to example 1, but with clear illustration why modeling backwards is helpful. If this was not done, the "starting" intermediate event would have been placed below the start event.

The intermediate event is still modeled at the bottom of start event. Do we want to prioritize this?

philippfromme commented 1 month ago

Do we have an issue covering the last missing feature?

abdul99ahad commented 1 month ago

Do we have an issue covering the last missing feature?

The question is does this usecase provides any value to the modeling? I might me wrong but imo the intermediate event should be in the start as eventually it is occupying the complete row.

If not, we can open the issue to cover this case as well.

nikku commented 1 month ago

The question is does this usecase provides any value to the modeling?

I agree. Example 2, as I see it, contradicts with example 1, our algorithm is already stable enough, hence I think we can safely ignore it (for now) and await further future feedback.

abdul99ahad commented 1 month ago

Since most of the relevant things are completed in the PR https://github.com/bpmn-io/bpmn-auto-layout/pull/68 and other. Closing this PR. If there's any urgent follow-up, feel free to open new issues.

bpmn-io / bpmn-auto-layout