在Python中创建给定节点字典的边字典

Question

我有一个节点字典，它的格式是：{string: list, string: list, ...}。我需要在两个键之间创建边，这两个键在它们的值列表中共享一个元素。基本上我想创建一个包含三列的表：shared element, key 1, key 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]}

由此我们可以推断出预期的结果：

^{pr2}$

要做到这一点，最简单的方法是颠倒事实：

from collections import defaultdict

revDict = defaultdict(list)

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

现在，你把dict颠倒过来，你可以简单地在上面迭代，组合元素，瞧：

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

编辑：使用集合而不是元组更好，因为边是唯一元素的无序集合，也就是集合。在

我认为根据边缘/节点dicts的最终目的，让边缘dict将节点存储为set，这可能是明智的：

edge: (node1, node2)

所以你有一个已经形成的dict的node:[edges]。我会这样创建新的dict：

^{pr2}$

使用defaultdict，您可以维护与使用dict相同的功能，只有当您对不存在的项调用__getitem__()方法时，它才会将该项添加到dict。在

您还可以利用这个新的dict创建一个(edge, node1, node2)形式的元组列表，其中包含一行代码列表comp：

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

---

同时，还有一些第三方模块可以清理您必须处理的任何图形业务。NetworkX是一个流行的模块。在