How to create adjacency list from cartesian coordinates

Question

I was wondering if anyone can give me pointers on how to create adjacency lists from a 2d matrix?

i.e:

if i have the matrix:

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

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

I would like to create an adjacency list that connects the '1's together in the 4 directions (north,east,south, west):

 adjacencylist= {(0,0):(0,1),(1,0)
    
    (0,1):(0,0),(1,1)
    
    (1,0):(0,0),(1,1)
    
    (1,1):(1,0),(0,1)}

Answer 1

I think the following code do what you said.

matrix = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0]]

adj_matrix = {}

for r_index, row in enumerate(matrix):
    for c_index, val in enumerate(row):
        if val == 1:
            adj_matrix[(r_index, c_index)] = []
            if r_index > 0 and matrix[r_index - 1][c_index] == 1:
                adj_matrix[(r_index, c_index)].append((r_index - 1, c_index))
            if r_index < len(matrix) - 1 and matrix[r_index + 1][c_index] == 1:
                adj_matrix[(r_index, c_index)].append((r_index + 1, c_index))
            if c_index > 0 and matrix[r_index][c_index - 1] == 1:
                adj_matrix[(r_index, c_index)].append((r_index, c_index - 1))
            if (
                c_index < len(matrix[0]) - 1
                and matrix[r_index][c_index + 1] == 1
            ):
                adj_matrix[(r_index, c_index)].append((r_index, c_index + 1))

print(adj_matrix)