Gibt es einen geeigneten Algorithmus zum Zeichnen eines gemischten Konstituenten- / Abhängigkeitsgraphen in einem Koordinatensystem?

9

Ich suche nach einem Algorithmus zum Zeichnen eines gemischten Konstituenten- / Abhängigkeitsgraphen (für eine sprachliche Anwendung). Ein solcher Graph hätte zwei verschiedene Arten von Eckpunkten (Token, Knoten) und zwei verschiedene Arten von Kanten (hierarchisch, nicht hierarchisch).

Ich bin neu in der Graphentheorie und den Algorithmen im Allgemeinen und hoffe, dass diese Frage nicht z. B. mit den Anforderungen auf Forschungsebene dieser Site kollidiert. Es sollte jedoch allgemein im Rahmen der Theorie liegen .

Das Diagramm müsste von unten nach oben gezeichnet werden (glaube ich), da alle Token mit derselben y-Koordinate angezeigt werden sollten und die y-Koordinaten von Knoten, die Token und / oder Knoten zu Bestandteilen gruppieren, dynamisch berechnet werden müssen. zB über ihren längsten Weg zu einem Token.

Hierarchische Kanten (die zum Gruppieren von Token / Knoten in Bestandteile verwendet werden) sollten eine Mindestanzahl von Biegepunkten (idealerweise 0) aufweisen, es sollte jedoch auch eine Mindestanzahl von Kreuzungen vorhanden sein, die bei Bedarf die erstere Anforderung überschreiben.

Nicht hierarchische Kanten (für Abhängigkeiten verwendet) sollten eine Mindestanzahl von Kreuzungen aufweisen und als Bézier-Kurven gezeichnet werden.

Das nächstbeste, auf das ich gestoßen bin, ist der von Buchheim et al. Verbesserung des Walker-Algorithmus zur Ausführung in linearer Zeit.

Bitte lassen Sie mich wissen, falls es notwendig sein sollte, meine Frage zu verbessern, und vielen Dank im Voraus für Hinweise.

BEARBEITEN:

Wie in einem Kommentar erwähnt, sollte ich erwähnen, dass ich grundsätzlich ein Standard-Diagrammlayout durch einen Algorithmus möchte, den ich - auf lange Sicht - innerhalb der Eclipse GEF- Möglichkeiten bearbeiten und überarbeiten möchte . Ich habe zuvor nach Optionen gesucht, um Graphviz für die Arbeit mit GEF zu gewinnen, aber es scheint keine funktionierende Lösung zu geben, die alle von GEF geerbten Bearbeitungsfunktionen beibehält.

ds.algorithms graph-algorithms cg.comp-geom graph-drawing sd
quelle
Benötigen Sie einen Algorithmus oder ein vorhandenes Tool? Graphviz ( graphviz.org ) kann dies tun. Sie geben das Diagramm an, möglicherweise einige Formatierungsoptionen (für verschiedene Arten von Knoten und Kanten), und das Werkzeug gibt ein angemessen gerendertes Diagramm aus.
Dave Clarke
@ DaveClarke: Danke. Mir ist bewusst, dass Graphviz dies tun kann. Leider scheint es derzeit keine Möglichkeit zu geben, Graphviz mit einem Editor zu verwenden, der auf dem [Eclipse Graphical Editing Framework] (www.eclipse.org/gef) basiert. Daher suche ich nach einem tatsächlichen Algorithmus. Es sei denn, jemand weiß, wie man Graphviz an GEF anschließt / portiert :).
SD
Es hört sich so an, als würde das OP nach einem Algorithmus suchen (oder nach einer Problemformulierung, die die Spezifikation erfasst)
Suresh Venkat
@SureshVenkat: Ja, danke für die Klarstellung.
SD
1
Q hat keine Erwähnung der Bearbeitung & aber im Kommentar lehnen Sie graphviz ab & scheinen anzuzeigen, dass Sie es mit GEF bearbeiten möchten. GEF ist ein allgemeines Framework / API für die visuelle Bearbeitung, auf dem andere "Plugins" aufbauen können. Sie möchten anscheinend ein Standard-Diagrammlayout mit einem Algorithmus, den Sie dann überarbeiten können. Schlagen Sie vor, dass Sie Ihre Frage bearbeiten, um dies widerzuspiegeln. Übrigens glauben Sie, dass graphviz verwendet werden kann, um Koordinaten zu generieren, die dann in einen Diagrammeditor eingespeist werden können.
Bezüglich der

Antworten:

1

Sie scheinen folgendes zu wollen

  • ein Graph-Layout-Algorithmus. Viele Standardalgorithmen verwenden typischerweise kraftbasierte Methoden, bei denen Knoten durch replusive / attraktive "Federn" verbunden sind und der Gleichgewichts- / Niedrigenergiezustand durch eine gewisse Anzahl von Iterationen (der entsprechenden global konstruierten kraftbezogenen Differentialgleichung) erhalten wird. Die Ausgabe des Algorithmus ist ein Satz von 2D- oder 3D-Koordinaten für Knoten und (normalerweise) Kanten.
  • Fähigkeit, die Ergebnisse dieses Algorithmus von Hand zu modifizieren. Wird normalerweise als "Diagrammeditor" bezeichnet. Dies beginnt mit den Koordinaten des Layout-Algorithmus und ermöglicht eine Anpassung.

Zu (1) scheint die vorderste Software graphviz zu sein . Zu (2) siehe zB diese Frage "Was ist der beste Grafikeditor" auf mathoverflow .

Beim Durchsuchen der graphviz-Galerie finden Sie hier zwei Diagrammtypen, die Ihren Wünschen ähneln.

ER-Diagramm und Ampel .

Sie sagen, Sie haben zwei Arten von Kanten. Ein einfacher Weg wäre, gerichtete Kanten "in Richtung oder weg" zu haben, wie im Ampelbeispiel. oder die Kanten können wie im ER-Diagramm auf zwei Arten beschriftet werden. Beide Beispiele zeigen zwei verschiedene Knotentypen mit unterschiedlichen Formen oder Beschriftungen oder Schattierungen usw. Andere Ansätze wären die Verwendung von Farben.

Wie der Mathoverflow Q / As anzeigt, gibt es viele Grafikeditoren. der std mit graphviz ist "dotty". siehe zB pdf "Bearbeiten von Grafiken mit Dotty" von Koutsofious.

Eine andere Technik zum Zeichnen, möglicherweise große Diagramme, besteht darin, strukturelle Zusammensetzungen zu betrachten, z. B. Cliquenzersetzungen.

vzn
quelle