Alternative für Graphviz mit besserer automatischer Knotenplatzierung für große Graphen?

Sorry für die Enttäuschung. Graphviz könnte in vielerlei Hinsicht besser sein, aber derzeit sind die Aussichten dafür nicht besonders gut, da AT&T die Arbeit nicht mehr so ​​sehr unterstützt wie in der Vergangenheit und einige der Autoren (wie ich) gegangen sind, um sich nach anderen umzusehen Arbeit. Wir suchen Leute, die das übernehmen wollen, also lass es uns wissen.

Wir sind auch von yFiles beeindruckt .

Probieren Sie auch Tom Sawyer Software aus ; Sie haben viel technisches Talent und haben viel an fortschrittlichen Layoutmethoden und interaktiven Tools gearbeitet. (Möglicherweise müssen Sie $$$ ausgeben, da die kostenlose Testversion anscheinend eingestellt wird.)

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

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

Wenn "groß" Tausende von Knoten bedeutet, vielleicht viele Tausend, verwenden Sie sfdpstatt neatowieder -Goverlap=false. (Das Subset Distance Model ist in sfdp nicht verfügbar, da nicht klar ist, wie mit variablen Kantenlängen beim Zusammenführen von Kanten in einem hierarchischen Solver umgegangen werden soll.) Hier sehen Sie ein gutes Beispiel für ein Diagramm mit 1054 Knoten

Für "Platzverschwendungsprobleme" bei nicht angeschlossenen 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 optimal zu packen, mit zusätzlichen Einschränkungen und manchmal in der Größenordnung dessen, was die Leute als "groß" betrachten, sodass subquadratische Algorithmen erforderlich sind.) Experimentieren Sie mit verbundenen Graphen mit -Goverlap-Optionen.

Das sind die Vorschläge. Was Ausreden und Erklärungen angeht...

Was jemand den "Avalanche-Effekt" nennt, wird auch als Layout-Instabilität in Bezug auf (geringfügige) Änderungen im Eingabegraphen bezeichnet. Dies ist eine Eigenschaft von fast allen Batch-Graph-Layout-Programmen und Constraint-Solvern. Sie sollten also nach interaktiven Tools wie dem D3-Spring-Embedder-Layout suchen, und Tim Dwyer hat viel großartige Arbeit daran geleistet, als er bei Microsoft war. Vielleicht wird ihr Graph Layout Toolkit (AGL) eines Tages seine interaktiven Constraint-Methoden übernehmen. Nur eine Beobachtung, die meisten Forscher und Programmierer haben nicht versucht, Skalierung, Interaktivität und Ästhetik gleichzeitig anzugreifen (wählen Sie zwei der oben genannten ...)

Das Styling-Problem ist auch gut, wir hatten einfach keine Zeit/Energie, um es anzugehen, da die meisten Diagramme automatisch generiert werden, sodass Sie Stile in einem Vorverarbeitungstool oder Skript anwenden könnten. Außerdem muss berücksichtigt werden, dass der Graph nicht nur ein statischer Parse-Baum ist, sondern nachdem ein Graph gelesen wurde, sein Stylesheet oder die Attribute von Objekten, auf die die Stile angewendet wurden, geändert werden können, und dann der Graph geschrieben werden muss so korrekt, dass die ursprüngliche Struktur noch so weit wie möglich erhalten bleibt. Nicht unüberwindbar, aber das sind Details, die sorgfältig durchdacht werden müssen.

Bugs können auf www.graphviz.org unter Bug and Issue Tracking gemeldet werden.

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

Kreuzungen - einige lokale Optimierungen könnten möglich sein. Nicht sicher, welches Tool verwendet wird. Es ist einfach, auf konkrete Beispiele hinzuweisen, bei denen Layouts besser sein könnten, aber schwieriger, eine effektive Lösung zu erfinden, bei der eine „Mindestanzahl von Kreuzungen“ die Dinge im Allgemeinen nicht wirklich verschlechtern würde.

Beachten Sie, dass ich direkt mit Graphviz verbunden bin.

Meine Software-Empfehlung ist " yEd " - eine kostenlose Allzweckanwendung zum Zeichnen von Graphen, 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 zur ausführlicheren Antwort, die eher für StackOverflow als für "Software Recommendation" geeignet wäre:

Das Problem, das Sie zu lösen versuchen, ist ein wirklich schwieriges Problem (insbesondere im Sinne von rechenintensiv ), daher ist es unwahrscheinlich, dass Sie ein Tool finden, das alle Ihre Probleme gleich gut lösen kann. Es gibt eine Reihe kostenloser Lösungen (GraphViz ist wahrscheinlich eine der besten) und eine ganze Reihe kommerzieller Konkurrenten. Für die kommerzielle Grafikzeichnungsbibliothek yFiles steht eine kostenlose (wie in Bier) plattformübergreifende Anwendung zur Verfügung, die Sie ausprobieren können. Es kann Daten aus verschiedenen Formaten importieren, Style-Mappings auf Ihre Daten anwenden und bietet eine riesige Sammlung verschiedener Layout-Algorithmen. 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 aus dem Browser oder nach der Installation eines der eigenständigen Programme für Windows, Linux und Mac gestartet werden.

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

Haftungsausschluss : Ich arbeite für das Unternehmen, das dieses (kostenlose) Produkt herstellt, vertrete jedoch nicht meinen Arbeitgeber auf Stack Exchange. Ich habe seit den späten 1990er Jahren den größten Teil meiner akademischen und beruflichen Zeit mit Diagrammzeichnungssoftware verbracht, und ich glaube, ich habe sehr fundierte Kenntnisse über den Markt und die verfügbare Software (sowohl kostenlose als auch kommerzielle). Möglicherweise sind andere Tools verfügbar, und ich hoffe, dass diese Website großartige Alternativen aufzeigen kann - ich werde sie sicherlich nicht leugnen.

Um sehr spezifisch auf die Anfrage der Frage zu antworten, da die anderen beiden Antworten großartige Arbeit geleistet haben, um sich zu erweitern:

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

Die Bestimmung der Kreuzungszahl eines Graphen ist jedoch ein NP-schweres Problem (Garey und Johnson haben 1983 gezeigt , dass es NP-vollständig ist).

Daher kann ein solches Programm nicht garantieren, den Graphen mit der minimal möglichen Anzahl von Kreuzungen in einer angemessenen Zeit zu finden, was das Programm unbrauchbar macht.

Dies würde sicherlich als "GraphViz-basierte Lösung" angesehen werden, aber wenn Sie mit GraphViz arbeiten, sollten Sie sich Gephi ansehen . Es ist weitaus leistungsfähiger, wenn es um die Verarbeitung großer Diagramme geht.

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 Studenten zu ermöglichen, mit UML zu arbeiten. PlantUML hilft auch blinden Softwareentwicklern, UML-Diagramme zu entwerfen und zu lesen.