networkx图中不存在的边列表？

Question

我有一个networkx图表.随着G.edges()我可以得到所有边的列表.但有没有办法获得所有其他不存在的边的列表？所以,如果有3个节点:a,b,c,我们假设a和b只是连接,那么我想获得一个不存在的边列表,如下所示:(a,c), (c,b).有一种简单的pythonic方法吗？

Answer 1

networkx 1.9中实际上有一个名为non_edges的新功能,仅用于此目的:

import networkx as nx
G = nx.MultiGraph()
G.add_edges_from([('A', 'B'), ('B', 'C')])
list(nx.non_edges(G))

Out[3]:
[('A', 'C')]

我把non_edges放在一个list()命令中,以实现输出,就像nx.non_edges生成器一样.在处理大型图形时,使用生成器非常有用.

Answer 2

请注意，Ezekiel Kruglick 展示了一种更好的方法来做到这一点，现在 networkx 有一个non_edges（还有一个non-neighbors）函数。

您可以使用 遍历所有可能的边itertools.combinations，并使用以下方法检查它是否不是 G 中的边G.has_edge：

import networkx as nx
import itertools as IT
G = nx.MultiGraph()
G.add_edges_from([('A', 'B'), ('B', 'C')])

missing = [pair for pair in IT.combinations(G.nodes(), 2)
           if not G.has_edge(*pair)]
print(missing)

产量

[('A', 'C')]