iPRALINE: Interaktive Problemanalyse und -behebung in komplexen industriellen Netzwerken

Es wurde ein neues json-Datenformat für Graphen mit Ports, Portgruppen, Portpaarungen, Knotengruppen, Kantenbündeln, Labeln und einigem mehr entwickelt. Dieses Datenformat serialisiert das folgende Datenstruktur-Modell, welches in Java implementiert wurde. Diese Implementierung ist auch auf github verfübar: https://github.com/j-zink-wuerzburg/praline.git

Zum Zeichnen von Graphen im praline-Format (typischerweise sind das Kabelpläne, Schaltpläne, Netzwerkpläne, …) wurde ein Layoutingalgorithmus entwickelt, der auf dem berühmten lagenbasierten Algorithmus von Sugiyama et al. (1981) und darauf aufbauenden Verfahren und Teilschritten basiert. Das Prinzip ist, dass die Knoten auf wenigen parallelen horizontalen Geraden angeordnet werden und die Zeichnung mit möglichst kurzen Kanten und möglichst wenigen Kreuzungen auskommt. Der Algorithmus wurde u.a. dahingehend erweitert, dass Portpaarungen und (rekursiv verschachtelte) Portgruppen berücksichtigt werden. Daraus ist 2020 auch ein Paper auf dem namhaften Symposium on Graph Drawing and Network Visualization entstanden. Der Artikel ist bei Springer und auf arXiv verfügbar.

Besonders geeignet ist der Algorithmus zur Visualisierung von Kabelplänen. Im Folgenden ein Beispiel eines solchen Kabelplans, der durch Unkenntlichmachung und leichte Modifikation eines realen industriellen Kabelplans entstanden ist.

Als zweiten Layoutingalgorithmus für Graphen im praline-Format haben wir einen kräftebasierten Graphzeichenalgorithmus verwendet. Das Prinzip eines solchen Algorithmus ist es, jeden Knoten des Graphen als ein physikalisches Teilchen zu modellieren. Zwischen benachbarten Knoten wirkt eine Federkraft, die die Knoten auf einen optimalen Abstand bringen will und zwischen Knoten, die nicht benachbart sind, wirken abstoßende Kräfte. Eine iterative Berechnung der Kräfte und Positionen erfolgt bis sich ein Gleichgewicht eingestellt hat. Die Herausforderung in unserem Fall liegt darin, dass unsere Knoten als unterschiedlich große Rechtecke gezeichnet werden sollen, der klassische kräftebasierte Algorithmus deren Form jedoch nicht berücksichtigt, was zu zahlreichen Überlappungen führen kann. Wir lösen dies durch Verschieben der Rechtecke (linkes Bild) oder Skalieren und Modifizieren des kräftebasierten Algorithmus (rechtes Bild).