Planare Graphenlayouts

Question

Was sind einige Kantenüberlappungs -Minimierungstechniken beim Auslegen eines Diagramms? (Vorzugsweise im Zusammenhang mit GraphViz) Gibt es auch eine vorhandene Software, die ein Diagramm planar lagern kann?

Aktuelles Layout - http://www.evecakes.com/doodles/master.gif

Der rosa Abschnitt in der oberen linken Ecke sieht gut aus, während der hellblaue Abschnitt einige vermeidbare Kanten überlappt.

Answer 1

Für allgemeine Grafiken das Problem eines planaren Layouts eines Diagramms mit den kleinsten Kanten (die Kreuzungsnummer) ist np-hard. Es werden also einige heuristische Methoden verwendet (wie die Force Based Layout Algorithmen).

Die folgende Seite beschreibt kurz die Graphviz -Algorithmen und schlägt einige Möglichkeiten vor, sie zum Nutzen zu verwenden. Es enthält auch Links zu den PDFs, die weitere Informationen zu den Algorithmen enthalten sollten:

http://rss.acs.unt.edu/rdoc/library/rgraphviz/html/graphvizlayouts.html

Ich hoffe, das hilft.

Answer 2

Die folgende Open -Source -Java -Bibliothek verfügt über einige Algorithmen, die dazu beitragen können, planare Diagramme auszulegen.http://open.trickl.com/trickl-graph/index.html

Insbesondere bieten die folgenden Klassen analytische Lösungen für das Problem:

Chrobakpaynelayout (Basierend auf der Implementierung von Boost C ++ durch Aaron Windsor))http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreelayout (Basierend auf der verteilten verteilten Lokalisierung in Sensornetzwerken * Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine und Seth Teller)

Was Sie vielleicht tun möchten, ist so etwas als der erste "Versuch", der keine Überschneidungen gewährleistet, obwohl sie möglicherweise nicht gut aussehen. Anschließend können Sie einen mit Kraft gestalteten Algorithmus anwenden, um die Knoten fairer auszuräumen.

Leider wurde die Bibliothek gerade erst veröffentlicht, sodass die Dokumentation nicht mehr ist. Es kann jedoch nützlich sein, wenn man einen tatsächlichen Code und nicht nur die Theorie bereitstellt.