Construct adjacency matrix in MATLAB

Question

Consider a set of points arranged on a grid of size N-by-M. I am trying to build the adjacency matrix such that neighboring points are connected.

For example, in a 3x3 grid with a graph:

1-2-3
| | |
4-5-6
| | |
7-8-9

We should have the corresponding adjacency matrix:

+---+------------------------------------------------------+
|   |   1     2     3     4     5     6     7     8     9  |
+---+------------------------------------------------------+
| 1 |   0     1     0     1     0     0     0     0     0  |
| 2 |   1     0     1     0     1     0     0     0     0  |
| 3 |   0     1     0     0     0     1     0     0     0  |
| 4 |   1     0     0     0     1     0     1     0     0  |
| 5 |   0     1     0     1     0     1     0     1     0  |
| 6 |   0     0     1     0     1     0     0     0     1  |
| 7 |   0     0     0     1     0     0     0     1     0  |
| 8 |   0     0     0     0     1     0     1     0     1  |
| 9 |   0     0     0     0     0     1     0     1     0  |
+---+------------------------------------------------------+

As a bonus, the solution should work for both 4- and 8-connected neighboring points, that is:

   o             o  o  o
o  X  o   vs.    o  X  o
   o             o  o  o

This the code that I have so far:

N = 3; M = 3;
adj = zeros(N*M);

for i=1:N
    for j=1:M
        k = sub2ind([N M],i,j);
        if i>1
            ii=i-1; jj=j;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
        if i<N
            ii=i+1; jj=j;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
        if j>1
            ii=i; jj=j-1;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
        if j<M
            ii=i; jj=j+1;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
    end
end

How can this improved to avoid all the looping?

Answer 1

If you notice, there is a distinct pattern to the adjacency matrices you are creating. Specifically, they are symmetric and banded. You can take advantage of this fact to easily create your matrices using the diag function (or the spdiags function if you want to make a sparse matrix). Here is how you can create the adjacency matrix for each case, using your sample matrix above as an example:

4-connected neighbors:

mat = [1 2 3; 4 5 6; 7 8 9];                 % Sample matrix
[r, c] = size(mat);                          % Get the matrix size
diagVec1 = repmat([ones(c-1, 1); 0], r, 1);  % Make the first diagonal vector
                                             %   (for horizontal connections)
diagVec1 = diagVec1(1:end-1);                % Remove the last value
diagVec2 = ones(c*(r-1), 1);                 % Make the second diagonal vector
                                             %   (for vertical connections)
adj = diag(diagVec1, 1)+diag(diagVec2, c);   % Add the diagonals to a zero matrix
adj = adj+adj.';                             % Add the matrix to a transposed copy of
                                             %   itself to make it symmetric

And you'll get the following matrix:

adj =

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

8-connected neighbors:

mat = [1 2 3; 4 5 6; 7 8 9];                 % Sample matrix
[r, c] = size(mat);                          % Get the matrix size
diagVec1 = repmat([ones(c-1, 1); 0], r, 1);  % Make the first diagonal vector
                                             %   (for horizontal connections)
diagVec1 = diagVec1(1:end-1);                % Remove the last value
diagVec2 = [0; diagVec1(1:(c*(r-1)))];       % Make the second diagonal vector
                                             %   (for anti-diagonal connections)
diagVec3 = ones(c*(r-1), 1);                 % Make the third diagonal vector
                                             %   (for vertical connections)
diagVec4 = diagVec2(2:end-1);                % Make the fourth diagonal vector
                                             %   (for diagonal connections)
adj = diag(diagVec1, 1)+...                  % Add the diagonals to a zero matrix
      diag(diagVec2, c-1)+...
      diag(diagVec3, c)+...
      diag(diagVec4, c+1);
adj = adj+adj.';                             % Add the matrix to a transposed copy of
                                             %   itself to make it symmetric

And you'll get the following matrix:

adj =

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