Matrix of labels to adjacency matrix

Question

Just wondering if there is an off-the-shelf function to perform the following operation; given a matrix X, holding labels (that can be assumed to be integer numbers 0-to-N) in each entry e.g.:

X = [[0 1 1 2 2 3 3 3],
     [0 1 1 2 2 3 3 4],
     [0 1 5 5 5 5 3 4]]

I want its adjacency matrix G i.e. G[i,j] = 1 if i,j are adjacent in X and 0 otherwise.

For example G[1,2] = 1, because 1,2 are adjacent in (X[0,2],X[0,3]), (X[1,2],X[1,3]) etc..

The naive solution is to loop through all entries and check its neighbors, but I'd rather avoid loops for performance reason.

Answer 1

You can use fancy indexing to assign the values of G directly from your X array:

import numpy as np

X = np.array([[0,1,1,2,2,3,3,3],
              [0,1,1,2,2,3,3,4],
              [0,1,5,5,5,5,3,4]])
G = np.zeros([X.max() + 1]*2)

# left-right pairs
G[X[:, :-1], X[:, 1:]] = 1
# right-left pairs
G[X[:, 1:], X[:, :-1]] = 1
# top-bottom pairs
G[X[:-1, :], X[1:, :]] = 1
# bottom-top pairs
G[X[1:, :], X[:-1, :]] = 1

print(G)
#array([[ 1.,  1.,  0.,  0.,  0.,  0.],
#       [ 1.,  1.,  1.,  0.,  0.,  1.],
#       [ 0.,  1.,  1.,  1.,  0.,  1.],
#       [ 0.,  0.,  1.,  1.,  1.,  1.],
#       [ 0.,  0.,  0.,  1.,  1.,  0.],
#       [ 0.,  1.,  1.,  1.,  0.,  1.]])