algorithm - 对邻接矩阵的行和列进行排序以显示派系

Question

我正在寻找一种重新排序技术来将邻接矩阵的连接组件组合在一起。

例如，我制作了一个插图，其中包含两个组，蓝色和绿色。最初，'1' 的条目分布在矩阵的行和列中。通过重新排列行和列，所有“1”都可以位于矩阵的两个连续部分，从而更清楚地显示蓝色和绿色分量。

我不记得这种重新排序技术叫什么了。我已经搜索了许多邻接矩阵、团、排序和重新排序的组合。

我找到的最接近的匹配项是

1. symrcm将元素移近对角线，但不进行分组。

2. Is there a way to reorder the rows and columns of matrix to create a dense corner, in R?重点是删除完全空的行和列

请提供此技术的通用名称，以便我可以更有效地进行谷歌搜索，或者为我指明 Matlab 函数的方向。

Answer 1

我不知道是否有更好的替代方法可以给您带来直接的结果，但这里有一种方法可以满足您的目的。

您的输入:

>> A

A =

 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1

方法一

Taking first row and first column as Column-Mask(maskCol) and Row-Mask(maskRow) respectively.

获取掩码，其值在第一行和第一列中都包含ones

maskRow = A(:,1)==1;
maskCol = A(1,:)~=1;

重新排列行(根据行掩码)

out = [A(maskRow,:);A(~maskRow,:)];

给出这样的东西:

out =

 1     0     0     1     0
 1     0     0     1     0
 0     1     1     0     1
 0     1     1     0     1
 0     1     1     0     1

重新排列列(根据列掩码)

out = [out(:,maskCol),out(:,~maskCol)]

给出期望的结果:

out =

 1     1     0     0     0
 1     1     0     0     0
 0     0     1     1     1
 0     0     1     1     1
 0     0     1     1     1

---

只需检查索引是否在它们应该在的位置，或者您是否想要相应的重新排列的索引；)

重新排列之前:

idx = reshape(1:25,5,[])

idx =

 1     6    11    16    21
 2     7    12    17    22
 3     8    13    18    23
 4     9    14    19    24
 5    10    15    20    25

重新排列后(与之前相同的过程)

outidx = [idx(maskRow,:);idx(~maskRow,:)];
outidx = [outidx(:,maskCol),outidx(:,~maskCol)]

输出:

outidx =

 2    17     7    12    22
 4    19     9    14    24
 1    16     6    11    21
 3    18     8    13    23
 5    20    10    15    25

---

方法二

对于一般情况，如果您事先不知道矩阵，这里是查找maskRow 和maskCol 的过程

Logic used:

1. Take first row. Consider it as column mask (maskCol).

2. For 2nd row to last row, the following process are repeated.

3. Compare the current row with maskCol.

4. If any one value matches with the maskCol, then find the element wise logical OR and update it as new maskCol

5. Repeat this process till the last row.

6. Same process for finding maskRow while the column are used for iterations instead.

代码:

%// If you have a square matrix, you can combine both these loops into a single loop.
maskCol = A(1,:);
for ii = 2:size(A,1)
    if sum(A(ii,:) & maskCol)>0 
        maskCol = maskCol | A(ii,:);
    end
end

maskCol = ~maskCol;

maskRow = A(:,1);
for ii = 2:size(A,2)
    if sum(A(:,ii) & maskRow)>0 
        maskRow = maskRow | A(:,ii);
    end
end

这是一个尝试的例子:

%// Here I removed some 'ones' from first, last rows and columns.
%// Compare it with the original example.
A = [0     0     1     0     1
     0     0     0     1     0
     0     1     1     0     0
     1     0     0     1     0
     0     1     0     0     1];

然后，重复之前的步骤:

out = [A(maskRow,:);A(~maskRow,:)];        %// same code used
out = [out(:,maskCol),out(:,~maskCol)];    %// same code used

结果如下:

>> out

out =

 0     1     0     0     0
 1     1     0     0     0
 0     0     0     1     1
 0     0     1     1     0
 0     0     1     0     1

Note: This approach may work for most of the cases but still may fail for some rare cases.

举个例子:

%// this works well.
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     1     0     0     1    1];

%// This may not
%// Second col, last row changed to zero from one
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     0     0     0     1    1];

为什么会失败？

As we loop through each row (to find the column mask), for eg, when we move to 3rd row, none of the cols match the first row (current maskCol). So the only information carried by 3rd row (2nd element) is lost.

This may be the rare case because some other row might still contain the same information. See the first example. There also none of the elements of third row matches with 1st row but since the last row has the same information (1 at the 2nd element), it gave correct results. Only in rare cases, similar to this might happen. Still it is good to know this disadvantage.

方法三

This one is Brute-force Alternative. Could be applied if you think the previous case might fail. Here, we use while loop to run the previous code (finding row and col mask) number of times with updated maskCol, so that it finds the correct mask.

程序:

 maskCol = A(1,:);
 count = 1;
 while(count<3)
     for ii = 2:size(A,1)
         if sum(A(ii,:) & maskCol)>0
             maskCol = maskCol | A(ii,:);
         end
     end
     count = count+1;
 end

采用上一个示例(上一个方法失败的地方)并在使用和不使用 while-loop

的情况下运行

没有蛮力:

>> out

out =

 1     0     1     0     0     0
 1     0     1     0     0     0
 0     0     0     1     1     0
 0     1     0     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

使用暴力破解 while 循环:

>> out

out =

 1     1     0     0     0     0
 1     1     0     0     0     0
 0     0     0     1     1     0
 0     0     1     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

获得正确结果所需的迭代次数可能会有所不同。但是有一个好的数字是安全的。

祝你好运!