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

Question

NetworkX主要用于图形分析,PyGraphviz主要用于绘图,它们旨在协同工作.然而,至少有一个方面,NetworkX的图形绘制(通过MatPlotLib)优于PyGraphviz的图形绘制(通过Graphviz),即NetworkX具有弹簧布局算法(可通过spring_layout函数访问)专门用于有向图,而PyGraphviz有几个弹簧布局算法(可通过neato程序和其他方法访问),将有向图布置为无向图.真正处理图形中方向的唯一Graphviz/PyGraphviz布局程序是dot,但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)

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)

绘制的第三和第四个数字基本相同,但对于箭头(整个数字已经旋转,但除此之外,没有区别).然而,第一和第二个数字的布局不同 - 而且不仅仅是因为NetworkX的布局算法引入了随机元素.

重复运行上面的代码表明这不是偶然发生的.NetworkX的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复制吗？

不幸的是,NetworkX (实际)函数的文档和注释源代码没有提供关于NetworkX为什么产生它的结果的线索.spring_layoutfruchterman_reingold_layout

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

Answer 1

好吧,我想我想出来了所以我要回答我自己的问题.我不认为它可以在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,以阻止节点相互叠加,这显然是一个kludge - 但它是一个改进,即节点与0 indegree在外面(使用NetworkX布局的好处)并且有适当的箭头不会被节点本身吞没(使用PyGraphviz绘图的好处).

我知道这并不是我要求的严格要求(即使用PyGraphviz/Graphviz本身的解决方案).

如果有人能提供更好的解决方案,我会很开心!

编辑:没有人提供一个更好的解决方案,如上所述,所以我将接受我自己的答案,表明它确实有效.然而,我也投票给了skyebend的答案,因为 - 虽然它没有解决问题 - 但它对理解潜在问题是一个非常有用的贡献.