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

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

Answer 1

[Sean de Wolski]

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))

[mazari ahmed]

l don't inderstand the function find(C(:,2)) ? l want to get for each node its set of neighbours for exemple neighbours{1} = {2,3,4} neighbours{2} = {1,3,4} . . . neighbours{n=256} = {45,78,17,34,52...}

[Sean de Wolski]

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]

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]

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