Rearranging rows of a boolean matrix so that the diagonals are all non-zero if possible
8 views (last 30 days)
Show older comments
Hello, just as a disclaimer I have a question about improving my code, not on how to get it to work.
I wrote a code that rearranges just the rows of a boolean matrix so that the diagonal values are all non-zero. This code gets pretty slow as the matrix being fed in gets pretty large. It starts lagging pretty bad with 25x25 matrices. I'm curious what I can do to speed my code up.
Here is the function that I have right now:
function [reAdmis, unmatchedTaskList] = rearrange(admis)
[n,~] = size(admis);
potAssignment = zeros(1,n);%potential assignments
dList=1:n; %Decision list: elements are zeroed if chosen
reAdmis = zeros(n,n); % reAdmis will be the answer
AdmisTemp = admis;
CC = sum(admis,1); %column count
RC = sum(admis,2); %row count
[~, colIndex] = sort(CC);
[~, rowIndex] = sort(RC);
[reAdmisTemp, dIndex] = reorganizeRow(AdmisTemp, rowIndex, n); %reorganizes the rows based on RC
for i = 1:n
for j = 1:n
if reAdmisTemp(j,colIndex(i))
reAdmis(colIndex(i),:)=admis(rowIndex(j),:);
AdmisTemp(rowIndex(j),:)=zeros; %used row gets zeroed
dList(dIndex(j))=0; % chosen element in dList is zeroed
potAssignment(dIndex(j))=colIndex(i); %Potential assignment is updated
AdmisTemp(:,colIndex(i))=zeros; %used column gets zeroed
break
end
end
CC = sum(AdmisTemp,1);
RC = sum(AdmisTemp,2);
[~, colIndex] = sort(CC);
[~, rowIndex] = sort(RC);
[reAdmisTemp, dIndex] = reorganizeRow(AdmisTemp, rowIndex, n);
end
end
function [organized, dIndex] = reorganizeRow(A, dIndex, n)
organized = zeros(n,n);
for i = 1:n
organized(i,:)=A(dIndex(i),:);
end
end
An example boolean matrix to use and its output could be:
admis = [1 0 1 0 0
0 0 0 0 1
1 1 0 0 1
0 1 0 1 1
1 1 1 1 1]
reAdmis = [1 1 0 0 1
0 1 0 1 1
1 0 1 0 0
1 1 1 1 1
0 0 0 0 1]
My hope is that this can be as fast as possible. I have no hard number for a time requirement, however my clocked speed using tic-toc was about 0.0003 seconds, which I'd like to be able to beat.
Thank you in advance for any help that you are able to provide
4 Comments
Answers (2)
Bruno Luong
on 16 Jul 2020
Your problem belong to the so-called "Assignment problem", that has dedicated algorithm called Hungarian assigment.
Take a look on the formal definition, try to understand it then find some implementation on File Exchange.
Matt J
on 11 Jul 2020
When your version works, it often works faster than the version below, however your version doesn't always get it right. I've attached a .mat file with an example matrix admis for which your version does not manage to get all non-zero diagonal elements.
load admis700 admis
N=size(admis,1);
P=optimvar('P',[N,N],'LowerBound',0,'UpperBound',1,'Type','integer');
prob=optimproblem('ObjectiveSense','max');
prob.Constraints.row=sum(P,1)==ones(1,N);
prob.Constraints.col=sum(P,2)==ones(N,1);
E=speye(N);
opts=optimoptions('intlinprog','Display','none');
tic;
prob.Objective=sum(sum((P*admis).*E));
sol=solve(prob,'options',opts);
reAdmis=round(sol.P)*admis;
toc;
6 Comments
Matt J
on 18 Jul 2020
Edited: Matt J
on 18 Jul 2020
The randomization procedure that I used to explore different choices of admis did not ensure this, however, the example failure cases admis10.mat and admis700.mat that I provided for you did have solutions where all the diagonal elements are one, as you will see when you run either my code or Bruno's.
In any case, I do not think there is any longer any reason for you to focus on either my solution or your own. Bruno's solution works and, for large N, is the fastest among all 3 methods. To demonstrate, I attach a 3rd data example, for which your solution does happen to work:
load admis200
tic;
R1=Lindsay(admis);
toc;
tic
R2=MattJ(admis);
toc
tic
R3=Bruno(admis);
toc
Tr1=trace(R1)
Tr2=trace(R2)
Tr3=trace(R3)
results in
Elapsed time is 0.030986 seconds.
Elapsed time is 0.135317 seconds.
Elapsed time is 0.015373 seconds.
Tr1 =
200
Tr2 =
200
Tr3 =
200
See Also
Categories
Find more on Logical in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!