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

Question

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:

Solution 1

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.

Solution 2

Here is a solution using pandas.

import pandas as pd

g = {
'A': [ 'A', 'B', 'C'], 
'B': [ 'A', 'C', 'E'], 
'C': [ 'A', 'B ',' D '], # I added a comma here
'D': [' C ',' E '],
'E': [' B ',' D ']
}

# clean up the example
g = {k: [v.strip() for v in vs] for k, vs in g.items()}

edges = [(a, b) for a, bs in g.items() for b in bs]

df = pd.DataFrame(edges)

adj_matrix = pd.crosstab(df[0], df[1])

# 1  A  B  C  D  E
# 0               
# A  1  1  1  0  0
# B  1  0  1  0  1
# C  1  1  0  1  0
# D  0  0  1  0  1
# E  0  1  0  1  0

I am not sure why you have 2 in your example matrix in (A, A) position.

Comments

[Vedang Mehta]

I believe that nodes pointed to itself have a weight of 2 in this weighted graph. This is just an assumption.

[Patterson]

The 2 is because the vertex 'A' have an edge to itself

[Patterson]

I can't import pandas. ImportError: No module named 'pandas'

[hilberts_drinking_problem]

You need to install pandas, or use a different method. Please refer here pandas.pydata.org Regarding the matrix: we can either count the out degree, or the in degree, or both. In the first two cases, (A,A) points to one, in the third case the rest of the matrix should be doubled. Let me know if I am missing something.

[Patterson]

Perfect, you helped me a lot! But could you explain me this code? I did not understand well the line where you do the loop that fills the array, I know you used "python comprehensions," but this is complicated for me, I am new to python, thanks a lot!

[Patterson]

Thank you for your explanation! Now it looks too easy!

[YNR]

@Yakym Pirozhenko Thank you for your solution. I have a huge dataset that would need 4M columns and 1M rows for adj_matrix . So I receive MemoryError on the server. Do you have any solution?

[hilberts_drinking_problem]

@YNr you could try scipy sparse matrix or use a graph from networkx package with weights representing edge counts.

[Sean]

Please add some explanations.