how to determine the neighbours of each node in a square graph ?
7 views (last 30 days)
Show older comments
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 Comments
Answers (2)
Sean de Wolski
on 28 Apr 2015
Edited: Sean de Wolski
on 28 Apr 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 Comments
Sean de Wolski
on 28 Apr 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
on 29 Apr 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
on 29 Apr 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 Comments
See Also
Categories
Find more on Directed Graphs in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!