Transpose a graph in python

Question

I have graph that I want to transpose.

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

Is there a way to make:

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

My attempt was like this:

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

I create a new graph with only the keys of the original graph. I loop through each key to add the transposed values. I loop through each list of values to find the matching value. From here if I find a match I will put the match’s key in the list of values for the current key. My issue is how to find match’s key. Is that possible?

The reason for my question is I think it's likely there should be a much better way of doing this in Python. I found some code online that would transpose if each node only had an edge to one other node. But that doesn’t work for my application. Like this:

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

Also a solution if the values are unique:

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

Answer 1

An easy and readable way to do it is to use collections.defaultdict and a nested for loop:

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)                                                                                            

output:

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

You can see that there is no "D" key in the resulting dictionary, but since we declared it as a defaultdict, then if you try to get it you'll have the intended result:

>>> graph_inv["D"]                                                                                
[]

However, it might not be the most efficient way.