Menu
Consider a set of points arranged on a grid of size N-by-M. I am trying to build the adjacency matrix such that neighboring points are connected.
For example, in a 3x3 grid with a graph:
1-2-3 | | | 4-5-6 | | | 7-8-9 We should have the corresponding adjacency 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 | +---+------------------------------------------------------+ As a bonus, the solution should work for both 4- and 8-connected neighboring points, that is:
o o o o o X o vs. o X o o o o o This the code that I have so far:
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 How can this improved to avoid all the looping?
710
To construct the adjacency matrix of a graph, the nodes are numbered 1 to N. Then each element (i,j) of the N-by-N matrix is set to 1 if node i is connected to node j, and 0 otherwise. Thus, for undirected graphs the adjacency matrix is symmetric, but this need not be the case for directed graphs.
A = adjacency( G ,'weighted') returns a weighted adjacency matrix, where for each edge (i,j) , the value A(i,j) contains the weight of the edge. If the graph has no edge weights, then A(i,j) is set to 1. For this syntax, G must be a simple graph such that ismultigraph(G) returns false .
To fill the adjacency matrix, we look at the name of the vertex in row and column. If those vertices are connected by an edge or more, we count number of edges and put this number as matrix element. The matrix to represent a graph in this way is called Adjacency matrix .
Description. plotmatrix( X , Y ) creates a matrix of subaxes containing scatter plots of the columns of X against the columns of Y . If X is p-by-n and Y is p-by-m, then plotmatrix produces an n-by-m matrix of subaxes.
If you notice, there is a distinct pattern to the adjacency matrices you are creating. Specifically, they are symmetric and banded. You can take advantage of this fact to easily create your matrices using the diag function (or the spdiags function if you want to make a sparse matrix). Here is how you can create the adjacency matrix for each case, using your sample matrix above as an example:
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 And you'll get the following 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 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 And you'll get the following 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 If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
