フィルターのクリア

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

9 ビュー (過去 30 日間)
Nadatimuj
Nadatimuj 2022 年 10 月 9 日
編集済み: Nadatimuj 2022 年 10 月 9 日
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))

採用された回答

John D'Errico
John D'Errico 2022 年 10 月 9 日
編集済み: John D'Errico 2022 年 10 月 9 日
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.
  1 件のコメント
Nadatimuj
Nadatimuj 2022 年 10 月 9 日
編集済み: Nadatimuj 2022 年 10 月 9 日
Perfect! Exactly what I was looking for...thank you very much!!

サインインしてコメントする。

その他の回答 (1 件)

MarKf
MarKf 2022 年 10 月 9 日
https://stackoverflow.com/a/3283732

カテゴリ

Help Center および File ExchangeStrategy & Logic についてさらに検索

タグ

製品


リリース

R2022b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by