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

Question

mazari ahmed 2015-4-28

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/213955-how-to-determine-the-neighbours-of-each-node-in-a-square-graph

回答： 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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Sean de Wolski 2015-4-28

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/213955-how-to-determine-the-neighbours-of-each-node-in-a-square-graph#answer_176977

编辑：Sean de Wolski 2015-4-28

在 MATLAB Online 中打开

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

This is very easy to traverse to identify connections, for example connected to 2:

connectedTo2 = find(C(:,2))

3 个评论
显示 1更早的评论隐藏 1更早的评论

Sean de Wolski 2015-4-28

在 MATLAB Online 中打开

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

请先登录，再进行评论。

Answer 2

Anelmad Anasli 2015-4-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/213955-how-to-determine-the-neighbours-of-each-node-in-a-square-graph#answer_177194

在 MATLAB Online 中打开

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