How do I generate an adjacency matrix of a graph from a dictionary in python?

Patterson picture Patterson · May 20, 2016 · Viewed 11.4k times · Source

I have the following dictionary:

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

It implements a graph, each list contains the neighbors of the graph vertices (dictionary keys are the vertices itself). I'm in trouble, I can not think of a way to get a graph adjacency matrix from their lists of neighbors, might be easy but I am new to python, I hope someone can help me! I am using Python 3.5

I need to generate the following matrix:

enter image description here

Answer

karakfa picture karakfa · May 20, 2016

without pandas

keys=sorted(g.keys())
size=len(keys)

M = [ [0]*size for i in range(size) ]

for a,b in [(keys.index(a), keys.index(b)) for a, row in g.items() for b in row]:
     M[a][b] = 2 if (a==b) else 1

M

[2, 1, 1, 0, 0],
[1, 0, 1, 0, 1],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 1, 0, 1, 0]]

Explanation

for a, row in g.items() iterates over the key:value entries in dictionary, and for b in row iterates over the values. If we used (a,b), this would have given us all the pairs.

(keys.index(a), keys.index(b)) But we need the index to assign to the corresponding matrix entry,

keys=sorted(g.keys()) that's why we extracted and sorted the keys.

for a,b in... getting the index entries and assigning value 1 or 2 based on diagonal element or not.

M = [ [0]*size for ... matrix cannot be used before initialization.