在python中转置图形

Question

我有一张我想转置的图

graph = { 'A' : ['B','C'],
          'B' : ['C',],
          'C' : ['A',],
          'D' : ['B','A']
}

有没有办法做到：

reverseGraph = { 'A' : ['C','D'],
                 'B': ['A','D'],
                 'C': ['A','B'],
                 'D': []
}

我的尝试是这样的：

def transpose(graph):
    transposed = {}
    for key in graph.keys():
        transposed.update({key:[]})
    for key in transposed:
        for value in graph.values():
            for letter in value:
                if letter is key:
                   #put the letter's key (from graph) in the list of the
                   #the current key in transposed

我创建了一个新的图，其中只有原始图的键。我循环遍历每个键以添加转置的值。我循环遍历每个值列表以找到匹配的值。从这里，如果我找到一个匹配项，我将把匹配项放在当前键的值列表中。我的问题是如何找到匹配的密钥。可能吗

我提出这个问题的原因是，我认为应该有一种更好的方法在Python中实现这一点。我在网上找到了一些代码，如果每个节点只有一条边，那么这些代码就会转置到另一个节点。但这不适用于我的应用程序。像这样：

inv_map = {v: k for k, v in my_map.items()}

如果值是唯一的，也可以使用解决方案：

dict((v, k) for k, v in my_map.iteritems())

Answer 1

这是您的代码：

output = {}
for e,v in graph.items():
    output[e] = sorted(v,reverse=False)
print(output)

输出类

{'A': ['B', 'C'], 'B': ['C'], 'C': ['A'], 'D': ['A', 'B']}

Answer 2

一种简单易读的方法是使用collections.defaultdict和嵌套for循环：

from collections import defaultdict                                                           

graph = {'A': ['B', 'C'], 'B': ['C'], 'C': ['A'], 'D': ['B', 'A']}
                                
graph_inv = defaultdict(list)                                                                 

for source, targets in graph.items(): 
   for target in targets: 
       graph_inv[target].append(source)                                                                                            

输出：

>>> graph_inv                                                                                     
defaultdict(list, {'B': ['A', 'D'], 'C': ['A', 'B'], 'A': ['C', 'D']})

您可以看到结果字典中没有“D”键，但由于我们将其声明为^{}，因此如果您尝试获取它，您将获得预期的结果：

>>> graph_inv["D"]                                                                                
[]

然而，这可能不是最有效的方法