在 Matlab 中生成零和一矩阵的更智能方法

Question

我想生成 n 个节点的无向图的所有可能的邻接矩阵（零对角线）。

例如，没有为 n=3 重新标记，我们得到 2^3(3-1)/2 = 8 个可能的网络配置（或邻接矩阵）。

适用于 n = 3 的一个解决方案（我认为这很愚蠢）如下：

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

我也虽然以下似乎更快但我的索引有问题，因为缺少 2 个矩阵：

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]

有没有更快的方法？

Answer 1

我肯定会用二进制编码生成邻接矩阵的非对角线元素：

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

如果您有 Statistics and Machine Learning Toolbox，那么 squareform 将轻松地为您一一创建矩阵：

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

虽然我会考虑沿维度 3 串联，但您可以单独且方便地查看每个矩阵。

或者，您可以自己以矢量化方式进行数组合成，这可能更快（以更多内存为代价）：

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

在 Matlab 中生成零和一矩阵的更智能方法

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

optimization

matlab

graph-theory

matrix

nodes