how to determine the neighbours of each node in a square graph ?

2 次查看（过去 30 天）
mazari ahmed
mazari ahmed 2015-4-28
回答： Anelmad Anasli 2015-4-29
Given the square representation of n = 256 nodes l want to display in a variable called neighbour{i} that returns all the neighbours of each node. for exemple in the square the number of nodes is n= 256 so l want to get the neighbours of each nodes in a cell array using matlab
for i=1:N
neighbour{i}=[neighbour{i} j]
end
%the code%
N = 16; M = 16; %# 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
[X Y] = meshgrid(1:N,1:M);
X = X(:); Y = Y(:);
adj = squareform( pdist([X Y], distFunc) == 1 );
display(adj);
%# plot connected points on grid
[xx yy] = gplot(adj, [X Y]);
plot(xx, yy, 'ks-', 'MarkerFaceColor','r')
axis([0 N+1 0 M+1])
[X Y] = 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)')) )
linked_node=cell(N,1);
% the most important step
for X=1:N
for Y=1:M
if ((X~=Y) &&(squareform( pdist([X Y], distFunc) == 1)))
linked_node{X}= [linked_node{X} Y];
end
end
end

请先登录，再回答此问题。

回答（2 个）

Sean de Wolski
Sean de Wolski 2015-4-28
编辑：Sean de Wolski 2015-4-28
I would build this as a binary connectivity matrix.
If node 1 is connected to two and three and four is only connected to 2, it would look like this
[0 1 1 0;
1 0 0 1;
1 0 0 0;
0 1 0 0;
This is very easy to traverse to identify connections, for example connected to 2:
connectedTo2 = find(C(:,2))
  3 个评论
显示 1更早的评论
Sean de Wolski
Sean de Wolski 2015-4-28
You would just call find on each column
neighbor{1} = find(C(:,1))
neighbor{2} = find(C(:,2))
neighbor{n} = find(C(:,n))
But storing the information in a connectivity matrix will make updating neighbors easy.
Anelmad Anasli
Anelmad Anasli 2015-4-29
Can l make it in a for loop and then call the set of neighbours when l need it? for i=1:n find(C(:,i)); end

请先登录，再进行评论。

Anelmad Anasli
Anelmad Anasli 2015-4-29
function linked_node = find_neighbours(N, M, CONNECTED)
%# which distance function
if CONNECTED == 8
distFunc = 'chebychev';
else
distFunc = 'cityblock';
end
linked_node=cell(N*M,1);
% the most important step
for X=1:N
for Y=1:M
linked_node{sub2ind([N M], X,Y)} = [];
if X - 1 > 0
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X-1,Y);
if strcmp(distFunc, 'chebychev')
if Y - 1 > 0
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X-1,Y-1);
end
if Y + 1 <= M
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X-1,Y+1);
end
end
end
if X + 1 <= N
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X+1,Y);
if strcmp(distFunc, 'chebychev')
if Y - 1 > 0
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X+1,Y-1);
end
if Y + 1 <= M
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X+1,Y+1);
end
end
end
if Y - 1 > 0
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X,Y-1);
end
if Y + 1 <= M
linked_node{sub2ind([N M], X,Y)}(end+1) = sub2ind([N M], X,Y+1);
end
end
end
end

类别

在 Help Center 和 File Exchange 中查找有关 Nearest Neighbors 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by