Подтвердить что ты не робот

Построить матрицу смежности в MATLAB

Рассмотрим множество точек, расположенных на сетке размера N-by-M. Я пытаюсь построить матрицу смежности так, чтобы соседние точки подключены.

Например, в сетке 3x3 с графиком:

1-2-3
| | |
4-5-6
| | |
7-8-9

Мы должны иметь соответствующую матрицу смежности:

+---+------------------------------------------------------+
|   |   1     2     3     4     5     6     7     8     9  |
+---+------------------------------------------------------+
| 1 |   0     1     0     1     0     0     0     0     0  |
| 2 |   1     0     1     0     1     0     0     0     0  |
| 3 |   0     1     0     0     0     1     0     0     0  |
| 4 |   1     0     0     0     1     0     1     0     0  |
| 5 |   0     1     0     1     0     1     0     1     0  |
| 6 |   0     0     1     0     1     0     0     0     1  |
| 7 |   0     0     0     1     0     0     0     1     0  |
| 8 |   0     0     0     0     1     0     1     0     1  |
| 9 |   0     0     0     0     0     1     0     1     0  |
+---+------------------------------------------------------+

В качестве бонуса решение должно работать как для 4- и 8-связанных соседних точек, а именно:

   o             o  o  o
o  X  o   vs.    o  X  o
   o             o  o  o

Этот код, который у меня есть до сих пор:

N = 3; M = 3;
adj = zeros(N*M);

for i=1:N
    for j=1:M
        k = sub2ind([N M],i,j);
        if i>1
            ii=i-1; jj=j;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
        if i<N
            ii=i+1; jj=j;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
        if j>1
            ii=i; jj=j-1;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
        if j<M
            ii=i; jj=j+1;
            adj(k,sub2ind([N M],ii,jj)) = 1; 
        end
    end
end

Как это можно улучшить, чтобы избежать всех циклов?

4b9b3361

ОТВЕТЫ

Ответ 1

Если вы заметили, существует отдельный шаблон для создаваемых вами матриц смежности. В частности, они симметричны и banded. Вы можете воспользоваться этим фактом, чтобы легко создать свои матрицы, используя функцию DIAG (или SPDIAGS, если вы хотите сделать разреженную матрицу). Вот как вы можете создать матрицу смежности для каждого случая, используя примерную матрицу выше в качестве примера:

4-связанные соседи

mat = [1 2 3; 4 5 6; 7 8 9];              %# Sample matrix
[r,c] = size(mat);                        %# Get the matrix size
diagVec1 = repmat([ones(c-1,1); 0],r,1);  %# Make the first diagonal vector
                                          %#   (for horizontal connections)
diagVec1 = diagVec1(1:end-1);             %# Remove the last value
diagVec2 = ones(c*(r-1),1);               %# Make the second diagonal vector
                                          %#   (for vertical connections)
adj = diag(diagVec1,1)+...                %# Add the diagonals to a zero matrix
      diag(diagVec2,c);
adj = adj+adj.';                         %'# Add the matrix to a transposed
                                          %#   copy of itself to make it
                                          %#   symmetric

И вы получите следующую матрицу:

adj =

     0     1     0     1     0     0     0     0     0
     1     0     1     0     1     0     0     0     0
     0     1     0     0     0     1     0     0     0
     1     0     0     0     1     0     1     0     0
     0     1     0     1     0     1     0     1     0
     0     0     1     0     1     0     0     0     1
     0     0     0     1     0     0     0     1     0
     0     0     0     0     1     0     1     0     1
     0     0     0     0     0     1     0     1     0


8-связные соседи

mat = [1 2 3; 4 5 6; 7 8 9];              %# Sample matrix
[r,c] = size(mat);                        %# Get the matrix size
diagVec1 = repmat([ones(c-1,1); 0],r,1);  %# Make the first diagonal vector
                                          %#   (for horizontal connections)
diagVec1 = diagVec1(1:end-1);             %# Remove the last value
diagVec2 = [0; diagVec1(1:(c*(r-1)))];    %# Make the second diagonal vector
                                          %#   (for anti-diagonal connections)
diagVec3 = ones(c*(r-1),1);               %# Make the third diagonal vector
                                          %#   (for vertical connections)
diagVec4 = diagVec2(2:end-1);             %# Make the fourth diagonal vector
                                          %#   (for diagonal connections)
adj = diag(diagVec1,1)+...                %# Add the diagonals to a zero matrix
      diag(diagVec2,c-1)+...
      diag(diagVec3,c)+...
      diag(diagVec4,c+1);
adj = adj+adj.';                         %'# Add the matrix to a transposed
                                          %#   copy of itself to make it
                                          %#   symmetric

И вы получите следующую матрицу:

adj =

     0     1     0     1     1     0     0     0     0
     1     0     1     1     1     1     0     0     0
     0     1     0     0     1     1     0     0     0
     1     1     0     0     1     0     1     1     0
     1     1     1     1     0     1     1     1     1
     0     1     1     0     1     0     0     1     1
     0     0     0     1     1     0     0     1     0
     0     0     0     1     1     1     1     0     1
     0     0     0     0     1     1     0     1     0

Ответ 2

Просто для удовольствия, здесь решение построить матрицу смежности, вычисляя расстояние между всеми парами точек на сетке (очевидно, не самый эффективный способ)

