NetworkX-Federmodell-Layout für gerichtete Grafiken in Graphviz / Pygraphviz

Question

NetworkX ist meistens für die Graph-Analyse, pygraphviz meist für die Zeichnung, und sie sollen zusammenarbeiten. Es gibt jedoch mindestens einen Respekt, in dem die Grafikzeichnung von NetworkX (über matpllotlib) der Graphenzeichnung von Pygraphviz (über Graphviz) überlegen ist, nämlich dass NetworkX einen Federlayout-Algorithmus hat (erreichbar über die spring_layout Funktion) speziell für gerichtete Grafiken, während Pygraphviz mehrere Spring-Layout-Algorithmen (erreichbar über die neato Programm und andere), die gerichtete Grafiken löschen, als wären sie ungerichtete Grafiken. Das einzige Graphviz / Pygraphviz-Layout-Programm, das die Richtung in einem Diagramm wirklich umgibt, ist dot, aber dot Erzeugt hierarchische Layouts, nicht zwangsgerichtete Layouts.

Hier ist ein Beispiel, das den Unterschied zwischen NetworkX und Pygraphviz für Spring-Layouts von gerichteten Graphen zeigt:

import networkx as nx
import pygraphviz as pgv
import matplotlib.pyplot as ppt

edgelist = [(1,2),(1,9),(3,2),(3,9),(4,5),(4,6),(4,9),(5,9),(7,8),(7,9)]

nxd = nx.DiGraph()
nxu = nx.Graph()
gvd = pgv.AGraph(directed=True)
gvu = pgv.AGraph()

nxd.add_edges_from(edgelist)
nxu.add_edges_from(edgelist)
gvd.add_edges_from(edgelist)
gvu.add_edges_from(edgelist)

pos1 = nx.spring_layout(nxd)
nx.draw_networkx(nxd,pos1)
ppt.savefig('1_networkx_directed.png')
ppt.clf()

pos2 = nx.spring_layout(nxu)
nx.draw_networkx(nxu,pos2)
ppt.savefig('2_networkx_undirected.png')
ppt.clf()

gvd.layout(prog='neato')
gvd.draw('3_pygraphviz_directed.png')

gvu.layout(prog='neato')
gvu.draw('4_pygraphviz_undirected.png')

