Wie zeichnet man einen orthogonalen Graphen aus seinen Kanten- und Scheitelpunktdaten?

7

Ich schreibe eine Software und muss einen Graphen orthogonal aus topologischen Daten (Vektor von Kanten, Eckpunkten und deren Konnektivitätsdaten) darstellen.

Diagramme bestehen aus einer Reihe von Scheitelpunkten und einer Reihe von Kanten , die jeweils zwei Scheitelpunkte verbinden. Ein Scheitelpunkt kann eine beliebige Anzahl verbundener Kanten aufweisen, wodurch das Problem erheblich komplizierter wird.

Ich habe einige Artikel gelesen und es sieht so aus, als ob das Kandinsky-Modell das beliebteste ist. Allerdings kenne ich den Algorithmus einfach nicht, jede andere Lösung (Algorithmus), die das Problem löst, ist ebenfalls sehr willkommen.

Nach dem Bearbeiten hinzugefügt

Das folgende Bild zeigt ein Beispiel aus der Praxis für ein Stromnetz, das als Rohdaten betrachtet werden sollte. Um aus diesem Netz ein Diagramm zu erstellen, müssen einige vorbereitende Aufgaben ausgeführt werden.

Eingabedaten:

Eingabedaten

Das Ergebnis, das ich suche, ist wie folgt: Wenn Sie genauer hinschauen, gibt es einige Merkmale:

Das rote Polygon in der Mitte des obigen Bildes (Eingabedaten) stellt ein Umspannwerk dar, das selbst ein Knoten ist und an mehr als 4 Kanten angeschlossen werden kann. Es gibt mehr rote Polygone, aber nur eines kann in das obige Bild eingepasst werden. Wie Sie vielleicht sehen, kann das folgende Bild viel mehr als ein rotes Polygon abdecken, was bedeutet, dass es einen größeren Bereich abbilden kann, sodass das folgende Bild viel dichter ist.

In schematischen Diagrammen behalten rote Polygone (Unterstationen) normalerweise ihre Position relativ zueinander bei. Wenn wir es also schaffen, über die Ausmaße der obigen Karte hinaus zu sehen, indem wir beispielsweise herauszoomen, sollten wir fast ein Dreieck sehen, das offensichtlich am zu sehen ist unten, während der linke links und der untere unten ist ..... (dies ist keine Regel, aber ich dachte, es könnte ein Vorsprung für den gewünschten Algorithmus sein)

Orthogonales Diagramm:

Orthogonales Schema

algorithm vector-graphics Iman
quelle
Bedeutet orthogonal in diesem Zusammenhang, nur vertikale und horizontale Kanten zu verwenden? Suchen Sie nach einer Möglichkeit, mehr als 4 Kanten darzustellen, die sich an einem einzelnen Scheitelpunkt treffen?
Trichoplax
@trichoplax Genau, und ich freue mich über jede Hilfe.
Iman
2
Ist der Graph garantiert planar, so dass der Graph ohne Überlappung der Kanten gezeichnet werden kann, wenn die orthogonalen Kanten für einen Moment vergessen werden?
Daniel M Gessel
1
Allgemeine Graph-Layout-Algorithmen sind schwierig zu programmieren und zu implementieren. Sogar die richtigen aus der Literatur zu finden, ist Schmerz. Sie sollten etwas genauer beschreiben, was Sie erwarten, ein Bild zeichnen.
Joojaa
1
Die Scheitelpunkte haben bereits eine bestimmte Position in 2D (oder auf einer Kugel). Es handelt sich also eher um ein Kantenrouting-Problem. Die triviale Lösung besteht darin, jede Kante zuerst entlang der x-Achse und dann entlang der y-Achse (oder umgekehrt) zu verlegen. Wenn dies richtig ist, kann es hilfreich sein, die Probleme mit dieser trivialen Lösung zu erklären. Ich stelle mir ein Minimierungsproblem vor, indem ich Strafen für die Probleme
Daniel M Gessel

Antworten:

-1

libCola

cola.js (auch bekannt als WebCola) ist eine JavaScript-basierte Neufassung von libcola, die gut mit D3.js funktioniert

http://marvl.infotech.monash.edu/webcola/

Beispiel für ein gerastertes Layout:

http://marvl.infotech.monash.edu/webcola/examples/dotpowergraph.html

OGDF

Öffnen Sie das Graph Drawing Framework

Haben Sie ein orthogonales Layout

Orthogonal: Ortholayout mit Modulen für die Schritte Form und Verdichtung, ClusterOrthoLayout

http://www.ogdf.net/doku.php/ogdf:features

Überprüfen Sie Projekte, die OGDF verwenden

http://www.ogdf.net/doku.php/project:external

HALLO

Menschlicher orthogonaler Layoutalgorithmus

https://vimeo.com/150509722

Kieffer, Steve, Tim Dwyer, Kim Marriott und Michael Wybrow. "Hola: Menschliches orthogonales Netzwerklayout." Visualisierung und Computergrafik, IEEE Transactions on 22, No. 1 (2016): 349 & ndash; 358.

Der Demz
quelle
Das klingt vielversprechend. Könnten Sie bearbeiten, um einige Details zu dem hinzuzufügen, was dies bietet?
Trichoplax
1
Es wäre auch nützlich, einen Überblick über die Funktionsweise der einzelnen Algorithmen zu haben, damit sie verglichen werden können, ohne die Antwort hinterlassen zu müssen.
Trichoplax