对邻接矩阵的行和列进行排序以显示派系
Cec*_*lia 6 algorithm matlab clique-problem adjacency-matrix
我正在寻找一种重新排序技术来将邻接矩阵的连通分量组合在一起.
例如,我用蓝色和绿色两组进行了说明.最初,'1的条目分布在矩阵的行和列中.通过重新排序行和列,所有'1'可以位于矩阵的两个连续部分中,更清楚地显示蓝色和绿色分量.
我不记得这种重新排序技术是什么.我搜索了邻接矩阵,集团,排序和重新排序的许多组合.
我发现的最接近的点击是
symrcm将元素移近对角线,但不制作组.有没有办法重新排序矩阵的行和列,以创建一个密集的角,在R？重点是删除完全空的行和列
请提供此技术的通用名称,以便我可以更有效地谷歌,或指向我的Matlab功能的方向.
我不知道是否有更好的选择可以为您提供直接的结果，但这里有一种方法可以满足您的目的。
您的输入：
>> 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
方法一
将第一行和第一列分别作为Column-Mask(
maskCol)和Row-Mask(maskRow)。
获取哪些值同时包含第一行和第一列的掩码
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
方法2
对于一般情况，如果您事先不知道矩阵，这里是查找maskRow和 的过程maskCol
使用的逻辑：
坐第一排。将其视为列掩码 (
maskCol)。对于第 2 行到最后一行，重复以下过程。
将当前行与 进行比较
maskCol。如果任何一个值与 匹配
maskCol，则找到元素明智的逻辑或并将其更新为新的maskCol重复此过程直到最后一行。
相同的查找过程
maskRow，而列则用于迭代。
代码：
%// 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
注意：此方法可能适用于大多数情况，但对于某些罕见情况仍可能失败。
这是一个例子：
%// 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];
为什么会失败？
当我们循环遍历每一行（以查找列掩码）时，例如，当我们移动到第三行时，没有任何列与第一行（当前
maskCol）匹配。因此，第三行（第二个元素）携带的唯一信息丢失了。这可能是罕见的情况，因为其他一些行可能仍包含相同的信息。请参阅第一个示例。第三行的元素也没有与第一行匹配，但由于最后一行具有相同的信息（第二个元素为 1），因此它给出了正确的结果。只有在极少数情况下，才会发生类似的情况。不过知道这个缺点还是有好处的。
方法三
这是蛮力替代方案。如果您认为之前的案例可能会失败，则可以应用。在这里，我们使用
while loopupdate 多次运行之前的代码（查找行和列掩码）maskCol，以便找到正确的掩码。
程序：
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
获得正确结果所需的迭代次数可能会有所不同。但拥有一个好的数字是安全的。
祝你好运！
| 归档时间： |
|
| 查看次数： |
1524 次 |
| 最近记录： |