反转 defaultdict(dict)

Question

如果我有一个 defaultdict(dict):

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

我怎样才能"reverse the arcs"？还是本网站的第 3 步？ http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/

示例输出：

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

转置图形：https://en.wikipedia.org/wiki/Transpose_graph

P.S。我想将我的反转图保留为 defaultdict(dict)。谢谢！

Answer 1

嵌套的 defaultdict 是一个二维数据结构（对于每个来源城市，可能有多个目的地）。因此，使用嵌套的 for 循环来遍历数据并重新插入到一个新的 defaultdict 中是有意义的，并且维度相反（交换源和目标）：

>>> 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}})

反转 defaultdict(dict)

Reverse a defaultdict(dict)

python

reverse

graph-theory

directed-graph

defaultdict