NetworkX style spring model layout for oriented graphs in Graphviz / PyGraphviz
NetworkX is mainly for graphical analysis, PyGraphviz is mainly for drawing, and they are designed to work together. However, there is at least one respect in which the NetworkX graphical drawing (via MatPlotLib) is superior to the PyGraphviz graphical drawing (via Graphviz), namely that NetworkX has a spring layout algorithm (accessible via a function spring_layout
) specifically for directed graphs while PyGraphviz has several spring layout algorithms (programmatically accessible neato
and others) that expose directed graphs as if they were undirected graphs. The only Graphviz / PyGraphviz layout program that does indeed handle direction in a graph dot
, but dot
creates hierarchical layouts, not power layouts.
Here is an example that shows the difference between NetworkX and PyGraphviz for spring oriented graph layouts:
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_80c7eab443.jpg )
The third and fourth figures are basically identical, but for the arrowheads (the whole figure is rotated, but other than that there is no difference). However, the first and second digits are laid out differently - and not just because the NetworkX layout algorithm introduces an element of randomness.
Repeated execution of the code above shows that this is not an accident. The NetworkX function spring_layout
was apparently written under the assumption that if there is an arc from one node to another, the second node should be closer to the center of the graph than the first (i.e. if the graph described in edgelist
, node 2 should be closer to node 9 than nodes 1 and 3, node 6 should be closer to node 9 than node 4, and node 8 should be closer to node 9 than node 7, this doesn't always work perfectly as we can see from nodes 4 and 5 in the first picture above, but that's a small problem compared to getting both 2 and 9 near the center and the "error" is very minor from my point of view). In other words, NetworkX spring_layout
is hierarchical and enforceable.
This is a nice feature because it makes the core / periphery structures more obvious in directed graphs (where, depending on the assumptions you are working with, nodes with no incoming arcs can be considered part of the periphery, even if they have a large number of outgoing arcs). @skyebend explained below why most layout algorithms treat directed graphs as if they were undirected, but the graphs above show (a) that NetworkX treats them differently and (b) that it does it in a fundamental way, which is useful for analysis.
Can this be reproduced with PyGraphviz / Graphviz?
Unfortunately, the documentation and the commented source code for the NetworkX function spring_layout
(in fact fruchterman_reingold_layout
) do not provide information on why NetworkX produces the result it does.
This is the result of using PyGraphviz to draw the network using the NetworkX function spring_layout
(see my own answer to this question below). 5_pygraphviz_plus_networkx.png: ( http://farm9.staticflickr.com/8378/8520231183_e7dfe21ab4.jpg )
source to share
Ok, I think I figured it out, so I'm going to answer my own question. I don't think it can be done in PyGraphviz as such. However, it is possible to instruct PyGraphviz to take the node positions from NetworkX, but bind them (using !
) so that the program neato
doesn't actually allow you to actually do anything other than rubber-stamping the node positions calculated for spring_layout
. Add the following lines of code to the following:
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')
The result is not perfect - I had to multiply the coordinates by 10 to stop the nodes from hovering over each other, which is (obviously) a kludge, but it's an improvement, i.e. the nodes with 0-independent are on the outside (advantage of laying out with NetworkX) and there are correct arrowheads that are not absorbed by the nodes themselves (advantage of drawing with PyGraphviz).
I know this is not strictly what I asked for though (i.e. a solution using PyGraphviz / Graphviz).
If anyone can suggest a better solution, I will be happy!
EDIT: No one has given a better solution to the problem as stated above, so I'm going to accept my own answer to let me know that it actually works. However, I also voted skyebend's answer because while it does not solve the problem, it is a very useful contribution to understanding the underlying issues.
source to share
Graphviz also has fdp and sfdp layout mode to force node placement, similar to spring layout. I'm not familiar with NetworkX, but it seems like it gvu.layout(prog='fdp')
might work? If NetworkX allows you to pass additional arguments to Graphviz, there are a number of custom layout options that you can tweak, which can give you a layout closer to what you want. See the Graphviz docs: http://www.graphviz.org/content/attrs
However, fdp layouts treat the network as an undirected graph. Most of the "spring" layouts I know also treat networks as non-directional because they have to transform them into Euclidean space (screen) where the distances are symmetrical. One exception would be spring "magnetic" layouts, which also tried to align the arcs to point in a similar direction to convey the hierarchy, as a neato / dot hybrid.
Algorithm implementations can also differ in how they convert network distances in a directed network to undirected weights / distances that need to be optimized by the layout. You can explicitly do this step yourself if you want more control over how directional arcs are interpreted.
source to share