Simple. Given N and M, the code below will work. Note that it builds the matrix in sparse form, since a large such matrix will indeed be sparse in nature. There will never be more than 4 non-zero elements per row, and some nodes talk to only 2 or 3 neighbors. If you don't want it to be sparse, then just use full at the end.
A = latticeAdjacencyMatrix(4,3);
full(A)
Agraph = graph(A);
plot(Agraph)
The code is fast too.
tic,
A = latticeAdjacencyMatrix(100,200);
toc
numel(A)
nnz(A)
And the matrix will really be a sparse matrix, with on average just a hair under 4 non-zero elements per row, so you do want to use sparse here, certainly so if N and M are at all large.
function A = latticeAdjacencyMatrix(N,M)
% N rows, M columns, denoting the size of the rectangular lattice
% A - N*M by N*M square adjacency matrix
% Connect nodes (i,j) to (i+1,j)
[i,j] = ndgrid(1:N-1,1:M);
ind1 = sub2ind([N,M],i,j);
ind2 = sub2ind([N,M],i+1,j);
% Connect nodes (i,j) to (i,j+1)
[i,j] = ndgrid(1:N,1:M-1);
ind3 = sub2ind([N,M],i,j);
ind4 = sub2ind([N,M],i,j+1);
% build the global adjacency matrix
totalnodes = N*(M-1) + (N-1)*M;
A = sparse([ind1(:);ind3(:)],[ind2(:);ind4(:)],ones(totalnodes,1),N*M,N*M);
% symmetrize, since the above computations only followed the edges in one direction.
% that is to say, if a talks to b, then b also talks to a.
A = A + A';
end
As I said, easy enough. Mainly just a couple of calls to ndgrid, then calls to sub2ind, then a final call to sparse. Accumarray would have also worked, but it would produce a full matrix as a result, and I think sparse makes more sense. You don't really need the calls to sub2ind, since it is an easy tool to replace with a simple formula, but why bother?
I suppose if N and M were seriously large, you could make A into a sparse LOGICAL matrix. This would use even less storage.
