webentwicklung-frage-antwort-db.com.de

Erstellen Sie Adjazenzmatrix in MATLAB

Stellen Sie sich eine Reihe von Punkten vor, die in einem Raster der Größe N-by-M angeordnet sind. Ich versuche, die Nachbarschaftsmatrix so zu erstellen, dass benachbarte Punkte miteinander verbunden werden.

Zum Beispiel in einem 3x3-Gitter mit einem Diagramm:

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

Wir sollten die entsprechende Adjazenzmatrix haben:

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

Als Bonus sollte die Lösung für benachbarte Punkte mit 4 und 8 Verbindungen funktionieren, das heißt:

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

Dies ist der Code, den ich bisher habe:

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

Wie kann dies verbessert werden, um alle Schleifen zu vermeiden?

30
Dave

Wenn Sie feststellen, haben die von Ihnen erstellten Adjazenzmatrizen ein eindeutiges Muster. Sie sind insbesondere symmetrisch und banded . Sie können diese Tatsache nutzen, um Ihre Matrizen mit der Funktion diag (oder der Funktion spdiags , wenn Sie eine dünnbesetzte Matrix erstellen möchten) einfach zu erstellen. So können Sie die Adjazenzmatrix für jeden Fall erstellen, indem Sie Ihre Beispielmatrix oben als Beispiel verwenden:

4 verbundene Nachbarn:

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)+diag(diagVec2, c);   % Add the diagonals to a zero matrix
adj = adj+adj.';                             % Add the matrix to a transposed copy of
                                             %   itself to make it symmetric

Und Sie erhalten die folgende Matrix:

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 verbundene Nachbarn:

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

Und Sie erhalten die folgende Matrix:

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
24
gnovice

Nur zum Spaß ist hier eine Lösung zum Erstellen der Adjazenzmatrix durch Berechnen des Abstands zwischen allen Punktpaaren im Raster (offensichtlich nicht der effizienteste Weg).

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

Und hier ist etwas Code, um die Adjazenzmatrix und die Grafik der verbundenen Punkte zu visualisieren:

%# 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

14
Amro

Ich habe diese Frage gerade gefunden, als ich nach demselben Problem suchte. Keine der angebotenen Lösungen funktionierte für mich jedoch aufgrund der Problemgröße, die die Verwendung spärlicher Matrixtypen erforderte. Hier ist meine Lösung, die in großen Instanzen funktioniert:

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
mnmltype

Ist gerade auf diese Frage gestoßen. Ich habe eine schöne funktionierende m-Funktion (link: sparse_adj_matrix.m ), die recht allgemein ist.

Es kann 4-Connect-Netze (Radius 1 gemäß L1-Norm) und 8-Connect-Netze (Radius 1 gemäß L_Infty-Norm) verarbeiten.
Es kann auch 3D (und beliebig höherdimensionale Raster) unterstützen.
Die Funktion kann auch Knoten weiter als radius = 1 verbinden.

Hier ist die Signitur der Funktion:


% 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(:)]);
2
Shai

Ihr aktueller Code scheint nicht so schlecht zu sein. Auf die eine oder andere Weise müssen Sie alle Nachbarpaare durchlaufen. Wenn Sie den Code wirklich optimieren müssen, würde ich Folgendes vorschlagen:

  • schleife über Knotenindizes i, wobei 1 <= i <= (N*M)
  • verwenden Sie nicht 2, um die Effizienz zu verbessern, die Nachbarn von Knoten i sind einfach [i-M, i+1, i+M, i-1] im Uhrzeigersinn

Beachten Sie Folgendes, um alle benachbarten Knotenpaare zu erhalten:

  • sie müssen nur die "rechten" Nachbarn (d. h. horizontale Kanten) für Knoten i % M != 0 berechnen (da Matlab nicht 0-basiert, sondern 1-basiert ist).
  • sie müssen nur "über" Nachbarn (d. h. vertikale Kanten) für Knoten berechnen. i > M
  • für diagonale Kanten gilt eine ähnliche Regel

Dies würde zu einer einzelnen Schleife führen (aber dieselbe Anzahl von N * M-Iterationen), ruft nicht,2ind () auf und hat nur zwei if-Anweisungen in der Schleife.

2
catchmeifyoutry

Fügen Sie für jeden Knoten in der Grafik eine Verbindung nach rechts und eine nach unten hinzu. Stellen Sie sicher, dass Sie Ihr Raster nicht überschreiten. Betrachten Sie die folgende Funktion, die die Adjazenzmatrix aufbaut.

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

Beispiel wie oben 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
0
ja72