How to convert an adjacency list into an adjacency matrix in Python

Question

I have an adjacency list like this:

Where the first row is saying 0 is adjacent to 1, 4, and 5; the second row is saying 1 is adjacent to 0, 2, and 6; the third row is saying 2 is adjacent to 1, 3, and 7, ...

How can I convert it into an adjacency matrix like so?

0 1 0 0 1 1 0 0 0 0
1 0 1 0 0 0 1 0 0 0
0 1 0 1 0 0 0 1 0 0
0 0 1 0 1 0 0 0 1 0
1 0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 1 1 0
0 1 0 0 0 0 0 0 1 1
0 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 1 0 0 0
0 0 0 0 1 0 1 1 0 0

Are you using numpy? `a = np.zeros((10,10))` / `a[0,[1,4,5]] = 1` will do it. — Tim Roberts, Mar 09 '21 at 20:20
Hey @tim, thanks for the quick reply, I tried your method and its giving me this matrix instead: `[[0. 1. 0. 0. 1. 1. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]][[0. 1. 0. 0. 1. 1. 0. 0. 0. 0.]` — Stina V, Mar 09 '21 at 20:28
* that matrix repeats a few times, am I typing it wrong? I assumed your "/" meant a line skip — Stina V, Mar 09 '21 at 20:34
I was showing you an example for the first line, assuming you could extend that into a loop that processes it all. I'll post an answer showing what I mean. — Tim Roberts, Mar 09 '21 at 21:12

lotrus28 · Answer 1 · 2021-03-09T20:42:29.257

0

import numpy as np
adj_dict = {}
path_to_list = '../adj_list.txt'
# Replace with zero if vertices are connected to themselves
empty_digonal = 1
with open(path_to_list) as f:
    adj_dict = {int(line.split()[0]):[int(x) for x in line.split()[empty_diagonal:]] for line in f.read().strip('\n').splitlines()}
adj_mx = np.zeros([len(adj_dict),len(adj_dict)])
for i in adj_dict:
        adj_mx[i,adj_dict[i]] = 1
assert sum(sum(adj_mx - adj_mx.T)) == 0, 'The matrix is not symmetric'

Probably not the optimal solution, but it works

edited Mar 09 '21 at 20:42

answered Mar 09 '21 at 20:36

lotrus28

848
2
10
19

Thanks @lotrus28, I am getting a traceback error: File "/tmp/source.py", line 10, in adj_mx[i,j] = 1 IndexError: index 1 is out of bounds for axis 1 with size 1 My code: `for line in sys.stdin: adj_dict = {} adj_dict = {int(line.split()[0]):[int(x) for x in line.split()[0:]] for line in line.strip('\n').splitlines()} adj_mx = np.zeros([len(adj_dict),len(adj_dict)]) for i in adj_dict: for j in adj_dict[i]: adj_mx[i,j] = 1 assert sum(sum(adj_mx - adj_mx.T)) == 0, print(adj_dict, end="")` – Stina V Mar 09 '21 at 20:45
@SilentP It means that you are trying to use `j==1`, when `j`'s maximum acceptable value is `0`. You have a "flat" matrix. Are you sure that the input is not one line? – lotrus28 Mar 09 '21 at 20:53

forgetso · Accepted Answer · 2021-03-10T09:08:11.287

How about creating lists of positioned 0s and 1s, of same length, inside the dataframe and then pulling them out as series.

# the lists will all be this length
maxlen = df.max().max()

df = pd.DataFrame([
    [0, 1, 4, 5],
    [1, 0, 2, 6],
    [2, 1, 3, 7],
    [3, 2, 4, 8],
    [4, 0, 3, 9],
    [5, 0, 7, 8],
    [6, 1, 8, 9],
    [7, 2, 5, 9],
    [8, 3, 5, 6],
    [9, 4, 6, 7]])

# the function used to create the lists
def createlist(x):
    arr=(maxlen+1)*[0]
    arr[x]=1
    return arr

# create the list for each cell, then concatenate the lists per row vertically, sum them, giving each final row
df2 = df.applymap(createlist).apply(lambda x: pd.concat([pd.Series(x[i]) for i in range(len(df.columns))], axis=1).sum(axis=1),axis=1)


df2

    0   1   2   3   4   5   6   7   8   9
0   1   1   0   0   1   1   0   0   0   0
1   1   1   1   0   0   0   1   0   0   0
2   0   1   1   1   0   0   0   1   0   0
3   0   0   1   1   1   0   0   0   1   0
4   1   0   0   1   1   0   0   0   0   1
5   1   0   0   0   0   1   0   1   1   0
6   0   1   0   0   0   0   1   0   1   1
7   0   0   1   0   0   1   0   1   0   1
8   0   0   0   1   0   1   1   0   1   0
9   0   0   0   0   1   0   1   1   0   1

To set the diagonal to zeroes do something like:

df3 = df2.values

np.fill_diagonal(df3, 0)

Thanks @forgetso, didn't think about converting it into a pandas dataframe its a lot easier to manipulate this way. Quick question, how would you pass a 0 instead of a 1 when referencing themselves? e.g. 0 should show 0 in the first cell (not counting index) instead of a 1, 1 should show 0 in the 2nd column 2nd row instead of a 1, etc. Also, any way to remove the columns and row index? — Stina V, Mar 09 '21 at 22:45
You could use `df3 = df2.values` and then fill the diagonal `np.fill_diagonal(df3, 0)`. You could apply this to @Tim Roberts answer as well. It looks a lot simpler. — forgetso, Mar 10 '21 at 08:57

score 0 · Answer 3 · answered Mar 09 '21 at 21:14

import numpy as np

rows = (
    [0, 1, 4, 5],
    [1, 0, 2, 6],
    [2, 1, 3, 7],
    [3, 2, 4, 8],
    [4, 0, 3, 9],
    [5, 0, 7, 8],
    [6, 1, 8, 9],
    [7, 2, 5, 9],
    [8, 3, 5, 6],
    [9, 4, 6, 7]
)

matrix = np.zeros((10,10))
for row in rows:
    matrix[row[0],row[1:]] = 1
print(matrix)

How to convert an adjacency list into an adjacency matrix in Python

3 Answers3