how to determine the neighbours of each node in a square graph ?
1 回表示 (過去 30 日間)
古いコメントを表示
![](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 件のコメント
回答 (2 件)
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 件のコメント
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
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
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
0 件のコメント
参考
カテゴリ
Help Center および File Exchange で Directed Graphs についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!