Graphviz / PyGraphviz 中有向图的 NetworkX 风格弹簧模型布局

NetworkX 主要用于图形分析，PyGraphviz 主要用于绘图，它们被设计为协同工作。然而，至少在一个方面，NetworkX 的图形绘制（通过 MatPlotLib）优于 PyGraphviz 的图形绘制（通过 Graphviz），即 NetworkX 具有 spring 布局算法（可通过spring_layout函数）专门用于有向图，而 PyGraphviz 有几种弹簧布局算法（可通过neato程序和其他）将有向图布置得就像无向图一样。唯一真正处理图形方向的 Graphviz / PyGraphviz 布局程序是dot, but dot创建分层布局，而不是强制导向布局。

下面的示例显示了 NetworkX 和 PyGraphviz 在有向图的弹簧布局方面的差异：

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 http://farm9.staticflickr.com/8516/8521343506_0c5d62e013.jpg)

2_networkx_undirected.png:(http://farm9.staticflickr.com/8246/8521343490_06ba1ec8e7.jpg http://farm9.staticflickr.com/8246/8521343490_06ba1ec8e7.jpg)

3_pygraphviz_directed.png:(http://farm9.staticflickr.com/8365/8520231171_ef7784d983.jpg http://farm9.staticflickr.com/8365/8520231171_ef7784d983.jpg)

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

绘制的第三个和第四个图形基本相同，但箭头不同（整个图形已旋转，但除此之外没有任何区别）。然而，第一张图和第二张图的布局不同 - 这不仅仅是因为 NetworkX 的布局算法引入了随机性元素。

反复运行上面的代码表明这不是偶然发生的。网络X的spring_layout函数显然是基于以下假设编写的：如果存在从一个节点到另一个节点的弧，则第二个节点应该比第一个节点更靠近图的中心（即，如果中描述的图edgelist有向，节点 2 应该比节点 1 和 3 更靠近节点 9，节点 6 应该比节点 4 更靠近节点 9，节点 8 应该比节点 7 更靠近节点 9；正如我们从上面第一张图中的节点 4 和 5 看到的那样，这并不总是完美地工作，但与将 2 和 9 都靠近中心相比，这是一个小问题，并且从我的角度来看，“错误”非常轻微） 。换句话说，NetworkX 的spring_layout既是等级制的又是强制导向的。

这是一个很好的功能，因为它使核心/外围结构在有向图中更加明显（其中，根据您正在使用的假设，没有传入弧的节点可以被视为外围的一部分，即使它们有大量输出弧）。 @skyebend 在下面解释了为什么大多数布局算法将有向图视为无向图，但上面的图显示 (a) NetworkX 以不同的方式对待它们，(b) 它以有助于分析的原则性方式这样做。

可以使用 PyGraphviz / Graphviz 复制吗？

不幸的是文档 http://networkx.github.com/documentation/latest/reference/generated/networkx.drawing.layout.spring_layout.html和评论的源代码 http://networkx.github.com/documentation/latest/_modules/networkx/drawing/layout.html对于 NetworkX 来说spring_layout（实际上fruchterman_reingold_layout) 函数没有提供任何线索来解释为什么 NetworkX 会产生这样的结果。

这是使用PyGraphviz使用NetworkX绘制网络的结果spring_layout函数（请参阅下面我自己对此问题的回答）。 5_pygraphviz_plus_networkx.png： （http://farm9.staticflickr.com/8378/8520231183_e7dfe21ab4.jpg http://farm9.staticflickr.com/8378/8520231183_e7dfe21ab4.jpg)

好吧，我想我已经弄清楚了，所以我要回答我自己的问题。我不认为can在 PyGraphviz 本身中完成。然而，我们可以指示 PyGraphviz 从 NetworkX 获取节点位置，但将它们固定（使用!） 所以这样neato除了对由以下方法计算的节点位置进行橡皮图章之外，程序实际上无法执行任何操作spring_layout。在上面添加以下代码行：

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')

结果并不完美——我必须将坐标乘以 10 才能阻止节点被绘制在彼此之上，这（显然）是一个拼凑——但它是一个改进，即具有0 入度位于外部（使用 NetworkX 布局的好处），并且有适当的箭头，不会被节点本身吞没（使用 PyGraphviz 绘图的好处）。

我知道这并不是我所要求的（即使用 PyGraphviz / Graphviz 本身的解决方案）。

如果有人能提供更好的解决方案，我会很高兴！

编辑：没有人为上面阐述的问题提供更好的解决方案，所以我将接受我自己的答案以表明它确实有效。然而，我也对 skyebend 的答案进行了投票，因为尽管它不能解决问题，但它对于理解根本问题非常有用。