Welche Algorithmen eignen sich für das interaktive Zeichnen von Graphen in Echtzeit?

Question

Welche Algorithmen eignen sich für das interaktive/Echtzeit-Grafikzeichnen für Live-Daten und direkte Manipulation?

Andernfalls - welche Bibliotheken verwenden Sie zum Zeichnen von Diagrammen?

Vorschläge;

• Prefuse Informations-Visualisierungs-Toolkit
• Gibt es noch andere?

Übrigens - ich meine Graphen im Sinne der Graphentheorie - Punkte und Linien

• jede Sprache
• Mit "live" meine ich, dass das Diagramm auf dem Bildschirm manipulierbar sein sollte.

Answer 1

Ich würde jede Bibliothek empfehlen, an der Jeff Heer gearbeitet hat:

• D3
• Protovis
• Fackel
• Prefuse

Ich glaube, alle drei Projekte sind quelloffen. Jeff Heer ist ziemlich gut darin, in seinem Code auf Dokumente zu verweisen, zumindest in der Prefuse-Bibliothek. Ein Blick auf den Prefuse-Quellcode:

BalloonTreeLayout : Der verwendete Algorithmus ist der von G. Melançon und I. Herman aus ihrer Forschungsarbeit Circular Drawings of Rooted Trees, Reports of the Centre for Mathematics and Computer Sciences, Report Number INS-9817, 1998.

ForceDirectedLayout.java : Keine Referenz erwähnt, aber es gibt viele Kommentare, die beschreiben, wie es funktioniert.

FruchtermanReingoldLayout.java : Referenzen Jung . Auf ihrer Website habe ich eine Papier mit Hinweisen auf verschiedene Algorithmen

NodeLinkTreeLayout.java : Der verwendete Algorithmus ist der von Christoph Buchheim, Michael Jünger und Sebastian Leipert aus ihrer Forschungsarbeit Verbesserung des Walker-Algorithmus, damit er in linearer Zeit läuft Graph Drawing 2002. Dieser Algorithmus korrigiert Leistungsprobleme in Walkers Algorithmus, der die Methode von Reingold und Tilford für ordentliche Zeichnungen von Bäumen verallgemeinert, um Bäume mit einer beliebigen Anzahl von Kindern an einem bestimmten Knoten zu unterstützen.

RadialTreeLayout.java : Der verwendete Algorithmus ist der von Ka-Ping Yee, Danyel Fisher, Rachna Dhamija und Marti Hearst in ihrem Forschungspapier Animierte Erkundung dynamischer Diagramme mit radialem Layout , InfoVis 2001. Dieser Algorithmus berechnet ein radiales Layout, das mögliche Größenvariationen berücksichtigt und sowohl Orientierungs- als auch Ordnungsbeschränkungen beibehält, um reibungslose und verständliche Übergänge zwischen Layout-Konfigurationen zu erleichtern.

SquarifiedTreeMapLayout : Dieser spezielle Algorithmus ist entnommen aus Bruls, D.M., C. Huizing, und J.J. van Wijk, "Squarified Treemaps" In Data Visualization 2000, Proceedings of the Joint Eurographics and IEEE TCVG Sumposium on Visualization , 2000, S. 33-42. Online verfügbar unter http://www.win.tue.nl/~vanwijk/stm.pdf . Für weitere Informationen über TreeMaps im Allgemeinen siehe http://www.cs.umd.edu/hcil/treemap-history

Answer 2

El prefuse Visualisierungs-Toolkit scheint ein guter Kandidat zu sein.

Prefuse unterstützt einen umfangreichen Satz von Funktionen für die Datenmodellierung, Visualisierung und Interaktion. Es bietet optimierte Datenstrukturen für Tabellen, Graphen und Bäume, eine Vielzahl von Layout- und visuellen Kodierungstechniken, und Unterstützung für Animation, dynamische Abfragen, integrierte Suche und Datenbank-Konnektivität. Prefuse ist in Java geschrieben und verwendet die Java 2D gr in Java Swing-Anwendungen Anwendungen oder Web-Applets integriert werden. Prefuse ist lizenziert unter den Bedingungen einer BSD Lizenz lizenziert und kann frei verwendet werden für sowohl für kommerzielle als auch nicht-kommerzielle Zwecke verwendet werden. (von der Homepage)

Answer 3

Das Zeichnen von Grafiken ist ein weites Feld. Hier ist ein Link zu einer Website der Forschungsgemeinschaft für Graphikzeichnen . Sie veranstalten jährlich eine Konferenz, die sich speziell mit dem Zeichnen von Grafiken befasst. Ich kann auch die Lektüre einiger Veröffentlichungen von Prof. David Harel - eines seiner Forschungsgebiete ist das Zeichnen von Diagrammen, zum Beispiel dieses Papier . Dies scheint im allgemeinen Fall ein schwer zu lösendes Problem zu sein. Vielleicht können Sie Ihre Anwendung auf eine begrenzte Teilmenge von Graphen beschränken (planare Graphen sind wahrscheinlich zu restriktiv). Wahrscheinlich lassen sich einfache Graphen mit einer kleinen Menge von Eckpunkten leichter handhaben.

Answer 4

Es gibt einige schicke Papiere, die mit Graphviz . Insbesondere:

• E.R. Gansner, E. Koutsofios, S.C. North, und K.-P. Vo (1993) "Eine Technik zum Zeichnen gerichteter Graphen"
• S.C. North und G. Woodhull (2002) "On-line Hierarchical Graph Drawing"

Answer 5

Ich verwende die Dot-Sprache zur Beschreibung von Diagrammen. Und die Ausgabe des Dot-Compilers enthält SVG, das in XML vorliegt und in XHTML eingebettet werden kann.

http://en.wikipedia.org/wiki/DOT_language