Smarter way to generate a matrix of zeros and ones in Matlab

Question

I would like to generate all the possible adjacency matrices (zero diagonale) of an undirected graph of n nodes.

For example, with no relabeling for n=3 we get 2^3(3-1)/2 = 8 possible network configurations (or adjacency matrices).

One solution that works for n = 3 (and which I think is quite stupid) would be the following:

n = 3;
A = [];
for k = 0:1
    for j = 0:1
        for i = 0:1
            m = [0 , i , j ; i , 0 , k ; j , k , 0 ];
            A = [A, m];
        end
    end
end

Also I though of the following which seems to be faster but something is wrong with my indexing since 2 matrices are missing:

n = 3
C = [];
E = [];

A = zeros(n);

for i = 1:n
    for j = i+1:n
        A(i,j) = 1;
        A(j,i) = 1;
        C = [C,A];
    end
end

B = ones(n);
B = B- diag(diag(ones(n)));
for i = 1:n
    for j = i+1:n
        B(i,j) = 0;
        B(j,i) = 0;
        E = [E,B];
    end
end

D = [C,E]

Is there a faster way of doing this?

Answer 1

I would definitely generate the off-diagonal elements of the adjacency matrices with binary encoding:

n = 4;  %// number of nodes
m = n*(n-1)/2;
offdiags = dec2bin(0:2^m-1,m)-48; %//every 2^m-1 possible configurations

If you have the Statistics and Machine Learning Toolbox, then squareform will easily create the matrices for you, one by one:

%// this is basically a for loop
tmpcell = arrayfun(@(k) squareform(offdiags(k,:)),1:size(offdiags,1),...
                 'uniformoutput',false);
A = cat(2,tmpcell{:}); %// concatenate the matrices in tmpcell

Although I'd consider concatenating along dimension 3, then you can see each matrix individually and conveniently.

Alternatively, you can do the array synthesis yourself in a vectorized way, it's probably even quicker (at the cost of more memory):

A = zeros(n,n,2^m);
%// lazy person's indexing scheme:
[ind_i,ind_j,ind_k] = meshgrid(1:n,1:n,1:2^m);
A(ind_i>ind_j) = offdiags.'; %'// watch out for the transpose

%// copy to upper diagonal:
A = A + permute(A,[2 1 3]);  %// n x n x 2^m matrix

%// reshape to n*[] matrix if you wish
A = reshape(A,n,[]);         %// n x (n*2^m) matrix