在Python中根据节点字典创建边字典

Question

我有一个字典，里面的格式是这样的：{字符串: 列表, 字符串: 列表, ...}。我需要在两个键之间建立连接，这两个键的值列表中有共同的元素。简单来说，我想做一个表格，里面有三列：共同元素, 键1, 键2。

这是我现在的代码：

edges = []

for v in nodesDict.list():
    for x in v:
      shared_element = x
      key1 = k
      edges.append(shared_element + ',' + key1)

这样做会生成每个值元素和它的键配对的元组，对吧？我现在不太确定怎么把那些有共同值的配对匹配起来，然后做出这个表格。

谢谢！另外，如果有人有更有效的方法来做这个，而不是一个一个去对比，那就太好了。

Answer 1

这是我不需要额外库的解决方案：

dict
{'A': [1, 2, 3, 4], 'B': [3, 4], 'C': [1, 4, 5]}

edges=[]

for index,item in enumerate(dict):
    for i in range(index+1,len(dict)):
        for x in dict[item]:
            for y in dict[dict.keys()[i]]:
                if x==y : edges.append((x,item,dict.keys()[i]))
print edges

[(1, 'A', 'C'), (4, 'A', 'C'), (3, 'A', 'B'), (4, 'A', 'B'), (4, 'C', 'B')]

Answer 2

首先，来看一个例子：

nodesDict = {'A': [1, 2, 3, 4], 'B': [3, 4], 'C': [1, 4, 5]}

从这个例子中，我们可以推测出预期的结果：

# [(1, 'A', 'C'), (3, 'A', 'B'), (4, 'A', 'B'), (4, 'A', 'C'), (4, 'B', 'C')]

为了得到这个结果，最简单的方法是先把字典反转过来：

from collections import defaultdict

revDict = defaultdict(list)

for k, v in nodesDict.items():
    for item in v:
        revDict[item].append(k)

现在，你已经把字典反转过来了，可以简单地遍历它，组合这些元素，结果就出来了：

from itertools import combinations
edges = []
for k, v in revDict.items():
    if len(v) > 1:
        for values in combinations(v, 2):
            edges.append((k,) + values)

print edges

# [(1, 'A', 'C'), (3, 'A', 'B'), (4, 'A', 'C'), (4, 'A', 'B'), (4, 'C', 'B')]

Answer 3

编辑：用集合（set）代替元组（tuple）更好，因为边是一个无序的独特元素集合，也就是集合。

我觉得，根据边/节点字典的最终用途，把边的 dict 存储节点用集合 set 是个不错的主意：

edge: (node1, node2)

所以你已经有了一个 node:[edges] 的字典。我会这样创建新的字典：

from collections import defaultdict

edgeDict = defaultdict(set) 
for node in nodesDict.keys():
    for edge in nodesDict[node]:
        edgeDict[edge].add(node) 

使用 defaultdict，你可以保持和普通 dict 一样的功能，只不过当你尝试访问一个不存在的项时，它会自动把这个项添加到 dict 中。

你还可以利用这个新的字典，用一行代码创建一个元组列表，格式是 (edge, node1, node2)：

[tuple(edge) + tuple(nodes) for edge, nodes in edgeDict.items()]

---

同时，还有一些第三方模块可以帮助你处理图形相关的事情。NetworkX 是一个很受欢迎的模块。