在MATLAB中构造邻接matrix

考虑一组在N-M尺寸的网格上排列的点。 我正在试图build立邻接matrix，使得相邻的点相连。

例如，在一个带有graphics的3×3网格中：

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

我们应该有相应的邻接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 | +---+------------------------------------------------------+ 

作为奖励，该解决scheme应该适用于4个和8个连接的相邻点，即：

  oooo o X o vs. o X o oooo 

这是我迄今为止的代码：

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

如何改进以避免所有的循环？

Answer 1

如果你注意到，你创build的邻接matrix有一个独特的模式。 具体来说，它们是对称的， 带状的 。 您可以利用这一事实轻松地使用DIAG函数创buildmatrix（如果要制作稀疏matrix，则使用SPDIAGS函数）。 下面是如何使用上面的示例matrix为每个案例创build邻接matrix：

4连接的邻居

 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)+... %# Add the diagonals to a zero matrix diag(diagVec2,c); adj = adj+adj.'; %'# Add the matrix to a transposed %# copy of itself to make it %# symmetric 

你会得到以下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个连接的邻居

 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 

你会得到以下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 

Answer 2

为了好玩，这里有一个解决scheme，通过计算网格上所有点对之间的距离来构造邻接matrix（显然不是最有效的方法）

 N = 3; M = 3; %# grid size CONNECTED = 8; %# 4-/8- connected points %# which distance function if CONNECTED == 4, distFunc = 'cityblock'; elseif CONNECTED == 8, distFunc = 'chebychev'; end %# compute adjacency matrix [XY] = meshgrid(1:N,1:M); X = X(:); Y = Y(:); adj = squareform( pdist([XY], distFunc) == 1 ); 

这里有一些代码来显示邻接matrix和连接点的graphics：

 %# plot adjacency matrix subplot(121), spy(adj) %# plot connected points on grid [xx yy] = gplot(adj, [XY]); subplot(122), plot(xx, yy, 'ks-', 'MarkerFaceColor','r') axis([0 N+1 0 M+1]) %# add labels [XY] = meshgrid(1:N,1:M); X = reshape(X',[],1) + 0.1; Y = reshape(Y',[],1) + 0.1; text(X, Y(end:-1:1), cellstr(num2str((1:N*M)')) ) 

Answer 3

在search相同的问题时，我只是发现了这个问题。 但是，由于需要使用稀疏matrixtypes的问题大小，所提供的解决scheme都不适用于我。 这是我的解决scheme，适用于大型实例：

 function W = getAdjacencyMatrix(I) [m, n] = size(I); I_size = m*n; % 1-off diagonal elements V = repmat([ones(m-1,1); 0],n, 1); V = V(1:end-1); % remove last zero % n-off diagonal elements U = ones(m*(n-1), 1); % get the upper triangular part of the matrix W = sparse(1:(I_size-1), 2:I_size, V, I_size, I_size)... + sparse(1:(I_size-m),(m+1):I_size, U, I_size, I_size); % finally make W symmetric W = W + W'; 

Answer 4

你目前的代码似乎并不那么糟糕。 无论如何，你需要迭代所有的邻居对。 如果你真的需要优化代码，我会build议：

• 在节点索引i上循环，其中1 <= i <= (N*M)
• 为了提高效率，不要使用sub2ind（），节点i的邻居顺时针顺序为simpy [iM, i+1, i+M, i-1]

请注意，要获得所有的邻居对节点：

• 你只需要为节点i % M != 0计算“右”邻居（即水平边缘）（因为Matlab不是基于0而是基于1）
• 你只需要为节点i > M计算“高于”的邻居（即垂直边缘）
• 对angular边缘也有类似的规则

这将导致一个单一的循环（但是相同数量的N * M迭代），不会调用sub2ind（），并且在循环中只有两个if语句。

Answer 5

刚刚遇到这个问题。 我有一个很好的工作m函数（链接： sparse_adj_matrix.m ），这是相当一般的。

它可以处理4个连接的网格（根据L1规范的半径1），8个连接的网格（根据L_infty规范的半径1）。
它也可以支持3D（和任意更高的montage网格）。
该函数还可以连接比radius = 1更远的节点。

这是函数的签名：

 % Construct sparse adjacency matrix (provides ii and jj indices into the % matrix) % % Usage: % [ii jj] = sparse_adj_matrix(sz, r, p) % % inputs: % sz - grid size (determine the number of variables n=prod(sz), and the % geometry/dimensionality) % r - the radius around each point for which edges are formed % p - in what p-norm to measure the r-ball, can be 1,2 or 'inf' % % outputs % ii, jj - linear indices into adjacency matrix (for each pair (m,n) % there is also the pair (n,m)) % % How to construct the adjacency matrix? % >> A = sparse(ii, jj, ones(1,numel(ii)), prod(sz), prod(sz)); % % % Example: % >> [ii jj] = sparse_adj_matrix([10 20], 1, inf); % construct indices for 200x200 adjacency matrix for 8-connect graph over a % grid of 10x20 nodes. % To visualize the graph: % >> [rc]=ndgrid(1:10,1:20); % >> A = sparse(ii, jj, 1, 200, 200);; % >> gplot(A, [r(:) c(:)]); 

Answer 6

对于图中的每个节点，向右向下添加一个连接。 检查你没有超越你的网格。 考虑下面构build邻接matrix的函数。

 function adj = AdjMatrixLattice4( N, M ) % Size of adjacency matrix MN = M*N; adj = zeros(MN,MN); % number nodes as such % [1]---[2]-- .. --[M] % | | | % [M+1]-[M+2]- .. -[2*M] % : : : % [] [] .. [M*N] for i=1:N for j=1:N A = M*(i-1)+j; %Node # for (i,j) node if(j<N) B = M*(i-1)+j+1; %Node # for node to the right adj(A,B) = 1; adj(B,A) = 1; end if(i<M) B = M*i+j; %Node # for node below adj(A,B) = 1; adj(B,A) = 1; end end end end 

上面的AdjMatrixLattice4(3,3)=

  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