Sort rows and columns of adjacency matrix to display clicks

I am looking for a reordering method to combine the related components of an adjacency matrix.

For example, I made an illustration with two groups, blue and green. Initially, β€œ1 record is distributed across the rows and columns of the matrix. By reordering rows and columns, allβ€œ 1 ”can be located in two adjacent slices of the matrix, more clearly displaying the blue and green components.

Illustration

I don’t remember what this reordering technique is called. I searched for a lot of combinations of adjacency matrix, click, sort and reorder.

Upcoming hits I found

Please provide a common name for this technique so that I can use Google more efficiently or point me to the direction of the Matlab function.

+6
source share
1 answer

I don't know if there is a better alternative that should give you direct results, but here is one approach that can serve your purpose.

Your input:

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

Method 1

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

Get a mask whose values ​​contain both in the first row and in the first column

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

Rearrange lines (according to line mask)

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

Gives something like this:

 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 

Reorder columns (according to column mask)

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

It gives the desired results:

 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 

Just check if the indexes are where they should be, or if you need the appropriate reordered indexes;)

Before reinstalling:

 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 

After reassembling (same process as before)

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

Output:

 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 

Method 2

For the General case , if you do not know the matrix in advance, here is the maskRow and maskCol search procedure

Logic Used:

  • Take the first line. Consider it as a column mask ( maskCol ).

  • For the second line to the last line, the next process is repeated.

  • Compare the current line with maskCol .

  • If any value matches maskCol , find the element wise logical OR and update it as a new maskCol

  • Repeat this process to the last line.

  • The same process to search for maskRow , while the column is used for iteration.

Code:

 %// 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 is an example to try the following:

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

Then repeat the above procedure:

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

Here is the result:

 >> 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 cases, but may fail for some rare cases.

Here is an example:

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

Why is this failing?

When we scroll through each row (to find the mask of the column), for example, when we go to the third row, none of the columns matches the first row (current maskCol ). Thus, the only information that is carried over by the third line (2nd element) is lost.

This may be a rare case, because some other line may contain the same information. See the first example. Also, none of the elements of the third row matches the first row, but since the last row has the same information (1 on the 2nd element), it gave the correct results. Only in rare cases can this happen. However, it is good to know this flaw.

Method 3

This option is an alternative to brute force. It can be applied if you think that the previous case may fail. Here we use a while loop to run the previous code (search for a string and a count mask) a number of times with the updated maskCol so that it finds the correct mask.

Procedure:

  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 

The previous example is executed (when the previous method fails) and is executed with and without while-loop

Without brute force:

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

With a Brute-Forcing while loop:

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

The number of iterations needed to get the right results may vary. But it's safe to have a good number.

Good luck

+2
source

Source: https://habr.com/ru/post/988183/


All Articles