计算 networkx 中两个图 'edge wise' 之间的差异

Question

我想使用 networkx 库比较两个图。我想尝试包含 3 个节点的硬编码示例。其中一张图被引用，所以我想检查第二张图的边缘是否在同一个地方。我在考虑简单的算法，该算法将从给定的参考图中减去参考图，如果结果不是空图，则它 returns false。

我的代码如下，但是不工作：

import networkx as nx
import matplotlib.pyplot as plt


S=nx.DiGraph()#S-sample graph

S.add_nodes_from([0,1,2])
S.add_edge(0,2)
S.add_edge(1,2)

nx.draw(S)
#plt.savefig("S.png")
#plt.show()

R=nx.DiGraph()#R-reference graph

R.add_nodes_from([0,1,2])
R.add_edge(1,2)

nx.draw(R)
#plt.savefig("R.png")
#plt.show()

def difference(S, R):
  DIF=nx.create_empty_copy(R)
  DIF.name="Difference of (%s and %s)"%(S.name, R.name)
  if set(S)!=set(R):
    raise nx.NetworkXError("Node sets of graphs is not equal")

 # if S.is_multipgraph():
 #   edges=S.edges_iter(keys=True)
 # else:
  edges=S.edges_iter()
  for e in edges:
    if not R.has_edge(*e):
      DIF.add_edge(*e)
  return DIF

D=difference(S, R)
plt.show(D)

Answer 1

简单的写法如下（raise nx.Networkx...行

后面你的差分法部分

for edge in S.edges_iter():
        if not R.has_edge(edge[0],edge[1]):
            DIF.add_edge(edge[0],edge[1])
    return DIF;

这是我为您的示例制作的图表：

正如@joel 所提到的，我通过将 edge[0] 与 edge[1] 交换来测试它的无向图，它工作正常。

至于您的代码，我认为您唯一的问题是显示图表。

首先要在单独的图中显示每个图形，您必须在每次绘制后执行 plt.show()。

Second 在最后一行你写了 plt.show(D) 这是不正确的方法，你必须使用 draw 函数然后调用 plt.show()

最后，看看 drawing documentation, you have other draw functions where you can customize the drawn graphs e.g. nx.draw_networkx_nodes 节点的形状、颜色、大小...

Answer 2

您是否要使用参考 (R) 图中的边计算图 (DIF)，而不是输入图 (S) 中的边？还是要计算 R 和 S 之间不同边的图形？我包括了两个选项，一个被注释掉了。

import networkx as nx

S = nx.DiGraph()#S-sample graph
S.add_nodes_from([0, 1, 2])
S.add_edge(0, 2)
S.add_edge(1, 2)

R = nx.DiGraph()#R-reference graph
R.add_nodes_from([0, 1, 2])
R.add_edge(1, 2)


def difference(S, R):
    DIF = nx.create_empty_copy(R)
    DIF.name = "Difference of (%s and %s)" % (S.name, R.name)
    if set(S) != set(R):
        raise nx.NetworkXError("Node sets of graphs is not equal")

    r_edges = set(R.edges_iter())
    s_edges = set(S.edges_iter())

    # I'm not sure what the goal is: the difference, or the edges that are in R but not in S
    # In case it is the difference:
    diff_edges = r_edges.symmetric_difference(s_edges)

    # In case its the edges that are in R but not in S:
    # diff_edges = r_edges - s_edges

    DIF.add_edges_from(diff_edges)

    return DIF

print(difference(S, R).edges())

此版本打印 [(0, 2)]

正如@Joel 所注意到的，在无向图中，不保证（至少：我没有在源代码或文档中找到它）节点的顺序将是一致的。如果这是一个问题，您可以先将元组转换为冻结集，因此顺序无关紧要。您需要 frozensets，而不是集合或列表，因为它们是可散列的（这是对集合成员的要求）

set([frozenset(x) for x in S.edges()])

计算 networkx 中两个图 'edge wise' 之间的差异

Computing the Difference between two graphs 'edge wise' in networkx

python

networkx