1_Networkx_Directed.png :(http://farm9.staticflickr.com/8516/8521343506_0c5d62e013.jpg.)

2_Networkx_undirected.png :(http://farm9.staticflickr.com/8246/8521343490_06BA1EC8E7.jpg.)

3_pygraphviz_Directed.png :(http://farm9.staticflickr.com/8365/8520231171_ef7784D983.jpg.)

4_pygraphviz_undirected.png :(http://farm9.staticflickr.com/8093/8520231231_80c7ab443.jpg.)

Die dritte und vierte Figure sind grundsätzlich identisch, aber für die Pfeilspitzen (die gesamte Figur wurde gedreht, aber abgesehen davon gibt es keinen Unterschied). Die erste und zweite Figure sind jedoch anders ausgelegt - und nicht nur, weil der Layout-Algorithmus von NetworkX ein Element der Zufälligkeit einführt.

Der wiederholte Ausführen des oben genannten Codes zeigt, dass dies kein Zufalls-Ereignis ist. NetworkX's. spring_layout Die Funktion wurde anscheinend an der Annahme geschrieben, dass der zweite Knoten, wenn sich ein Bogen von einem Knoten an einem anderen befindet, näher an der Mitte des Diagramms liegen, als der erste (dh wenn das in beschriebene Graph edgelist ist gerichtet, der Knoten 2 sollte näher an den Knoten 9 sein als die Knoten 1 und 3, der Knoten 6 näher am Knoten 9 sein sollte, als der Knoten 4 ist, und der Knoten 8 sollte näher an den Knoten 9 sein, als der Knoten 7 näher ist als der Knoten 7; Dies funktioniert nicht immer perfekt, da wir in der ersten Abbildung von den Knoten 4 und 5 in der ersten Abbildung sehen, aber das ist ein kleines Problem im Vergleich zu den 2 und 9 in der Nähe des Zentrums, und der "Fehler" aus meiner Sicht ist sehr gering) . Mit anderen Worten, NetworkX spring_layout ist sowohl hierarchisch als auch zwangsweise gerichtet.

Das ist ein schönes Merkmal, denn es macht Kern- / Peripheriestrukturen, die in gerichteten Diagrammen offensichtlicher sind (wobei in Abhängigkeit von den Annahmen, mit denen Sie arbeiten, Knoten ohne ankommende Bögen als Teil der Peripherie betrachtet werden können, auch wenn sie große Zahlen haben von ausgehenden Bögen). @skyebend hat unten erläutert, warum die meisten Layout-Algorithmen gerichtete Diagramme behandeln, als ob sie ungerichtet waren, aber die Diagramme oben zeigen (a), dass NetworkX sie anders behandelt, und (b), dass dies auf eine Prinzipielle ist, die für die Analyse hilfreich ist.

Kann dies mit Pygraphviz / Graphviz repliziert werden?

Leider das. Dokumentation und die kommentierte. Quellcode Für NetworkX's. spring_layout (eigentlich fruchterman_reingold_layout) Funktion bietet keinen Hinweis darauf, warum NetworkX das Ergebnis erzeugt, das es tut.

Dies ist das Ergebnis der Verwendung von pygraphviz, um das Netzwerk mit dem NetzwerkX zu zeichnen spring_layout Funktion (siehe meine eigene Antwort auf diese Frage unten). 5_pygraphviz_plus_networkx.png: (http://farm9.staticflickr.com/8378/8520231183_E7DFE21AB4.jpg.)

Answer 1

Okay, ich glaube, ich habe es herausgefunden, so dass ich meine eigene Frage beantworten werde. Ich denke nicht kann in pygraphviz an sich fertig sein. Man kann jedoch pygraphviz anweisen, die Knotenpositionen von NetworkX zu ergreifen, aber sie (unter Verwendung) !) so, dass die neato Das Programm wird daran gehindert, irgendetwas etwas zu tun, außer Gummi-Stempeln, die die von spring_layout. Fügen Sie den obigen folgenden Zeilen des Codes hinzu:

for k,v in pos1.iteritems():
    gvd.get_node(k).attr['pos']='{},{}!'.format(v[0]*10,v[1]*10)

gvd.layout(prog='neato')
gvd.draw('5_pygraphviz_plus_networkx.png')

Das Ergebnis ist nicht perfekt - ich musste die Koordinaten um 10 multiplizieren, um die Knoten daran zu stoppen, dass die Knoten aufeinander gezogen werden, was (offensichtlich) ein Kötung ist - aber es ist eine Verbesserung, dh die Knoten mit 0 Indeye sind außen (Nutzen, mit NetworkX auszulegen) und es gibt ordnungsgemäße Pfeilspitzen, die nicht von den Knoten selbst verschluckt werden (Nutzen der Zeichnung mit Pygraphviz).

Ich bin mir bewusst, dass dies nicht strikt ist, wonach ich gefragt habe (dh eine Lösung mit Pygraphviz / Graphviz selbst).

Wenn jemand eine bessere Lösung bieten kann, bin ich glücklich!

Bearbeiten: Niemand hat das auf artikulierte artikulierte Lösung eine bessere Lösung zur Verfügung gestellt, also akzeptiere ich meine eigene Antwort, um das Signal anzunehmen, dass es eigentlich funktioniert. Ich stimme jedoch auch Skyebends Antwort, denn - obwohl er das Problem nicht löst - ist es ein sehr nützlicher Beitrag, um die zugrunde liegenden Probleme zu verstehen.

Answer 2

Graphviz hat auch einen FDP und SFDP. Layout-Modus zum Tune der Kraft gerichteten Platzierung von Knoten, die analog zu einem Federlayout ist. Ich bin mit NetworkX nicht vertraut, aber es scheint gvu.layout(prog='fdp') könnte funktionieren? Wenn NetworkX die Weitergabe zusätzlicher Argumente in GraphVIZ ermöglicht, gibt es eine Reihe konfigurierbarer Layoutparameter, die Sie optimieren könnten Siehe Graphviz docs: http://www.graphviz.org/content/attrs.

Die FDP-Layouts behandeln jedoch das Netzwerk als ungerichtetes Graph. Die meisten "Frühlingslayouts", die ich kenne, wusste auch Netzwerke als ungerichtet, da sie sie in einen euklidischen Raum (den Bildschirm) verwandeln müssen, in dem die Entfernungen symmetrisch sind. Eine Ausnahme wäre "magnetische" Federlayouts, die auch versuchen, Bögen auszurichten, sodass sie in eine ähnliche Richtung zeigen, um eine Hierarchie zu vermitteln, als Sortieren von neato / dot-Hybrid.

Algorithmus-Implementierungen können sich auch unterscheiden, wie sie die Netzwerkabstände in einem gerichteten Netzwerk umwandeln, um zu ungerichteten Gewichten / Entfernungen, die durch das Layout optimiert werden können. Möglicherweise möchten Sie diesen Schritt explizit selbst machen, wenn Sie mehr Kontrolle über die Art und Weise, wie gerichtete Bögen interpretiert werden möchten.