graph - Graphviz/PyGraphviz 中的有向图的 NetworkX 样式 Spring 模型布局

Question

NetworkX 主要用于图形分析，PyGraphviz 主要用于绘图，它们旨在协同工作。然而，至少在一个方面，NetworkX 的图形绘制(通过 MatPlotLib)优于 PyGraphviz 的图形绘制(通过 Graphviz)，即 NetworkX 具有 Spring 布局算法(可通过 spring_layout 函数访问)用于有向图，而 PyGraphviz 有几种 Spring 布局算法(可通过 neato 程序和其他程序访问)，它们可以像无向图一样布置有向图。唯一真正处理图形方向的 Graphviz/PyGraphviz 布局程序是 dot，但 dot 创建分层布局，而不是强制导向布局。

下面是一个例子，展示了 NetworkX 和 PyGraphviz 在有向图的 spring 布局方面的区别:

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 应该比节点 9 更接近节点 7 是；正如我们从上图第一个图中的节点 4 和 5 中看到的那样，这并不总是完美的，但与将 2 和 9 都放在中心附近以及从我的角度来看的“错误”相比，这是一个小问题非常轻微)。换句话说，NetworkX 的 spring_layout 既是分层的又是强制导向的。

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

这可以使用 PyGraphviz/Graphviz 复制吗？

不幸的是 documentation和评论 source code对于 NetworkX 的 spring_layout(实际上是 fruchterman_reingold_layout)函数没有提供任何关于 NetworkX 产生结果的线索。

这是使用 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 以阻止节点被绘制在彼此之上，这(显然)是一个杂乱无章——但这是一种改进，即度数为 0 的节点在外侧(使用 NetworkX 布局的好处)，并且有适当的箭头不会被节点本身吞噬(使用 PyGraphviz 绘图的好处)。

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

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

编辑:没有人为上述问题提供更好的解决方案，因此我将接受我自己的答案以表明它确实有效。但是，我也对 skyebend 的答案投了赞成票，因为 - 尽管它不能解决问题 - 它对理解潜在问题非常有用。