Frage:
Alternative für Graphviz mit besserer automatischer Knotenplatzierung für große Grafiken?
Victor Stafusa
2014-02-05 03:24:47 UTC
view on stackexchange narkive permalink

In der Vergangenheit habe ich Graphviz verwendet, um Diagramme zu zeichnen. Es ist ein schönes Werkzeug für kleine Diagramme.

Aber leider ist Graphviz für große Diagramme wirklich zum Kotzen:

  • Es hat immer Kanten gekreuzt, die offensichtlich ohne Kreuz gezeichnet werden konnten.
  • Es überlagert verschiedene Texte und macht sie unlesbar.
  • Es hat kein wiederverwendbares Design (wie CSS), und Sie müssen dieselben Personalisierungen in Knoten und Kanten immer wieder wiederholen noch einmal.
  • Wenn der Benutzer beispielsweise die Positionen zweier Knoten tauschen möchte. Zu diesem Zweck ist es häufig erforderlich, die Quelldatei stark zu hacken und dabei möglicherweise nicht verwandte Teile des Diagramms zu verschrauben.
  • Es ist sehr einfach, kleine Änderungen an einer isolierten Stelle des Grafik, Graphviz erzwingt große größere Änderungen an anderer Stelle und macht häufig die Arbeitsstunden ungültig, um zu überzeugen, dass es richtig gezeichnet wird.
  • Es verschwendet viel Platz in der Grafik und überfüllt gleichzeitig einige Stellen so sehr .
  • Manchmal bilden einige Kanten sehr kurvenreiche Pfade, um den Quellknoten mit dem Zielknoten zu verbinden. Sie weisen seltsame nutzlose Kurven und viele überlagerte seitlich laufende Kanten auf.
  • Es weist Lawineneffekte auf . Triviale Änderungen irgendwo in der Grafik können die Heuristik von Graphviz stören und zu einer völlig anderen Grafik führen.
  • Viele Fehler ...

Ich möchte etwas, das wie folgt lautet: Als Benutzer kann ich einfach:

  • Definieren Sie die Knoten, möglicherweise mit dem anzuwendenden Stil.
  • Sagen Sie, was die Kanten sind, möglicherweise mit dem anzuwendenden Stil.

Und dann gibt das Programm Folgendes aus:

  • Ein Diagramm mit der minimal möglichen Anzahl von Kreuzungen.
  • Hübsch ausgerichtete Knoten sind gut.

Ich möchte NICHT:

  • Fügen Sie viele Hacks zur Eingabe hinzu, nur weil das Tool zu dumm ist, um zu sehen, dass es zwei bestimmte Knoten austauschen könnte
  • Kanten und Knoten müssen manuell positioniert werden.
  • Lawineneffekte erzielen.

Was könnte also ein guter Ersatz für Graphviz sein? Ich möchte wirklich, dass es kostenlos ist.

Hinweis: Das Format, in dem das Diagramm eingegeben werden soll, ist mir egal, solange ich eine Datei mit dem speichern und bearbeiten kann Diagrammbeschreibung (unabhängig von der Sprache dieser Beschreibung). Es besteht also absolut keine Notwendigkeit, sich noch mit der Punktsprache oder Ähnlichem zu befassen (tatsächlich würde ich meine Punktedateien gerne vollständig wegwerfen, da es dort viel mehr Hacks gibt als die eigentliche grafische Beschreibung) / p>