N = 3; M = 3;                  %# 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 );

И вот некоторый код для визуализации матрицы смежности и графика связанных точек:

%# plot adjacency matrix
subplot(121), spy(adj)

%# plot connected points on grid
[xx yy] = gplot(adj, [X Y]);
subplot(122), plot(xx, yy, 'ks-', 'MarkerFaceColor','r')
axis([0 N+1 0 M+1])
%# add labels
[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)')) )

8_connected4_connected

Ответ 3

Я просто нашел этот вопрос при поиске той же проблемы. Однако ни один из предоставленных решений не работал у меня из-за размера проблемы, который требовал использования разреженных типов матриц. Вот мое решение, которое работает в больших масштабах:

function W = getAdjacencyMatrix(I)

[m, n] = size(I);

I_size = m*n;

% 1-off diagonal elements
V = repmat([ones(m-1,1); 0],n, 1);
V = V(1:end-1); % remove last zero

% n-off diagonal elements
U = ones(m*(n-1), 1);

% get the upper triangular part of the matrix
W = sparse(1:(I_size-1),    2:I_size, V, I_size, I_size)...
  + sparse(1:(I_size-m),(m+1):I_size, U, I_size, I_size);

% finally make W symmetric
W = W + W';

Ответ 4

Ваш текущий код выглядит не так уж плохо. Так или иначе вам нужно перебирать все соседние пары. Если вам действительно нужно оптимизировать код, я бы предложил:

  • цикл через node индексы i, где 1 <= i <= (N*M)
  • не используйте sub2ind() для эффективности, соседи node я являются simpy [i-M, i+1, i+M, i-1] по часовой стрелке

Обратите внимание, что для получения всех соседних пар узлов:

  • вам нужно только вычислить "правильных" соседей (то есть горизонтальных ребер) для узлов i % M != 0 (так как Matlab не основан на 0, а основан на 1)
  • вам нужно только вычислить "выше" соседей (т.е. вертикальные края) для узлов i > M
  • существует аналогичное правило для диагональных ребер

Это будет связано с одним циклом (но с таким же числом итераций N * M), не вызывает sub2ind() и имеет только два оператора if в цикле.

Ответ 5

Просто наткнулся на этот вопрос. У меня хорошая рабочая m-функция (ссылка: sparse_adj_matrix.m), которая является довольно общей.

Он может обрабатывать сетку с 4 соединениями (радиус 1 согласно норме L1), 8-соединительную сетку (радиус 1 согласно норме L_infty).
Он также может поддерживать 3D (и произвольно более высокомерные сетки).
Функция также может соединять узлы дальше радиуса = 1.

Здесь знак функции:


% Construct sparse adjacency matrix (provides ii and jj indices into the
% matrix)
%
% Usage:
%   [ii jj] = sparse_adj_matrix(sz, r, p)
%
% inputs:
%   sz - grid size (determine the number of variables n=prod(sz), and the
%        geometry/dimensionality)
%   r  - the radius around each point for which edges are formed
%   p  - in what p-norm to measure the r-ball, can be 1,2 or 'inf'
%
% outputs
%   ii, jj - linear indices into adjacency matrix (for each pair (m,n)
%   there is also the pair (n,m))
%
% How to construct the adjacency matrix?
% >> A = sparse(ii, jj, ones(1,numel(ii)), prod(sz), prod(sz));
%
%
% Example:
% >> [ii jj] = sparse_adj_matrix([10 20], 1, inf);
% construct indices for 200x200 adjacency matrix for 8-connect graph over a
% grid of 10x20 nodes.
% To visualize the graph:
% >> [r c]=ndgrid(1:10,1:20);
% >> A = sparse(ii, jj, 1, 200, 200);;
% >> gplot(A, [r(:) c(:)]);

Ответ 6

Для каждого node на графике добавьте соединение справа и один вниз. Убедитесь, что вы не перегружаете свою сетку. Рассмотрим следующую функцию, которая строит матрицу смежности.

function  adj = AdjMatrixLattice4( N, M )
    % Size of adjacency matrix
    MN = M*N;
    adj = zeros(MN,MN);

    % number nodes as such
    %  [1]---[2]-- .. --[M]
    %   |     |          |
    % [M+1]-[M+2]- .. -[2*M]
    %   :     :          :
    %   []    []   ..  [M*N]     

    for i=1:N
        for j=1:N
            A = M*(i-1)+j;          %Node # for (i,j) node
            if(j<N)                
                B = M*(i-1)+j+1;    %Node # for node to the right
                adj(A,B) = 1;
                adj(B,A) = 1;
            end
            if(i<M)
                B = M*i+j;          %Node # for node below
                adj(A,B) = 1;       
                adj(B,A) = 1;
            end            
        end
    end    
end

Пример выше AdjMatrixLattice4(3,3)=

 0     1     0     1     0     0     0     0     0
 1     0     1     0     1     0     0     0     0
 0     1     0     0     0     1     0     0     0
 1     0     0     0     1     0     1     0     0
 0     1     0     1     0     1     0     1     0
 0     0     1     0     1     0     0     0     1
 0     0     0     1     0     0     0     1     0
 0     0     0     0     1     0     1     0     1
 0     0     0     0     0     1     0     1     0