Erstellen Sie Adjazenzmatrix in MATLAB

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

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

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

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.

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