Leute, hier stellen Sie eine Frage (und ich werde den Klappentext "graphviz wirklich scheiße" übersehen, weil Sie gut erklären, warum er "scheiße" ist).
Ein Mitarbeiter sagt, dass d3.js (die meiste) Positionierung richtig macht. Offensichtlich hat es andere nicht so schöne Nebenwirkungen, wie z. B. browserbasiert und dynamisch zu sein (d. H. Nicht jeder erhält die gleiche Ausgabe), sodass es möglicherweise nicht das ist, was Sie wollen.
Bevor ich Graphvis verwendete, erzeugte ich Diagramme in Perl mit Graph :: Easy (und mit Graph). http://search.cpan.org/~tels/Graph-Easy/lib/Graph/Easy.pm Ich würde Graph oder Graph :: Easy nicht empfehlen. Ich bin von ihnen weg migriert, damit mein Perl-Programm eine Punktdatei als Zeichenfolge ausspuckt und Graphvis darauf ausführt.
Nach weiteren Informationen von einem Cow-Orker ist graphviz für den generischen Fall ziemlich gut (ja, wir wissen, wie schlecht die Ausgabe sein kann, aber das Problem ist völlig trivial). Wenn Sie bestimmte Annahmen treffen können (z. B. keine Zyklen), gibt es bessere Algorithmen, aber graphviz scheint sie auch zu bündeln (spielen Sie ein bisschen mit seinen Optionen). Sie benötigen Clustering, und dies wird nur dann einfacher zugänglich, wenn Sie Annahmen über die Eingabedaten verwenden können.
@mirabilos Glauben Sie mir, ich habe bereits viele Optionen ausprobiert (seit 2011). Wenn der Graph keinen Zyklus hätte, würde er zu einer Art Baum ausarten und wäre leicht zu zeichnen. Mein Graph hat jedoch tatsächlich viele Zyklen und hat ungefähr 200 Knoten. Um dies mit graphviz zu handhaben, musste ich das Diagramm in 12 unabhängige Untergraphen aufteilen und die Knoten wiederholen, die in mehr als einem Diagramm angezeigt werden. Außerdem musste ich viele unsichtbare Knoten, Kanten und Cluster hinzufügen. In meinen Diagrammen haben die Cluster nur wenige oder gar keine semantische Bedeutung. Sie sind nur Hacks, um zu versuchen, graphviz zu zwingen, seine Arbeit richtig zu machen.
@Oxinabox, ja das ist traurig. Angesichts der großen Anzahl von Hacks in den Heuristiken, Tags und der Struktur von graphviz denke ich, dass ein Neustart von Null viel besser wäre als eine Gabelung.
Computational Science SE hat hier die gleiche Frage: http://scicomp.stackexchange.com/questions/3315/visualizing-very-large-link-graphs.Besides GraphViz stehen mehrere Optionen zur Verfügung: Free * [JavaScript InfoVis Toolkit] ( http://philogb.github.com/jit/index.html)* [igraph] (http://igraph.sourceforge.net/) Paket für das [R statistische System] (http: //cran.r-project .org /) * [zGrViewer] (http://zvtm.sourceforge.net/zgrviewer.html) * [Große Grafikbibliothek] (http://lgl.sourceforge.net/) Nicht kostenlos * [GraphInsight] (http : //www.graphinsight.com/)
Diese erfüllen nicht die Anforderungen des OP, da es zu manuell ist, aber für einige Benutzer ist [Cupid] (http://nedbatchelder.com/blog/201401/svg_figures_with_cupid.html) eine gültige Vorgehensweise.
Können Sie ein Beispieldiagramm veröffentlichen (oder einen Link dazu bereitstellen), das Sie anlegen möchten?
@Sebastian Nun, ich habe die Firma, in der wir dieses Problem hatten, bereits verlassen. Aber ich kann die Daten in einer Sicherungsdatei irgendwo haben.
Wenn Sie dies tun, veröffentlichen Sie es bitte nicht hier, um rechtliche Probleme zu vermeiden. Sie sollten keine Daten haben, die zu einem Unternehmen gehören, das Sie verlassen haben.
Fünf antworten:
#1
+73
north at graphviz
2014-03-14 03:24:51 UTC
view on stackexchange narkive permalink

Entschuldigung für die Enttäuschung. Graphviz könnte in vielerlei Hinsicht besser sein, aber zu diesem Zeitpunkt sind die Aussichten dafür nicht groß, da AT&T die Arbeit nicht so sehr unterstützt wie in der Vergangenheit und einige der Autoren (wie ich) gegangen sind, um andere zu suchen Arbeit. Wir suchen Leute, die es übernehmen möchten, also lassen Sie es uns wissen.

Wir sind auch von yFiles beeindruckt.

Versuchen Sie auch Tom Sawyer Software; Sie haben viel technisches Talent und haben viel an fortschrittlichen Layoutmethoden und interaktiven Werkzeugen gearbeitet. (Möglicherweise müssen Sie $$$ ausgeben, da die kostenlose Testversion anscheinend nicht mehr angeboten wird.)

In der Frage wurde nicht angegeben, welches spezifische Layout-Tool oder welche Optionen ausprobiert wurden oder wie groß ein "großes" Netzwerk ist Es ist nicht klar, was vorgeschlagen werden soll.

Wenn "groß" möglicherweise Hunderte von Knoten bedeutet, versuchen Sie ordentlich -Goverlap = false (um eine Überlappung der Knotentextbeschriftung zu vermeiden) und möglicherweise -Gmodel = Teilmenge , um ein besseres Clustering zu erreichen. (Diese Optionen sind nicht die Standardeinstellung, da bei der Datenanalyse, z. B. in der Bioinformatik, eine direkte MDS-Einbettung eine genauere Darstellung der Entfernungen im zugrunde liegenden Netzwerk ermöglicht.)

Wenn "groß" möglicherweise Tausende von Knoten bedeutet Bei vielen Tausenden verwenden Sie sfdp anstelle von ordentlich erneut mit -Goverlap = false. (Das Teilmengenabstandsmodell ist in sfdp nicht verfügbar, da nicht klar ist, wie variable Kantenlängen beim Zusammenführen von Kanten in einem hierarchischen Löser behandelt werden sollen.) Ein gutes Beispiel für ein 1054-Knotendiagramm finden Sie hier

Zu "Problemen mit verschwendetem Speicherplatz" bei nicht verbundenen Komponenten siehe auch die Attribute pack und packmode. Die Lösungen für solche Probleme sind nicht offensichtlich (im Grunde versuchen Sie, unregelmäßige Formen mit zusätzlichen Einschränkungen optimal zu verpacken, und manchmal im Maßstab dessen, was die Leute als "groß" betrachten, sodass subquadratische Algorithmen erforderlich sind.) Experimentieren Sie für verbundene Graphen mit -Goverlap-Optionen.

Dies sind die Vorschläge. Ausreden und Erklärungen ...

Was jemand den "Lawineneffekt" nennt, wird auch als Layoutinstabilität in Bezug auf (geringfügige) Änderungen im Eingabediagramm bezeichnet. Dies ist eine Eigenschaft fast aller Batch-Diagramm-Layout-Programme und Constraint-Solver. Sie sollten also nach interaktiven Tools wie dem D3 Spring Embedder Layout suchen, und Tim Dwyer hat bei Microsoft eine Menge großartiger Arbeit geleistet. Vielleicht wird das Graph Layout Toolkit (AGL) eines Tages seine interaktiven Einschränkungsmethoden übernehmen. Nur eine Beobachtung, die meisten Forscher und Programmierer haben nicht versucht, Skalierung, Interaktivität und Ästhetik gleichzeitig anzugreifen (wählen Sie eine der beiden oben genannten Optionen ...).

Das Styling-Problem ist ebenfalls gut Wir hatten einfach keine Zeit / Energie, um das Problem anzugehen, da die meisten Diagramme automatisch generiert werden, sodass Sie Stile in einem Vorverarbeitungswerkzeug oder -skript anwenden können. Es muss auch berücksichtigt werden, dass das Diagramm nicht nur ein statischer Analysebaum ist, sondern dass nach dem Lesen eines Diagramms sein Stylesheet oder die Attribute von Objekten, auf die die Stile angewendet wurden, geändert werden können. Anschließend muss das Diagramm ausgeschrieben werden richtig in einer Weise, die die ursprüngliche Struktur so weit wie möglich beibehält. Nicht unüberwindbar, aber dies sind Details, die sorgfältig durchdacht werden müssen.

Fehler können auf www.graphviz.org unter Fehler- und Problemverfolgung gemeldet werden.

Globales Kantenrouting mit glatten Kurven - schweres Problem. Beachten Sie, dass viele cool aussehende Layouts einiger anderer Werkzeuge gekrümmte Kanten verwenden, aber nur über alles andere zeichnen, was im Weg ist. Ich denke, wir haben diese Funktion auch zu graphviz hinzugefügt. Ich denke auch, dass es ein CHI- oder INFOVIS-Papier gab, das zeigt, dass solche gekrümmten Kanten tatsächlich etwas schwerer richtig zu lesen sind als gerade Linien.

Kreuzungen - Möglicherweise ist eine lokale Optimierung möglich. Ich bin mir nicht sicher, welches Tool verwendet wird. Es ist leicht, konkrete Beispiele aufzuzeigen, bei denen Layouts besser sein könnten, aber es ist schwieriger, eine effektive Lösung zu finden, bei der "minimale Anzahl von Kreuzungen" die Dinge im Allgemeinen nicht schlimmer machen würde.

Beachten Sie, dass ich es bin direkt mit Graphviz verbunden.

Ich habe gestimmt. Stephen North ist ein [anerkannter Experte] (http://scholar.google.co.uk/citations?user=_QJP9-0AAAAJ&hl=de) in der Grafikvisualisierung, und angesichts des Bashs von Graphviz durch das OP ist es wertvoll, seine Erkenntnisse zu haben als Antwort. (Ich verstehe zwar die Frustration des OP, aber die grafische Darstellung ist ein schwieriges Problem.)
#2
+30
Sebastian
2014-03-10 17:51:38 UTC
view on stackexchange narkive permalink

Meine Softwareempfehlung lautet " yEd" - eine kostenlose Anwendung zum Zeichnen von Allzweckgraphen, die sich sehr bemüht, die Probleme zu lösen, auf die Sie gestoßen sind. Nach meinem besten Wissen verwendet diese Software die besten frei verfügbaren Implementierungen der Layoutalgorithmen.

Nun zu der detaillierteren Antwort, die für StackOverflow besser geeignet wäre als für "Softwareempfehlung":

Das Problem, das Sie lösen möchten, ist ein wirklich schwieriges Problem (insbesondere im Sinne von rechenintensiv ). Daher ist es unwahrscheinlich, dass Sie ein Tool finden, mit dem Sie alle Ihre Probleme gleichermaßen lösen können Gut. Es gibt eine Reihe kostenloser Lösungen (GraphViz ist wahrscheinlich eine der besten) und eine ganze Reihe kommerzieller Wettbewerber. Für die kommerzielle yFiles -Grafikzeichnungsbibliothek steht eine plattformübergreifende kostenlose Anwendung (wie in Bier) zur Verfügung, die Sie ausprobieren können. Es kann Daten aus verschiedenen Formaten importieren, Stilzuordnungen auf Ihre Daten anwenden und bietet eine große Sammlung verschiedener Layoutalgorithmen. Es heißt yEd und kann von hier aus ohne Installation in einer Webversion ausgeführt werden. Die Desktop-Version kann als Java-Webstart-Anwendung direkt vom Browser oder nach der Installation eines der eigenständigen Programme für Windows, Linux und Mac gestartet werden.

Einige der Layout-Algorithmen sollten wahrscheinlich nicht verwendet werden mit sehr großen Diagrammen (Zehntausende von Elementen), da sie sehr lange ausgeführt werden oder zu viel Speicher benötigen, aber meistens gibt es mindestens einen Layoutstil, der gut zu Ihren Daten passt. Wenn Sie gegen die API programmieren müssen, müssen Sie die zugrunde liegende Bibliothek (verfügbar für Java, .net, Javascript) lizenzieren, was gegen Ihre "kostenlose" Anforderung verstößt. Dies würde Ihnen jedoch noch mehr Kontrolle über das Layout geben.

Haftungsausschluss : Ich arbeite für das Unternehmen, das dieses (kostenlose) Produkt erstellt. Bei Stack Exchange vertrete ich jedoch nicht meinen Arbeitgeber. Ich habe den größten Teil meiner akademischen und beruflichen Zeit seit Ende der neunziger Jahre mit Grafikzeichnungssoftware verbracht und glaube, dass ich sehr gründliche Kenntnisse über den Markt und die verfügbare Software (sowohl kostenlose als auch kommerzielle) habe. Möglicherweise sind andere Tools verfügbar, und ich hoffe, dass diese Website großartige Alternativen bietet - ich werde sie mit Sicherheit nicht leugnen.

+1. Die OP-Anfrage ist nicht möglich (das Programm gibt eine Grafik mit der minimal möglichen Anzahl von Kreuzungen für eine große Grafik -> NP-hart, also viel Glück). Diese Antwort ist Expertenqualität.
Ich habe auch gestimmt. Wenn es jemals einen Ort gab, an dem sich Experten melden sollten, gibt es schwierige Probleme, und es ist besonders schön, von Experten zu hören, wenn es darum geht, Software zu erhalten.
Verwenden Sie [dottoxml] (https://bitbucket.org/dirkbaechle/dottoxml), um von GraphViz (`.dot`) in ein Format zu konvertieren, das yEd lesen kann.
Als unabhängiger Benutzer von yEd (nicht mit dem Unternehmen verbunden) bestätige ich, dass yEd die beste kostenlose Software ist, die es gibt (und ich habe viele ausprobiert).
#3
+16
Franck Dernoncourt
2014-03-14 05:43:03 UTC
view on stackexchange narkive permalink

Um ganz genau auf die Anfrage der Frage zu antworten, da die beiden anderen Antworten einen großartigen Job gemacht haben, um zu erweitern:

Was Sie fragen, ist nicht möglich. Sie möchten ein Programm, das ein "Diagramm mit der minimal möglichen Anzahl von Kreuzungen" liefert, und Sie haben ausdrücklich darum gebeten, dass das Programm für große Diagramme funktioniert.

Die Bestimmung der Kreuzungsnummer eines Graphen ist jedoch ein NP-hartes Problem (Garey und Johnson zeigten, dass es 1983 NP-vollständig ist).

Daher kann ein solches Programm nicht garantieren, dass der Graph mit der minimal möglichen Anzahl von Kreuzungen in angemessener Zeit gefunden wird, was das Programm unbrauchbar macht.

Es kann eine "relativ kleine" Anzahl von Kreuzungen geben, nicht unbedingt ein globales Minimum.
#4
+5
BrianV
2019-11-15 04:01:36 UTC
view on stackexchange narkive permalink

Dies wird sicherlich als "GraphViz-basierte Lösung" angesehen, aber wenn Sie mit GraphViz arbeiten, sollten Sie Gephi ausprobieren. Es ist weitaus leistungsfähiger, wenn es darum geht, große Grafiken zu verarbeiten.

#5
+1
user11879
2018-11-17 00:04:44 UTC
view on stackexchange narkive permalink

PlantUML ist ein Open-Source-Tool, mit dem Benutzer UML-Diagramme aus einer einfachen Textsprache erstellen können. Die Sprache von PlantUML ist ein Beispiel für eine anwendungsspezifische Sprache. Es verwendet die Graphviz-Software, um seine Diagramme zu erstellen. Es wurde verwendet, um blinden Schülern die Arbeit mit UML zu ermöglichen. PlantUML hilft auch blinden Softwareentwicklern beim Entwerfen und Lesen von UML-Diagrammen.

enter image description here

Entschuldigung, aber das ist überhaupt nicht hilfreich. Der Autor fragt ausdrücklich nach einer Software, die die Probleme besser löst als GraphViz. Dies schließt also offensichtlich GraphViz-basierte Lösungen aus. Und UML-Diagramme sind sicherlich auch nicht die typischen Anwendungen für "große Graphen". Wollten Sie eine andere Frage beantworten?


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...