Qt-Graph-Drawing

Ich habe vor kurzem damit begonnen, die Entwicklung auf einem Projekt, das erfordert, dass Sie mich zu visualisieren, Grafiken, und ich bin auf der Suche für einen anständigen Algorithmus, um dieses problem anzugehen.

Den Graphen ich bin Zeichnung Modell Datenfluss, so dass eine vernünftige Zeichnung könnte von Links nach rechts oder von oben nach unten. Sie sind natürlich, Regie und meist azyklische -- das heißt, es könnte ein paar rückwärts und Kanten, aber diese wäre ein kleiner Anteil und ich würde glücklich sein, entfernen Sie diese vor der Berechnung der vertex-Positionen, wenn eine DAG, die als Eingabe würde eine wesentliche Verbesserung der Laufzeit.

Ich bin mit C++ und Qt für dieses Projekt und bin schon sehr vertraut mit der Elastischen Knoten und der Grafik-Szene Beispiele bietet Qt. Wenn jemand gesehen hat, KCacheGrind, was ich versuche zu tun, ist ähnlich wie das call-graph-Visualisierung.

Meine aktuellen versuche noch ein original-Algorithmus weist jedem Knoten eine Schicht basierend auf seine minimale Entfernung von der Wurzel, und dann versucht, die position der Knoten in jeder Schicht in einer solchen Weise, dass edge crossings minimiert werden. Ich war nicht in der Lage zu implementieren, der Letzte Teil der richtig, und ich glaube, dass das problem NP-Hart.

Was ich Suche ist die Anleitung, welche Arten von algorithmen wurden verwendet, um effizient lösen dieses problem in der Vergangenheit.