Any function to get adjacency matrix of 2D M by N lattice?

Is there any function in matlab to generate adjacency matrix, A of 2D M by N lattice?

For example, for M = 4, N = 3,

A = [0	1	0	0	1	0	0	0	0	0	0	0
1	0	1	0	0	1	0	0	0	0	0	0
0	1	0	1	0	0	1	0	0	0	0	0
0	0	1	0	0	0	0	1	0	0	0	0
1	0	0	0	0	1	0	0	1	0	0	0
0	1	0	0	1	0	1	0	0	1	0	0
0	0	1	0	0	1	0	1	0	0	1	0
0	0	0	1	0	0	1	0	0	0	0	1
0	0	0	0	1	0	0	0	0	1	0	0
0	0	0	0	0	1	0	0	1	0	1	0
0	0	0	0	0	0	1	0	0	1	0	1
0	0	0	0	0	0	0	1	0	0	1	0];

plot(graph(A))

Answer 1

[John D'Errico]

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)

ans = 12×12

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

Agraph = graph(A);
plot(Agraph)

The code is fast too.

tic,
A = latticeAdjacencyMatrix(100,200);
toc

Elapsed time is 0.009200 seconds.

numel(A)

ans = 400000000

nnz(A)

ans = 79400

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.

[Nadatimuj]

Perfect! Exactly what I was looking for...thank you very much!!

Answer 2

[MarKf]

https://stackoverflow.com/a/3283732

[Nadatimuj]

Thanks!