Erstellen Sie eine Adjazenzmatrix in MATLAB

Betrachten eine Reihe von Punkten angeordnet, die auf einem raster der Größe N-M.
Ich bin versucht zu bauen, die Nähe matrix, so dass
benachbarte Punkte miteinander verbunden sind.

Beispielsweise in einem 3x3-raster mit einem Diagramm:

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

Sollten wir die entsprechende Nachbarschaft-matrix:

+---+------------------------------------------------------+
|   |   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 funktionieren sowohl für 4 - und 8-verbunden sind die benachbarten Punkte, das ist:

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

Dieser den code, den ich bisher:

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 dieser verbessert werden, um zu vermeiden, all die Schleife?

Kommentar zu dem Problem
Nein, das ist keine Hausaufgabe. Mein Ziel ist es Plotten Sie diese Punkte und Linien zeichnen zwischen verbundenen Punkte als graph. Das interessante an der Sache ist, dass diese Punkte nicht zu bleiben, die sich auf dem grid.. Kommentarautor: Dave

InformationsquelleAutor der Frage Dave | 2010-07-18

  1. 23

    Wenn Sie bemerken,, es ist ein deutliches Muster der Nähe-Matrizen, die Sie erstellen. Insbesondere sind symmetrische und gebändert. Sie können diese Tatsache nutzen, um einfach erstellen Sie Ihre Matrizen mit der DIAG Funktion (oder die SPDIAGS Funktion, wenn Sie möchten, um eine sparse matrix). Hier ist, wie können Sie erstellen, die Nähe matrix für jeden Fall, mit Ihrer Probe die matrix oben als Beispiel:

    4-angeschlossen 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)+...                %# 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

    , 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-angeschlossen 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

    InformationsquelleAutor der Antwort gnovice

  2. 13

    Nur zum Spaß, hier ist eine Lösung zu konstruieren, die Nachbarschaft-matrix durch Berechnung der Distanz zwischen allen Paaren von Punkten auf dem Gitter (nicht der effizienteste Weg, natürlich)

    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 sind einige code-Visualisierung der Nachbarschaft-matrix und der graph der verbundenen Punkte:

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

    Erstellen Sie eine Adjazenzmatrix in MATLAB
    Erstellen Sie eine Adjazenzmatrix in MATLAB

    InformationsquelleAutor der Antwort Amro

  3. 4

    Ich habe gerade diese Frage bei der Suche nach dem gleichen problem. Jedoch, keine der Lösungen funktionierte für mich, weil das problem der Größe, die erforderlich, die Verwendung von sparse-matrix-Typen. Hier ist meine Lösung, die funktioniert auf großen Instanzen:

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

    InformationsquelleAutor der Antwort mnmltype

  4. 2

    Ihrer aktuellen code scheint nicht so schlimm. Die eine oder andere Weise müssen Sie die Iteration über alle Nachbarn Paaren. Wenn Sie wirklich brauchen, um den code optimieren, würde ich vorschlagen:

    • Schleife über Knoten-Indizes i, wo 1 <= i <= (N*M)
    • nicht verwenden, sub2ind() für die Effizienz, den Nachbarn von Knoten i sind simpy [i-M, i+1, i+M, i-1] im Uhrzeigersinn

    Bemerken, dass man alle Nachbarn Paaren von Knoten:

    • Sie haben nur zu berechnen, die "richtigen" Nachbarn (d.h. die horizontalen Kanten) für Knoten i % M != 0 (seit Matlab ist nicht 0-basiert sondern 1-basiert)
    • Sie haben nur zu berechnen "oben" Nachbarn (d.h. die vertikalen Kanten) für Knoten i > M
    • gibt es eine ähnliche Regel für Diagonale Kanten

    Dies würde leed zu einem single-loop - (aber gleiche Anzahl von N*M Iterationen), wird aufrufen nicht sub2ind(), und hat nur zwei if-Anweisungen in der Schleife.

    InformationsquelleAutor der Antwort catchmeifyoutry

  5. 2

    Kam gerade über diese Frage. Ich habe eine schöne Arbeit m-Funktion (link: sparse_adj_matrix.m), dass ganz allgemein.

    Es kann mit 4-connect-raster (radius 1 nach L1-norm), 8-connect-raster (radius 1 nach L_infty norm).

    Es können auch 3D Unterstützung (und beliebig höher domensional grids).

    Die Funktion kann auch die Verbindung von Knoten weiter als radius = 1.

    Hier ist die Signatur 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(:)]);

    InformationsquelleAutor der Antwort Shai

  6. 0

    Für jeden Knoten in dem Graphen hinzu kommt eine Verbindung nach rechts und eine nach unten. Überprüfen Sie, dass Sie nicht überfordert mit Ihrem grid. Betrachten Sie die folgende Funktion baut, dass die Nachbarschaft-matrix.

    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

    InformationsquelleAutor der Antwort ja72

Schreibe einen Kommentar