找出两个图之间的差异

Question

我正在使用图形数据结构解决我的一个子问题。我已经使用以顶点作为键和边作为节点列表的字典来实现它。示例：

graph1 = {'1': ['3'],'2': [],'3': ['1', '7'],'7':['3']}

我想比较两个图表，即上面的图表：

graph2 = {'1': ['3'],'2': ['3'],'3': ['1', '2'],'7':[]}

以上两图在边上有所不同

我想要这两个图的差异信息，例如：

graph1-graph2 = {'2':[],'3':['1','7'],'7':['3']}
graph2-graph1 = {'2':['3'],'3':['1','2'],'7':[]}

简而言之，我正在寻找 graph1 和 graph2 之间的对称差异。

我尝试按照 link 中的建议获取设置差异。但是由于值是列表，所以我收到错误 TypeError: unhashable type: 'list'。我明白这是因为集合是不可变的而列表是可变的数据结构。类型转换产生错误。

我也尝试使用 link 中给出的数据帧差异，我遇到了与上述相同的类型错误。

有没有简单的方法得到解决方案？任何帮助表示赞赏。提前致谢:)

PS：我想让我的图实现简单。因此，我没有使用任何高级库，如 networkx。

编辑 1：请注意，我想要的结果有点类似于集合的对称差异的结果，而不是完全对称的差异。

使用结果，我想了解两个图中哪些节点不同。结果应包含两个图中边列表不同的节点。喜欢：

'2' : [] (graph1)
'2' : ['3'] (graph2)

and

'3' : ['1','7'] (graph1)
'3' : ['1','2'] (graph2)

Answer 1

您可以使用以下内容：

注意。这假设词典 具有相同的键 （如果没有，请明确显示所需的输出

graph1_2 = {}
graph2_1 = {}

for key in graph1:
    s1 = set(graph1[key])
    s2 = set(graph2[key])
    if s1 == s2:
        continue
    else:
        graph1_2[key] = graph1[key]
        graph2_1[key] = graph2[key]

输出：

>>> graph1_2
{'2': [], '3': ['1', '7'], '7': ['3']}

>>> graph2_1
{'2': ['3'], '3': ['1', '2'], '7': []}

找出两个图之间的差异

Finding difference between two graphs

python

dictionary

set-difference