python - Converting a graph into dictionary form

Question

I am currently writing a program to model Dijkstra's algorithm, however I am having some trouble the graph in its current form below:

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 2), ({'d', 'g'}, 7), ({'d', 'h'}, 1) ,
      ({'e', 'i'}, 2), ({'e', 'j'}, 7), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

I want to get the graph in the form such as the one below

{ 'a': {'b': 4, 'c': 6, 'd': 8},
    'b': {'a': 4, 'e': 1, 'f': 9}, etc

Would this be possible?

标签： pythonpython-3.xdictionarydijkstra

Answer 1

You can use collections.defaultdict for this.

Code:

from collections import defaultdict

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 2), ({'d', 'g'}, 7), ({'d', 'h'}, 1) ,
      ({'e', 'i'}, 2), ({'e', 'j'}, 7), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

result = defaultdict(dict)
for edge in G[1]:
    v1, v2 = edge[0]
    result[v1][v2] = edge[1]
    result[v2][v1] = edge[1]

print(result)

Output:

defaultdict(<class 'dict'>,
            {'a': {'b': 4, 'c': 6, 'd': 8},
             'b': {'a': 4, 'e': 1, 'f': 9},
             'c': {'a': 6, 'f': 2},
             'd': {'a': 8, 'g': 7, 'h': 1},
             'e': {'b': 1, 'i': 2, 'j': 7},
             'f': {'b': 9, 'c': 2},
             'g': {'d': 7, 'h': 2},
             'h': {'d': 1, 'g': 2},
             'i': {'e': 2, 'j': 4},
             'j': {'e': 7, 'i': 4}})