Create a neighbourhood graph from a given binary matrix using matlab

Question

I am trying to create a neighbourhood graph from a given binary matrix B. Neighbourhood graph (A) is defined as an adjacency matrix such that

(A(i,j) = A(j,i) = 1)

if the original matrix B(i) = B(j) = 1 and i and j are adjacent to each (left, right, up, down or diagonal). Here I used the linear subscript to access the original matrix B. For example, consider the below matrix

B = [ 0 1 0; 
      0 1 1; 
      0 0 0 ];

My A will be a 9 * 9 graph as given below

A = [ 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 0; 
      0 0 0 1 0 0 0 1 0; 
      0 0 0 0 0 0 0 0 0; 
      0 0 0 0 0 0 0 0 0; 
      0 0 0 1 1 0 0 0 0; 
      0 0 0 0 0 0 0 0 0 ];

Since in the original B matrix, B(4), B(5) and B(8) are adjacent with corresponding entries 1, the adjacency matrix A has 1 at A(4,5), A(5,4), A(4,8), A(8,4), A(5,8) and A(8,5).

How can I create such an adjacency matrix A given the matrix B in an efficient way?

Answer 1

This doesn't require any toolbox, and works for square or rectangular matrices. It uses array operations with complex numbers.

Consider a binary matrix B of size M×N.

1. Create an M×N matrix, t, that contains the complex coordinates of each nonzero entry of B. That is, entry t(r,c) contains r+1j*c if B(r,c) is nonzero, and NaN otherwise.
2. Compute an M*N×M*N matrix, d, containing the absolute difference for each pair of entries of B. Pairs of entries of B that are nonzero and adjacent will produce 1 or sqrt(2) in matrix d.
3. Build the result matrix, A, such that it contains 1 iff the corresponding entry in d equals 1 or sqrt(2). Equivalently, and more robust to numerical errors, iff the corresponding entry in d is between 0 and 1.5.

Code:

B = [0 1 0; 0 1 1; 0 0 0]; % input
t = bsxfun(@times, B, (1:size(B,1)).') + bsxfun(@times, B, 1j*(1:size(B,2)));
t(t==0) = NaN; % step 1
d = abs(bsxfun(@minus, t(:), t(:).')); % step 2
A = d>0 & d<1.5; % step 3

To get B back from A:

B2 = zeros(sqrt(size(A,1)));
B2(any(A,1)) = 1;