piwik-script

English Intern
    Lehrstuhl für Informatik I - Algorithmen und Komplexität

    iPRALINE: Interaktive Problemanalyse und -behebung in komplexen industriellen Netzwerken

    Projekttitel: iPRALINE: Interaktive Problemanalyse und -lösung in komplexen industriellen Netzwerken
    Status: abgeschlossen
    Forscher: Alexander Wolff (lokaler PI), Johannes Zink
    Finanzierung: Zentrales Innovationsprogramm Mittelstand (ZIM) des Bundesministeriums für Wirtschaft und Energie (BMWi)
    Kooperationspartner: Infosim GmbH & Co. KG, Würzburg
    denkbares GmbH, Würzburg
    Laufzeit: 04.2019–03.2021

    Ziel des Projekts war es, technische Netzwerke (z.B. Rechnernetze und Schalt- oder Kabelpläne) und abstrakte Netzwerke (z.B. Wissensnetze) so zu visualisieren, dass Domänenexperten sich schnell orientieren und insbesondere kritische Stellen der Netzwerke effektiv analysieren können.

    Nachfolgend werden die Hauptergebnisse genauer beschrieben. Die Algorithmen, insbesondere der lagenbasierte Algorithmus, wurden prototypisch implementiert und von den Projektpartnern getestet und verwendet.

    praline-Datenstruktur

    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

    Lagenbasierter Zeichenalgorithmus

    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 leichter Modifikation eines realen industriellen Kabelplans entstanden ist.

    Kräftebasierter Zeichenalgorithmus

    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 diese durch Verschieben der Rechtecke (linkes Bild) oder Skalieren und Modifizieren des kräftebasierten Algorithmus (rechtes Bild).

    (Stand 15.03.2021)