[DMN Designer] Automatic Layout Feature

DMN Designer should autolayout new imported DMN models. The autolayout should position DRG diagram nodes into horizontal layers to minimize crossing of connectors with respect of Top-Down importance. It means if nodes Layer B are inputs for nodes in Layer A then the Layer B will be below Layer A. The autolayout should also try to minimize scrolling needed to see whole DRG diagram.

User should also have possibility to invoke autolayout feature any time during designing the diagram. In this case the action should be undoable with the Undo toolbar button.

The approach used to achieve this is the Sugiyama Method, which is done in 4 steps. Each step have its own set of algorithms. For each step, we selected one of the available algorithms to implement, based on our current needs and time to develop:

Step 1 - Cycle breaking: We break cycles in diagram by reversing some edges (they are de-reversed in the end). This step are required because we need ending points in step 2 while sweeping through graph;

Step 2 - Layering: We sweep through graph (diagram) and put each node (vertex) in a layer, based on it's distance from others node. For edges that crosses multiple layers, we create virtual vertices connecting those. They are removed at the end.
This approach usually puts the start nodes at the top and the deepest nodes at the end. In the current implementation we're using Longest Path algorithm. A better approach can be developed in future using Network Simplex;

Step 3 - Node Ordering: We order each node (vertex) inside its layers in order to reduce crossing, using median. Another approach that can be used is barycenter.

Step 4 - Node Positioning: We de-reverse nodes reversed in step 1 and remove virtual nodes reconnecting the concrete nodes. Then we calculate the position of each node. This step can be divided in two steps: one for horizontal position and other for vertical for better positioning. Currently we're using a simple approach: every block of nodes inside the layers is centered and the distance between layers is the same. So it will produce results like the attachment "Automatic Layout Demo".

Architecture
From the design of view the goals are:

• Layout Public interface & DMN implementation
  • The goal for this API is to provide the layout declaration data for an input Graph (DMN, BPMN, etc) instance. It will NOT mutate the graph structure and/or data at all. This way it will provide methods for calculating the candidate locations for the graph elements. even could be the case the elements must be resized as well, and it returns on some result data object that specifies the necessary updates to be done on the elements. So the resulting layout data will be consumed by another component that will use the command API in order to perform the necessary updates (location, size) for the graph' elements.
  • Build a well defined layout API (shared) on some api module
  • Build the requested layout implementation specific for DMN inside some DMN shared module (considering the implementation is shared between client and server)
  • Any other common or base classes can be placed inside the commons module

• Designer integration
  • Once having the layout API and implementations, next step is to consume this API in order to obtain the layout data and use it to mutate the graph structure. So we need some kind of component for this, for example we can name it as LayoutExecutor.
  • Create some default layout executor which will consume the layout API and use the command API to perform the updates on the model (graph) via "commands", this way we can undo/redo all the operations on the designer
  • [Optional] This designer integration can be done as generic, and so reuse it for other domains like BPMN, or just specific for DMN