Search code examples
pythonreversegraph-theorydirected-graphdefaultdict

Reverse a defaultdict(dict)

If I have a defaultdict(dict):

defaultdict("dict"), {'NYC': {'LA': '3000'}, 'SanFrancisco': {'Houston': '1000'}, 'LA': {'Detroit': '200', 'Ames': '300', 'SanFrancisco': True}, 'Austin': {'Houston': '500'}})

How can I "reverse the arcs"? Or step 3 from this website? http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/

Example output: 

# edited for more clarity
defaultdict(<class 'dict'>,
            {'Ames': {'LA': '300'},
             'Detroit': {'LA': '200'},
             'Houston': {'Austin': '500', 'SanFrancisco': '1000'},
             'LA': {'NYC': '3000'},
             'SanFrancisco': {'LA': True}})

For transposing a graph: https://en.wikipedia.org/wiki/Transpose_graph

P.S. I would like to keep my reversed graph as a defaultdict(dict). Thank you!

Solution

  • The nested defaultdict is a two-dimensional data structure (for every source city there are possible multiple destinations). Accordingly, it makes sense to use nested for-loops to traverse the data and reinsert into a new defaultdict with the dimensions reversed (swapping the source and destination):

    >>> from collections import defaultdict

>>> start = defaultdict(dict, {'NYC': {'LA': '3000'}, 'SanFrancisco': {'Houston': '1000'}, 'LA': {'Detroit': '200', 'Ames': '300', 'SanFrancisco': True}, 'Austin': {'Houston': '500'}})

>>> goal = defaultdict(dict)
>>> for source, dests in start.items():
        for dest, distance in dests.items():
            goal[dest][source] = distance

>>> goal
defaultdict(<class 'dict'>, {'LA': {'NYC': '3000'}, 'Houston': {'SanFrancisco': '1000', 'Austin': '500'}, 'Detroit': {'LA': '200'}, 'Ames': {'LA': '300'}, 'SanFrancisco': {'LA': True}})