how to determine the neighbours of each node in a square graph ?
2 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/149568/image.jpeg)
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
0 commentaires
Réponses (2)
Sean de Wolski
le 28 Avr 2015
Modifié(e) : Sean de Wolski
le 28 Avr 2015
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 commentaires
Sean de Wolski
le 28 Avr 2015
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
le 29 Avr 2015
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
le 29 Avr 2015
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
0 commentaires
Voir également
Catégories
En savoir plus sur Directed Graphs dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!