Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

iPRALINE: Interactive Problem Analysis and Solving in Complex Industrial Networks

Project Title: iPRALINE: Interactive Problem Analysis and Solving in Complex Industrial Networks
Status: completed
Researchers: Alexander Wolff (local PI), Johannes Zink
Funding: Zentrales Innovationsprogramm Mittelstand (ZIM) of the German Federal Ministry for Economic Affairs and Energy (BMWi)
Cooperation Partners: Infosim GmbH & Co. KG, Würzburg
denkbares GmbH, Würzburg
Term: 2019\04–2021\03

The goal of the project was to visualize technical networks (e.g., computer networks and circuit or cable diagrams) and abstract networks (e.g., knowledge networks) in such a way that domain experts can quickly orient themselves and can analyze critical points of these networks efficiently.

The main results are described in more detail below. The algorithms, in particular the layer-based algorithm, have been implemented prototypically. They are tested and used by our project partners.

praline data structure

We have developed a new json data format for graphs with ports, port groups, port pairings, vertex groups, edge bundles, labels and some more. This data format serializes the following data structure model, which we have implemented in Java. This implementation is also available on github:

layered drawing algorithm

For drawing graphs in praline format (typically these are cable plans, circuit diagrams, network diagrams, ...) we have developed a layouting algorithm based on the famous layer-based algorithm of Sugiyama et al. (1981) and procedures and substeps building on it. The main principle is that the vertices are arranged on a few parallel horizontal lines and the drawing gets along with as short edges and as few crossings as possible. Among other things, we have extended the algorithm to allow port pairings and (recursively nested) port groups. This also resulted in a paper at the renowned Symposium on Graph Drawing and Network Visualization in 2020. The article is available on the web pages of Springer and arXiv.

The algorithm is particularly suitable for the visualization of cable plans. The following is an example of such a cable plan, created by obscuring and slightly modifying a real industrial cable plan.

force-directed drawing algorithm

As a second layouting algorithm for graphs in the praline format, we used a force-directed graph drawing algorithm. The principle of such an algorithm is to model each vertex of the graph as a physical particle. Between adjacent vertices, a spring force acts to bring the vertices to an optimal distance, and, between non-adjacent vertices, repulsive forces act. An iterative calculation of forces and positions is performed until equilibrium is reached. The challenge in our case is that we want our vertices to be drawn as rectangles of different sizes, but the classical force-directed algorithm does not take their shape into account, which can lead to numerous overlaps. We solve this by shifting the rectangles (left image) or scaling them and modifying the force-directed algorithm (right image).

(Status of 2021/03/15)